Real-Time Machine Learning in JavaScript

Athan Reines | @kgryte | @stdlibjs

Overview

Intro
Motivation
JavaScript
Examples
Tips and Tricks
Conclusions

The talk overview is as follows...

First, I will introduce machine learning and define some foundational concepts.
Next, I will motivate why you should care about machine learning and, in particular, real-time machine learning.
Then, I will discuss machine learning as it applies to JavaScript.
I will then walk through a few examples showcasing real-time machine learning in JavaScript.
After which, I will offer some tips and tricks when applying real-time machine learning algorithms.
And finally, I will offer some conclusions and additional resources you can use to get started using JavaScript for real-time machine learning.

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.

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 = t_{n-1}$

$t_n = \frac{1}{7} \sum_{i=n-7}^{n-1} t_i$

$t_n = \frac{1}{W} \sum_{i=n-W}^{n-1} 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 = t_{n-1}, which is a way of saying that, for a given day n, 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

This brings us to real-time machine learning.

For the purposes of this talk, 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 JavaScript environments, such as web browsers and Node.js.

Why incremental algorithms?

Privacy
Low latency
Offline
Power efficient
Direct access to sensor data

Why are incremental algorithms exciting?

Incremental machine learning algorithms allow for model training and prediction/classification to happen concurrently. 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.

Often, incremental algorithms have low memory footprints, making them suitable for IoT and other resource limited devices.

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

Privacy. Incremental machine learning algorithms allow data to stay on-device. For example, the Apple Watch has an API which allows you to access heart beat data. With incremental machine learning, 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 have direct access to all device sensor data, which removes the need for often complex device data serialization and de-serialization logic.

Example Data Streams

Mouse/cursor movements
Scrolling
Clicks
Sensors
Monitoring

Use Cases

Forecasting
Anomalies
Clustering

What can real-time machine learning allow you to do?

We have already discussed one use case: forecasting (prediction). The naive model we formulated earlier which involved computing an average in order to forecast tomorrow's temperature can be formulated as an incremental algorithm.

Each day we can record the temperature, use that temperature to update our model, and make a forecast for the next day based on our updated model.

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 you are able to classify new data as "anomalous", the sooner you 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, such as CPU utilization and memory usage, 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 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 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

Tips and Tricks

Simulation
Exploratory Data Analysis
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 is to use simulation to generate synthetic datasets to run against real-time machine learning algorithms so you better understand an algorithm's capabilities and limitations.

Next, always, always, always perform exploratory data analysis.

This means exploring your data by plotting and performing basic analyses in order to get a "feel" for your data and to test any basic assumptions (e.g., as we did when testing that the network sensor data is normally distributed).

Next, while true in general, but especially for real-time 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 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 real-time algorithms require specialized tree data structures, such as quantile approximation.

The second is using the right algorithm.

One example where using the right algorithm is critical is 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 and Node.js server applications, this is not viable.

Conclusions

JavaScript
Data Structures
Algorithms

Thank you!

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