Questions tagged [online]

Online algorithms refer to computations that are performed iteratively, with data arriving during the computation. For questions focusing on the Internet, please use the "internet" tag.

Filter by
Sorted by
Tagged with
0
votes
0answers
18 views

Online estimation of a quadratic form

I have a functional form $y = x^T Q x + b^T x + c$, with $Q, b, c$ to be estimated, $x \in \mathbb{R}^n$ and $n$ varies around 10-20, depending on the problem. $x$ is sampled from a known Gaussian ...
1
vote
0answers
24 views

Does this exist: Recursive Least Absolute Deviation-Regression?

For least squares regression there exists the Recursive Least Squares algorithm which allows to find the least squares solution online. Does something similar exist for Least Absolute Deviation ...
5
votes
2answers
100 views

What are good resources for online time series forecasting? [closed]

I have a project in which I'm given the state of the order book for a stock every 1ms, and I need to predict the return on the stock 2 minutes in the future using this information. I haven't been able ...
3
votes
1answer
31 views

Recursive ARIMA

I am trying to implement recursive ARIMA that would just update the parameters with new data point, rather than re-estimate them from scratch, without taking into account the previous model. What I ...
2
votes
1answer
66 views

What is the best strategy for the simplified version of the multi-armed bandit?

Consider a simplified version of the multi-armed bandit problem, where: like in the standard multi-armed bandit: when you pull the lever of 1 bandit you win/lose some amount from that bandit ...
0
votes
0answers
17 views

How do you find the median of a long list of unsorted integers that can only be loaded in the memory in batches? [duplicate]

Say we have a really long list of integers and they can only be loaded in batches/chunks in the memory. Also, the numbers are random and not sorted. How do you find the grand median of all the ...
0
votes
1answer
21 views

How can I compute standard deviation without k observations

For a given variable $X$, we compute the standard deviation. Now I removed $k$ observations from $X_n$ and I would like to compute the new standard deviation $\sigma_{(k)}$ using $\sigma_{n}$. I ...
1
vote
0answers
10 views

Analyzing the effect of terms on the continuation of an on-line discussion

The Data I am analyzing approximately 200 million online "threaded" posts (think USENET NEWS, Google Groups, Reddit, etc.). The posts have a tree structure like so: ...
0
votes
0answers
8 views

Calculate standard deviation of a set of numbers in one cycle over the numbers without knowing average in advance [duplicate]

I have an set of numbers that I need to calculate standard deviation of. I want to do it in a single cycle over that set and I don't know the average of the array beforehand. I need it for my program: ...
1
vote
1answer
59 views

Doubt about definition of Regret in Online convex optimization setting

In online convex optimization, the regret of an algorithm $\mathcal{A}$ as defined in Introduction to Online Convex Optimization (Page 5) is: $$ regret_T(\mathcal{A}) = \sup_{\{f_1,...,f_T\}} \sum_{t=...
0
votes
0answers
15 views

How to update K-means online once offline trained?

Problem statement: If we segment customers of a retail company, in let's say "k" clusters using k-means, and name them meaningfully based on their summary statistics, then how to update it later on, ...
1
vote
1answer
36 views

what is the simplest possible online learning model / algorithm

Let me define my vernacular here: I'm looking to understand what the simplest online learning algorithm is. By 'online' I just mean it doesn't have to see all the past observations in order to update ...
0
votes
0answers
19 views

Understanding research paper (online PCA)

I was reading this paper - https://pdfs.semanticscholar.org/efc7/ba57ece148f9f311a7e49639b69f70878489.pdf and got really confused by algorithm 2. Basically the paper suggests that we can input some ...
1
vote
2answers
25 views

What’s the difference between online machine learning and software that updates the model automatically and reestimates when new data are entered?

Is online machine learning basically a software that updates the model automatically every time the data changes? So instead of having to run the same line of code again by a person and again by ...
0
votes
0answers
14 views

Mistake bound in halving with prior?

Some of the answers I found where - Question: What if we had a "prior" p on the different functions in C? Can we make at most lg(1/p_f) mistakes, where f is the target function? Ans: Sure, ...
0
votes
0answers
13 views

Expert selection criteria in Randomized Weighted Majority Algorithm?

The RWMA states that - In each round 't' we choose one of the experts at random (with probability proportional to his/ her weight) and follow his / her advice. So we can say that at each round, ...
0
votes
0answers
76 views

Efficient online (rolling window) estimation of a GARCH model

I have a time series $x_t$ of length $n$. I would like to model it using rolling window approach with window length (width) $w$: window $1$: $x_1,\dots,x_w$, window $2$: $x_2,\dots,x_{w+1}$, $\dots$, ...
3
votes
1answer
53 views

Reducing the dataset size for KDE

I have GPS data, so 2 coordinates, and I want to estimate the busiest places (i.e. the places with more data points). However, I have a lot of points: currently ~4 million for 12 days, and I will be ...
0
votes
0answers
16 views

Can Incremental/Online Learning be Implemented for Custom Word Embeddings

I'm currently working with a neural network (in Keras) that predicts classes from text using custom word embeddings. It's worked well until now, but has to be retrained frequently on new data. The ...
1
vote
1answer
333 views

How come Mini Batch K means partial_fit method be useful for stream clustering?

Currently, I'm studying the advance in cluster analysis regarding stream clustering. I ended up assessing Mini batch K means because of some comments I read on the Internet, like the following one: ...
0
votes
0answers
25 views

Batch computation vs online computation

In short, could you explain in which situations online computation is better than batch computation? (I am currently reading a paper (https://arxiv.org/abs/1003.0120) about offline policy evaluation ...
1
vote
1answer
39 views

Online Optimization - Regret in Absolute Error

In the online convex optimization literature static regret is defined as $\sum_{t=1}^{T}\left(f_t\left(x_t\right)-f_t\left(x^*\right)\right)$ where $x^*=\arg min_{x\in\mathcal{X}}\sum_{t=1}^{T}f_t\...
-2
votes
1answer
84 views

General process of training a Neural Network [closed]

I have a very broad question about the general procedure of training a NN. I am not too concerned about the precise algorithms in this question at the moment. But there is one thing bothering me. ...
0
votes
1answer
39 views

What is the cumulants of a whole data in terms of the cumulants of its parts?

I have around 8 billion data points, and I need to calculate the distribution and the cumulants of this distribution. However, due to technical restrictions, and time constraints, I can only ...
2
votes
1answer
97 views

Can you use stochastic gradient descent with a multinomial likelihood?

I have a multinomial likelihood of the form: $$P(\underline n|\underline x) = N!\prod_{i=1}^M \frac{f_i(\underline x)^{n_i}}{n_i!}$$ where $\underline x$ is a vector of parameters, $f_i(\underline x)...
2
votes
2answers
124 views

Online update of Pearson coefficient

Suppose I have an online stream of data points $x_i,y_i$, where $i=1,2,\dots$. I want to compute the Pearson correlation coefficient between the vectors $\vec x$ and $\vec y$. But here is the catch. ...
1
vote
1answer
79 views

Resources for Non-Bayesian Online Change-point Detection

I am interested in learning about the fundamentals of on-line change point detection. I am specifically not interested in the Bayesian methods. The only solid resource / review / survey I could find ...
1
vote
1answer
32 views

Testing methodology

I recently built a simple feed forward NN to predict daily demand (48 output neutrons, representing half hours) based upon 32 input features. I tested the performance by firstly doing 10 fold cross ...
2
votes
1answer
34 views

Is there a goodness of fit metric that can be computed online with $O(1)$ memory?

Say I have two random streams of two dimensional data. I want to measure how closely their underlying PDF's match. My current method is to estimate the PDF's by accumulating the samples online in a ...
0
votes
0answers
29 views

Dynamic Calculation of Variance after removing an observation

I know that there are formulas for calculating variance in dynamic fashions. I have also seen formulas for calculating rolling variances assuming you know what number is leaving and entering the ...
15
votes
2answers
684 views

Recursively updating the MLE as new observations stream in

General Question Say we have iid data $x_1$, $x_2$, ... $\sim f(x\,|\,\boldsymbol{\theta})$ streaming in. We want to recursively compute the maximum likelihood estimate of $\boldsymbol{\theta}$. That ...
3
votes
1answer
161 views

what is the diffrences between online and one pass learning?

as long as I know, online learning takes actions at each time step (for each data), and one-pass algorithm just can see each data once. I already read Wikipedia: about streaming algorithms. These ...
1
vote
1answer
62 views

How to use/treat a hidden layer as the new target to predict in a neural network?

Let's suppose I have a neural network with one hidden layer. During training, for a given pair of (input, target), I want to perform several iterations, such that the first iteration would be trying ...
1
vote
0answers
37 views

Clarification regarding proof of convergence of online EM

Online EM algorithm was proposed by Olivier Cappé in Link to paper. They assume that complete data likelihood $f(x ; \theta)$ belongs to exponential family i.e. $f(x;\theta) = h(x) \exp \left\lbrace ...
2
votes
1answer
144 views

Tuning distance threshold in online clustering

In online clustering there are approaches where a threshold $r$ on the distance to the nearest cluster is used to determine whether a new data point should be associated to an existing cluster or ...
2
votes
0answers
50 views

What is the relationship between Online Learning and Statistical Learning?

Online Learning also known as Online Convex Opimization has famous algorithms like Follow-the-Leader and Online Gradient Descent (See OCO Book) Now stoastic programming has algorithms like Sample ...
1
vote
2answers
63 views

on-line regression with 1 output [closed]

I have 12 input variables from sensor (IMU) to predict 1 output (Speed of a boat) variable. Is it possible to use regression (or something else?) in this case where it is a continuous data stream from ...
4
votes
2answers
129 views

Practical realities of updating a trained model with new data

In my day to day work, I train models on data using R packages that have no extension for Bayesian priors. I will generally have a large dataset to start off with, and add new data as needed. Any ...
0
votes
0answers
22 views

Are there specific Machine Learning Algorithms that are more indicated for Real Time Analytics?

As the title suggests, I am wondering if there are specific ML algorithms that are more suitable for real time learning. In my case, I am working on deploying a stacking algorithm on Spark Streaming ...
2
votes
2answers
239 views

Regret in online learning

In online learning/online convex optimization, it's often the case that you compare your algorithm against the best action in hindsight (i.e., from https://people.cs.umass.edu/~akshay/courses/cs690m/...
1
vote
0answers
28 views

Transforming an echo state network to online training

I have recently become interested in echo state networks, I've been using the simple introduction to ESNs here https://mantas.info/wp/wp-content/uploads/simple_esn/minimalESN.py by Dr. Mantas ...
1
vote
0answers
28 views

What is the effect of the use of online-learning algorithms on non streaming data?

I am wondering what the effects of using a passive-aggressive classifier instead of something like a SVM classifier on a non-streaming data would be. In other words, what are the general assumptions ...
0
votes
0answers
16 views

Recursive least square with incomplete data

If we have a system $\mathbf{Y}_t = \mathbf{A}_0 + \mathbf{v}_t$, in which $\mathbf{v}_t$ is the noise. Using the first $t$ samples, we can estimate $\mathbf{A}_0$ by the arithmetic (sample) mean, ...
3
votes
2answers
2k views

How to frequently update classification model with new training data?

How do I incorporate a new stream of data into my classification model? Do I have to retrain the model from the beginning every time I want to incorporate new data, or can I update the existing model ...
2
votes
0answers
45 views

Any previous work on online coordinate descent, where a new coordinate appears at each iteration?

I'd like to analyze the behavior of coordinate descent algorithms, where as a twist, at each iteration, a new variable appears. For example, if $T$ is my total number of iterations, then at iteration $...
1
vote
2answers
116 views

What test to use to find the probability of highest value?

If I have a vector of around 40 values each with a normally distributed error, is there an easy way to figure out the probability of each element being the element with maximal true value? For context,...
1
vote
0answers
31 views

Online estimation of drifting discrete probability

I recently come across (in a practical setting) to the following problem. Suppose I receive items from a finite set ,one at a time . At each moment one item is drawn independently from an unknown ...
1
vote
0answers
36 views

Performance of Hierarchical Temporal Memory on unsupervised online anomaly detection problems

I'm looking for an algorithm to detect anomalies in streaming data (server metrics). The detection needs to be near-real time and unsupervised (labeled data will never be available, unfortunately, and ...
1
vote
0answers
43 views

Adding new center in an RBF network without memorizing previous training examples

Suppose we train an RBF by minimizing the LSE on a couple of training points and we are doing it incrementally in an online fashion. So basically we update the QR factorization using e.g. Givens ...
1
vote
1answer
46 views

Algorithm for selecting largest possible value, when observing online sequence of unknown distribution?

I have been trying to devise an algorithm for a problem that's been bugging me for a while. For some weird reason I haven't been able to find any mention of this problem in the literature, so far. I ...