Machine Learning in the Browser

Athan Reines | @kgryte | @stdlibjs

Overview

Motivation
JavaScript
Examples
Libraries and Frameworks
Web Standards
Tips and Tricks
Conclusions

The talk overview is as follows...

First, I will motivate why machine learning in browser environments is important and why you should care.
Next, as this talk concerns machine learning in the browser, I will discuss JavaScript as it relates to machine learning.
Then, I will walk through some browser-based machine learning examples.
I'll then highlight a few promising libraries and frameworks for browser-based machine learning.
Next, I'll discuss what is happening at the standards level which is making the web platform a better environment for machine learning.
Then, I'll offer some tips and tricks.
And finally, I will offer some conclusions and additional resources you can use to get up and running.

If I move too quickly, this talk is on-line, with notes, so you can revisit during and after this conference.

Simply go to my GitHub page, or follow me on Twitter where I'll tweet a link to the talk slides.

Why machine learning in the browser?

Privacy
Low latency
Offline
Power efficient
Direct access to sensor data

Why is machine learning in the browser exciting?

Running machine learning algorithms in the browser allows for localized model training and prediction/classification. I don't need to decouple these two aspects: training and prediction.

Meaning, in practice, for particular types of problems, I do not need dedicated infrastructure or processes/threads for training and separate infrastructure for prediction.

Not only does this stand in contrast to traditional "big data" architectures, but this also stands in notable contrast to environments such as Jupyter notebooks, which effectively make the browser a glorified RPC client and require a backend server architecture to actually receive and execute commands.

Why is this distinction important? For the following reasons...

Privacy. Running machine learning algorithms in browser environments allows data to stay on-device. For example, health and fitness trackers, such as the Apple Watch, now have APIs which allow you to access heart beat data. By running incremental machine learning algorithms on-device, I can train a model (i.e., learn a user's "normal" heart beat pattern) and then detect when a heart beat, or set of heart beats, no longer fits this pattern. In this scenario, I never have to send this data to remote servers.

Because I don't have to send data to remote servers, analysis has low latency, works offline, and can be more power efficient.

Finally, as analysis can occur on-device (or using newer buzzword terminology, at the "edge"), we can have direct access to device sensor data, which removes the need for often complex device data serialization and de-serialization logic.

Example Datasets

Mouse/cursor movements
Scrolling
Clicks
Sensors
Monitoring

Use Cases

Forecasting
Anomalies
Clustering

What can machine learning in browser environments allow you to do?

The short answer is most everything you can do in non-browser environments. The main exception being the batch analysis of data of sufficient scale to be impractical for a single device.

As particularly concerns browser environments...

For the UI interaction data we discussed in the previous slide, such as cursor movement and scrolling, we can generate a prediction as to what resource a user will most likely need next, allowing us to create what would feel like a faster and more responsive UI.

One example I have seen in a real-world application is tracking cursor movement and, based on (x,y) coordinates over time, training a model to predict which button a user will click next, causing the desired resource to be fetched before a user actually clicks the button, and thereby leading to a more instantaneous experience.

Another classic use case is anomaly detection, such as detecting a malfunctioning system or fraudulent activity. In this classification task, we want to detect when a datum, or set of datums, is different than the rest.

The sooner we are able to classify new data as "anomalous", the sooner we can fix a potential problem.

A third use case is clustering, which is the process of assigning groups.

As an example, we could collect device performance metrics and identify different application "states", such as resource intensive, idle, et cetera.

The number of states and how frequently they are occupied could be informative for on-device resource planning and optimization.

Why JavaScript?

Myths

Performance
Incompatibility

The first myth is poor performance. As part of our work on stdlib, we have written and run the benchmarks. You can run them yourself. They are publicly available.

JavaScript environments are just as fast as, and more often than not, faster than, Python and easily faster than R.

Modern JavaScript environments are highly optimized and continually improving. With WebAssembly and Node.js native add-ons, reaching near-native speed in JavaScript environments is readily achievable.

The second myth is that JavaScript is somehow incompatible with mathematical computation.

The argument in support of this myth typically goes something like single-threaded, something, something, floating-point, something, something, 64-bit integers.

What is clear about the people making this argument is that they have not used other languages for scientific computing and machine learning, because many of the arguments used against JavaScript apply equally to other languages used for mathematical computation.

People can, and, more importantly, do write robust and performant mathematical code in JavaScript.

Personally, I can point to stdlib and the fact that we've implemented literally thousands of mathematical functions in JavaScript and have not encountered any overwhelming issues due to the language itself.

This said, yes, some languages have syntactical features more amenable to terser code (e.g., operator overloading), but the lack of these features does not preclude math algorithms from being implemented.

In fact, e.g., C suffers from similar operator overloading limitations and no one who believes the "JavaScript cannot do math" myth seems to believe the same about C.

In short, many of those who say math cannot be done in JavaScript seem to have various preconceptions which are not grounded in reality and most likely have never written mathematical libraries.

The primary reason why people do not currently do mathematical computation in JavaScript (and, by association, browser environments) is that other ecosystems already have a critical mass of libraries and frameworks for doing mathematical computation.

The issue is not one of technical limitations, but one of community support--a problem that myself and colleagues are working to address with stdlib.

Examples

Anomaly Detection

Clustering

Regression

Classification

Libraries and Frameworks

Observable

The first is Observable, a reactive notebook environment which exclusively leverages the web platform.

Similar to Jupyter notebooks, one can use Observable to create interactive notebooks which interleave prose and code, aiding exploration and analysis.

To showcase a few examples...

The first of which is a notebook which explores techniques for visualizing complex functions.

In this notebook, the author mixes prose and code to demonstrate visualization techniques. What makes Observable particularly compelling is that one is able to freely use all the technologies associated with the web platform. In this case, the author showcases how to use WebGL to generate stunning visualization of complex functions with interactive elements.

The next notebook explores chaotic systems.

In this notebook, the author is exploring how to reason about and model chaotic systems. Again, similar to other notebooks, we see the mixing of prose and code, coupled with interactivity, allowing the reader to better understand what is chaos and how can we reason about it.

The last notebook allows you to better reason about the US Federal Budget, by mapping budget expenditures to equivalent amounts in your monthly budget.

For those familiar with the work of Brett Victor, we can see that Observable provides an environment and framework for creating explorable explanations.

In fact, this is one of the advantages of Observable when compared to other notebook environments, such as Jupyter. Observable, being a "reactive" environment, supporting an out-of-order execution model, lends itself to a tighter integration between analysis and exploration and creative coding.

This tighter integration allows developers and analysts alike to more powerfully and expressively probe and interact with both their data and the algorithms which operate on that data (as we saw in the real-time machine learning notebooks we saw earlier).

Tensorflow.js

Predicting Strikes

Another library is tensorflow.js, a machine learning library being actively developed by a team within Google Brain.

Tensorflow.js aims to bring the power of Tensorflow to JavaScript environments, allowing you to train and deploy machine learning models in web browsers and Node.js.

(...explore tensorflow examples--posenet and pacman--on the tensorflow.js website...)

A last tensorflow.js example is an Observable notebook for training a model on MLB strike data and then using the trained model to predict strikes.

(...watch the live demo...)

What is important to note about this notebook is (1) all model training and evaluation happens entirely on the client. No servers needed.

And (2) neural networks are often treated as a black box, things which are hard to understand and reason about. By moving machine learning from traditional environments, such as R and Python, to the browser, we are able to tighten the feedback loop to visualize how an algorithm, even a neural network black box, learns in real-time, allowing us to explore and probe how, in a sense, an algorithm "thinks".

And thus, we should not underestimate the importance of browser-based machine learning as an important pedagogical device.

Apache Arrow

Large Datasets

The last library I want to highlight is Apache Arrow.

Apache Arrow specifies a standardized language-independent columnar memory format for flat and hierarchical data, organized for efficient analytic operations on modern hardware.

One of the main goals of Apache Arrow is to provide a common data format which can be used across environments and language, thus avoiding data serialization and deserialization costs.

To demonstrate using Apache Arrow in browser environments, we can open another Observable notebook which showcases how to use Apache Arrow with large datasets.

In this notebook, we can readily load and manipulate a few hundred thousand records--in this case, Chicago crime statistics--all within the browser environment.

For those who are unimpressed and consider a few hundred thousand records to be "tiny", keep in mind two things: (1) when performing exploratory data analysis on large datasets, doing so on an entire dataset is impractical; rather, one commonly performs exploratory data analysis on a "representative" sample.

(2) in theory, while a browser does have memory limitations, it does also have access to close to half a user's hard drive. By appropriately leveraging in-browser databases and stream APIs, one can, under certain circumstances, readily analyze many gigabytes of data, entirely within a browser environment.

Web Standards

WebAssembly

A portable compilation target for the web

Allows running languages other than JavaScript within browser environments

C/C++ → IR → wasm → x86/ARM

Modern compilers, such as LLVM, are comprised of two components: a frontend compiler, which takes a higher level language like C and compiles it to an intermediate representation, and a backend compiler which takes an intermediate representation and compiles it to machine-specific instructions.

Accordingly, in a modern compiler pipeline, WebAssembly (abbreviated: wasm) resides after the intermediate representation.

In the shown pipeline, I begin with input source files. A frontend compiler compiles those source files to an intermediate representation.

A backend compiler takes the intermediate representation and compiles to WebAssembly.

The WebAssembly is subsequently passed to a JavaScript engine, either loaded over HTTP in a browser or read from the filesystem in Node.js.

The JavaScript engine then translates the WebAssembly to machine code specific to a host platform.

Two Formats

Text Format


(module
  (type $0 (func (param i32 i32) (result i32)))
  (export "add" $add)
  (func $add (type $0) (param $var$0 i32) (param $var$1 i32) (result i32)
    (i32.add
      (get_local $var$0)
      (get_local $var$1)
    )
  )
)

Value Types

i32
f32
i64
f64

Binary Encoding


00 61 73 6d 01 00 00 00  04 74 79 70 65 87 80 80  |.asm.....type...|
80 00 01 40 02 01 01 01  01 08 66 75 6e 63 74 69  |...@......functi|
6f 6e 82 80 80 80 00 01  00 06 6d 65 6d 6f 72 79  |on........memory|
85 80 80 80 00 80 02 80  02 01 06 65 78 70 6f 72  |...........expor|
74 86 80 80 80 00 01 00  03 61 64 64 04 63 6f 64  |t........add.cod|
65 8c 80 80 80 00 01 86  80 80 80 00 00 14 00 14  |e...............|
01 40 04 6e 61 6d 65 86  80 80 80 00 01 03 61 64  |.@.name.......ad|
64 00                                             |d.|

Memory Access

i32.load8_s (signed)
i32.load8_u (unsigned)
i32.load16_s
i32.load16_u
i32.load
i64.load8_s
i64.load8_u
i64.load16_s
i64.load16_u
i64.load32_s
i64.load32_u

i64.load
f32.load
f64.load
i32.store8
i32.store16
i32.store
i64.store8
i64.store16
i64.store32
i64.store
f32.store

f64.store

Control Constructs

nop
block
loop
if
else
br
br_if
br_table
return
end

Operators

i32.add
i32.sub
i32.mul
i32.div_s
i32.div_u
i32.rem_s
i32.rem_u
i32.and
...many more

Advantages

Compact
Parsing
Typed
Optimization
Deoptimization
Lower-level
GC
Performance

WebAssembly has several stated advantages...

First, the binary format is compact, which means fewer bytes must be sent across a network and faster load times.
Next, because the binary format is structured, having a defined layout, module loaders need to only perform a single-pass in order to parse an encoded module into an AST in preparation for translating to machine code. The advantage of only requiring a single-pass is that modules can be instantiated faster compared to a module written in vanilla JavaScript.
Third, WebAssembly is strongly typed, which means more efficient serialization and, again, fewer bytes sent across a network.
Next, because WebAssembly is strongly typed, compilers are able to perform ahead-of-time optimizations. This is in contrast to JavaScript, for instance, which first must be compiled and monitored to determine if particular functions are running "hot".

Once a function is "hot", the function is sent to an optimizing compiler which makes optimistic assumptions about input value types and code paths, essentially creating an optimized version of the "hot" function.

If a function receives an unexpected input value type, the optimized function is de-optimized and the cycle repeats indefinitely or until a function is put in "deoptimization hell".

So instead of runtime optimization, with WebAssembly, we can perform the optimization an optimizing compiler does before ever running in a JavaScript runtime.
Next, because WebAssembly is strongly typed, we are able to avoid de-optimizing cycles as the optimization/deoptimization loop is no longer needed: input and output value types are defined ahead-of-time and not something a runtime compiler must empirically discover.
Another advantage is that WebAssembly is lower-level, which means that WebAssembly is easier to translate to efficient and optimized machine instructions, which means faster execution.
Next, WebAssembly does not currently come with a garbage collector, which means that WebAssembly modules are responsible for manually managing memory. This is useful as this allows control over when memory is allocated and deallocated, as you might want to during "deadtime", i.e., when an application is running idle.

On the flip side, the lack of GC also means that languages which depend on a GC cannot be easily compiled to WebAssembly (e.g., Python, et al).
If we combine all of these advantages, WebAssembly promises, for certain applications, better performance compared to JavaScript.


// File: dasum.c
#include <math.h>

double c_dasum( const int N, const double *X, const int stride ) {
    double sum;
    int m;
    int n;
    int i;

    sum = 0.0;
    if ( N <= 0 || stride <= 0 ) {
        return sum;
    }
    // If the stride is equal to `1`, use unrolled loops...
    if ( stride == 1 ) {
        m = N % 6;

        // If we have a remainder, run a clean-up loop...
        if ( m > 0 ) {
            for ( i = 0; i < m; i++ ) {
                sum += fabs( X[i] );
            }
        }
        if ( N < 6 ) {
            return sum;
        }
        for ( i = m; i < N; i += 6 ) {
            sum += fabs( X[i] ) + fabs( X[i+1] ) + fabs( X[i+2] ) + fabs( X[i+3] ) + fabs( X[i+4] ) + fabs( X[i+5] );
        }
        return sum;
    }
    n = N * stride;
    for ( i = 0; i < n; i += stride ) {
        sum += fabs( X[i] );
    }
    return sum;
}

Length	JavaScript	wasm	Native	Perf
10	22,438,020	18,226,375	7,084,870	2.57x
100	4,350,384	6,428,586	6,428,626	1.0x
1,000	481,417	997,234	3,289,090	0.30x
10,000	28,186	110,540	355,172	0.31x
100,000	1,617	11,157	30,058	0.37x
1,000,000	153	979	1,850	0.53x

Web Standards

BigInt
Value Types

Tips and Tricks

Avoid Built-ins
Read the Source!
Data Structures

ndarray
circular buffers
trees

Algorithms

So...tips and tricks. The following tips are generally applicable regardless of whether a machine learning algorithm is written and used in JavaScript.

The first tip, which is perhaps most applicable to JavaScript, is to avoid built-in mathematical functions (i.e., those mathematical functions which are defined by the ECMAScript standard and part of JavaScript's built-in standard library).

For a variety of historical reasons, the built-in implementations are ill-defined (allowing browser vendors to make trade-offs between speed and accuracy) and commonly have bugs.

Since one cannot specify the exact environment version in which browser-based machine learning algorithms will run (i.e., your users may have browsers spanning from the ancient to the most recent, with everything in between), if you want to ensure reproducibility of even the most basic mathematical operations, use community libraries, such as stdlib.

Second, the ecosystem for browser-based numerical, scientific, and machine learning libraries is in significant flux, with no clear "winner" among many contenders.

Accordingly, in order to ensure that you use quality implementations, you currently cannot rely on proxies for assessing quality, such as stars and downloads.

Especially within the JavaScript community, libraries and frameworks are born and die every day, with significant hype-driven herding propelling library adoption.

The most reliable approach for assessing whether to use a library is by reading. the. source.

Next, while true in general, but especially for machine learning, what makes algorithms performant are two things.

The first is using the right data structure.

One such data structure is n-dimensional arrays (ndarrays), which are single-segment contiguous blocks of memory. These data structures allow for more efficient cache optimization.

Another common data structure for real-time machine learning algorithms is a circular buffer. While the textbook definition is simple, these need to be implemented carefully in order to avoid poor memory management, especially when implementing them in JavaScript.

Certain machine learning algorithms, and, in particular, real-time algorithms, require specialized tree data structures. One such algorithm is quantile approximation.

The second is using the right algorithm.

One example where using the right algorithm is critical is, again, quantile approximation. A naive approach would require storing all data in memory and sorting the data each time a new data arrives.

A better approach is use an approximate method which uses a tree data structure and an acceptable error rate.

In batch analysis, especially for one-off analyses, we can be okay using naive algorithms or less efficient data structures; however, in the context of real-time statistical analysis and machine learning within web applications, this is not viable.

Conclusions

JavaScript
Data Structures
Algorithms
Get Involved!

There are 4 points I want you to remember from this talk...

First, JavaScript is perfectly suitable for mathematical computation and machine learning. And not only is machine learning in JavaScript and browser environments possible, but doing so introduces new types of machine learning applications, which offer better data privacy, better performance, and better resource utilization. In the words of Brendan Eich, "Always bet on JavaScript".
Second, machine learning algorithms, especially real-time machine learning algorithms, require using the right data structure, regardless of what language they are implemented in.
Third, machine learning algorithms require using the right algorithm.
Last, get involved! People are building the future of machine learning on the web, and we need people like you to continue making that future possible. That means contributing to open-source libraries, writing Observable notebooks to showcase new and interesting machine learning applications, and getting your companies to help sponsor, either through developer time or funding, machine learning development for the web.

Thank you!

https://github.com/stdlib-js/stdlib
https://www.patreon.com/athan

Appendix

Machine Learning

Models

$$y = a_nx_n + a_{n-1}x_{n-1} + \cdots + a_0x_0 + b$$

To describe those patterns we want to find, we formulate and train models.

A model is a mathematical formulation summarizing the nature of, and describing the relationship between, data variables.

Models serve as the statistical foundation for machine learning.

In order for machine learning algorithms to find patterns in data, we must "train" (or "teach") machine learning algorithms as to what those patterns are.

In a sense, machine learning algorithms "learn" the models used to describe particular patterns. That learning often comes in the form of learning specific values of coefficients within an equation.

In this equation, those coefficients would be a_n, a_{n-1}, a_0, et cetera.

As a more concrete example...

What will be the temperature tomorrow?

$$t_{n+1} = t_{n}$$

$$t_{n+1} = \frac{1}{7} \sum_{i=n-6}^{n} t_i$$

$$t_{n+1} = \frac{1}{W} \sum_{i=n-W+1}^{n} t_i$$

...suppose we want to "predict" the temperature tomorrow. A naive approach would be to predict that the temperature tomorrow is whatever the temperature is today.

Our naive approach can be expressed mathematically as t_{n+1} = t_{n}, which is a way of saying that, for a given day n+1, the temperature should equal the temperature of the previous day. This equation is our model.

However, we might, perhaps rightly, believe that this naive approach might not be as accurate as we would like due to day-to-day temperature variability (i.e., noise).

For example, an anomalous weather pattern may lead to extreme variation, such as a very warm day followed by a very cold day, but, for most climates, such extreme variability would not be "normal".

So, one possible refinement would be to predict that the temperature tomorrow is the average temperature of the past, say, 7 days.

By taking the average, we will "smooth" out some of the day-to-day variability and hopefully have a more reliable estimate over the long term.

In other words, by using the average temperature of the previous 7 days to predict tomorrow's temperature, our predictions will be closer (i.e., have a smaller error), on average, to the actual temperature than had we used our naive model.

We can generalize our model by using the parameter W which represents the number of days we want to average over.

In this example, the "model" is the mathematical formula describing the computation of the average temperature. That model is "trained" by giving the model data (e.g., the temperature for each of the past 7 days). In this case, the output of the trained model is a single value, which we then use to "predict" tomorrow's temperature.

Training Algorithms

Batch: build a model from a "batch" of data
Incremental: continuously update a model as data arrives
Mini-batch: hybrid of batch and incremental training.

How we train machine learning algorithms comes in three varieties.

The first is "batch". Batch training means training a model over an entire dataset. In order to accommodate new data, we must re-train our model by performing batch training over the entire updated data set.

Many "big data"/map-reduce style algorithms (e.g., such as those run on Hadoop) are of this variety.

The second is "incremental". Incremental training means training a model incrementally, one datum at a time. Such an approach allows one to continuously update a model as data arrives, without having to re-train over the entire data set.

The third is mini-batch, which is a hybrid of batch and incremental. In this variety, we buffer data and train models in small batches.

The primary motivation for mini-batch is the ability to achieve some of the robustness of batch training with a reasonably close approximation of the immediacy of incremental training (i.e., mini-batch can achieve "near real-time").

Real-Time Machine Learning

I define real-time machine learning as the subset of machine learning algorithms which support incremental training. I.e., as a new datum arrives, I can update my model incrementally. Meaning, in order to generate a new prediction, I don't need to store and analyze all past prior events.

Commonly, perhaps due to marketing departments, you'll see machine learning approaches and technologies labeled as "real-time". These approaches are more accurately described as "near real-time", in which, due to distributed computing strategies and/or parallelization, they allow for re-training and analysis to be done more quickly than traditional batch analysis.

My definition excludes these near real-time approaches.

Why this limited definition? Because I find incremental machine learning algorithms particularly compelling, especially when used in browser environments.

Machine Learning in the Browser

Overview

Why machine learning in the browser?

Example Datasets

Use Cases

Why JavaScript?

Myths

Examples

Anomaly Detection

Clustering

Regression

Classification

Libraries and Frameworks

Observable

Tensorflow.js

Apache Arrow

Web Standards

WebAssembly

Two Formats

Text Format

Value Types

Binary Encoding

Memory Access

Control Constructs

Operators

Advantages

Web Standards

Tips and Tricks

Conclusions

Thank you!

Appendix

Machine Learning

Models

What will be the temperature tomorrow?

Training Algorithms

Real-Time Machine Learning

The End