Questions tagged [online-algorithms]

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

234 questions
Filter by
Sorted by
Tagged with
87 views

Online updating of $t$-value for simple linear regression

Suppose I am regressing a dependent variable $y$ onto a single independent variable $x$ using a simple ordinary least squares regression model $y = \beta_1 x + \beta_0$. Suppose I start with $n$ data ...
• 123
54 views

What is the intuition behind the single-pass algorithm (Welford's method) for the corrected sum of squares?

The corrected sum of squares is the sum of squares of the deviations of a set of values about its mean. $$S = \sum_{i=1}^k\space\space(x_i - \bar x)^2$$ We can calculate the mean in a streaming ...
• 359
13 views

Online mixture inference; better alternatives than windowed EM?

I have an online Gaussian mixture estimation problem that I would appreciate some input on. To be more precise, I have a stream of scalar observations $x_1, x_2, \dotsc$ arriving over time which are ...
• 145
43 views

Online learning with strongly convex loss w.r.t. L1 norm

Consider an online learning problem where the loss function observed by the algorithm at time $t$ can be written as $$f_t(\lambda) = \langle V_t, w \rangle + \mu \sum \lambda_i \log \lambda_i$$ for ...
• 141
1 vote
23 views

Does anyone know if online linear learning assumes white noise to the residuals? My thought process is that serial correlation can arise due to the fact that the fit at time t uses the information ...
81 views

Incrementally Computing $\Sigma_t v_t$ Without Storing $x_i$, $v_i$, or $\Sigma_t$

Motivation: I have a discussion with friends many days ago, at that time I think this problem is very easy so we directly skip, later I realize I cannot solve it XD. The problem is: Given a sequence ...
• 161
1 vote
50 views

The hunt for a 'nice' flexible distribution [duplicate]

Background Suppose I have data $\mathcal{D}_1, \cdots, \mathcal{D}_n$ with each $\mathcal{D}_i$ containing $m$ observations $X_{i1}, \cdots, X_{im}$; these observations are of unknown distribution, ...
• 621
1 vote
56 views

Improve HMM state estimation in latest data

I have a time-series dataset that is poisson-distributed, where each day I get a new additional datapoint. If I input all the data into a HMM (I am using code I found from hmmlearn in python) it does ...
• 83
660 views

Linear regression on a large dataset

I want to run linear regression on a dataset who is too large to be loaded into memory. I intend to simply calculate $$\left(\sum_{i=1}^n x_ix_i^T\right)^{-1} \cdot \left(\sum_{i=1}^n x_iy_i\right)$$ ...
• 255
1 vote
108 views

Understanding the regret bound of stochastic bandit vs. adversarial bandit

I am a beginner at MAB. One thing that puzzles me these days: The regret of the UCB policy (and Thompson Sampling with no prior) for stochastic bandit is $\sqrt{KT\ln T}$, but the regret of the EXP3 ...
• 93
1 vote
18 views

Moving-optimum optimization

Are there ready-made algorithms to solve the following problem? At each time step $t$ the agent chooses a value $x_t$. There is a function $f(x, t)$ that gives the error on timestep $t$ after ...
• 133
1 vote
19 views

Online learning with random action set?

Suppose I have an online bayesian linear regression problem for which I can updated the posterior distribution of parameters. Using this posterior, I want to make a point forecast by sampling from it. ...
• 11
1 vote
58 views

Online Estimation of a Joint Distribution from batches of data

I want to implement an algorithm for the online estimation of a joint probability distribution from a sequence of mini batches sampled from the real distribution. The distribution is discrete and non ...
• 11
36 views

Online r2 calculation does not match sklearn r2 calculation (python)

I am trying to replicate sklearn's linear regression coefficients and r2 score with an online calculation (so that it updates with each additional point of data). Starting with this code here. ...
75 views

Big-O of Upperbound on the Regret of Exp3

I'm having difficulty understanding how to compute Big-O for the upper bound on the regret in Exp3 algorithm. I think the actual algorithm isn't quite important for my question but since I couldn't ...
• 173
51 views

Bernoulli parameter estimation after every sample received

I have a pretty simply-looking question on the parameter estimation. hope you can help me. I have a biased coin and I want to decide if the probability of head $p$ is bigger or smaller than known ...
• 21
37 views

Name for incrementally calculating a mean

If μ = 4 and n = 2 and suddenly I have a new datum of 22 I can add 1 to n and recalculate μ as (4*2+22)/3 = 10 without even looking back at the old data. This can be used as an optimization to reduce ...
29 views

Which optimizers are suitable for online learning for an agent?

An agent is exploring an unknown world. The agent uses a neural network to make predictions about the next time step. We want to use some form of gradient descent optimizer to tune the network ...
• 133
156 views

I run 100 simulations with CI at 99% and different seeds. For each simulation I created a report that contains different performance indexes (means) with their CI. However, I noticed that one index ...
• 175
115 views

Time series model in production - Re-train on the fly as as batch process?

Let's say I've a time series of phone calls per day over the last three years. I could train a model using exponential smoothing (e.g. HoltWinters) for predicting the future amount of phone calls per ...
46 views

Strategy when introducing a new arm

Let's say we have a bandit with two arms, and we know that one arm has a reward probability 0.5 and the other is unknown. How do we create a strategy to maximise the reward?
• 21
1 vote
726 views

Online clustering approach

Is there any "online" clustering approach? I mean that the procedure should be like this: Can be fitted with the initial portion of data. Can be updated with the upcoming batch of data. The ...
• 99
55 views

How are online reinforcement learning algorithms evaluated?

In online reinforcement learning (RL), we have a behaviour policy. Let this policy be an epsilon-greedy policy. Suppose that I run Q-learning for some episodes and evaluated it by plotting "sum ...
• 21
217 views

Changepoints in linear regression (NOT piecewise regression)

I have two variables, X and Y, whose relationship can be described well by a linear regression. HOWEVER, this relationship changes every once in a while. It is not that the relationship changes ...
• 1,541
1 vote
350 views

Is there an incremental dimensionality reduction algorithm that can handle batch size less than number of components to be reduced?

I have a large dataset of patient data by hour. For example, given the shape as (hours, features), patient 1 data shape could be ...
• 123
2k views

Live peak / trough detection (data provided)

At the bottom of this question is the data of three time series in CSV-format. All are of same length and they all contain measurements of the same event "A". But each time series is using a ...
• 83
737 views

Running n-lag correlation matrix?

Working in python, I get data at regular interval. The data contains some features, $X_1,\dots,X_p$. I am trying to get an online algorithm to build correlation matrixes. The naive approach of keeping ...
• 1,665
458 views

Confusion about "online learning" and "data or class incremental learning"?

I saw there are some posts on stackexchange on the subject (example1, example2 and example3). However, in this paper, they use SGD as an online learning model. They state that The incremental ...
• 223
570 views

Difference between regret and pseudo-regret definitions

I am following the book Bandit Algorithms. In page 48, they introduces regret after $n$ rounds as $$\mathbf{R} = n\mu^\star - \mathbb{E}\Bigg[\sum_{t=1}^n \mathbf{X}_t\Bigg] \tag{1}$$ In page 55, ...
• 297
1 vote
61 views

Particle Swarm Optimization (PSO) for incremental/online learning

As stated in the title, is there a way to adapt PSO to an online scenario where new data samples arrive continuously? In more detail: suppose that I have a classifier with several parameters for which ...
• 87
25 views

problems while production the clustering results

I searched for clustering in production but do not find related practical answers. Is it possible to make the clustering code in production? Suppose I have a data set for 1M users with around 100 ...
• 101
1 vote
225 views

Incremental update of Normal Distribution

There's a price time series $\{p_{t}, t=1..n\}$. Is it possible to estimate Normal Distribution for every data point $N_{t}(\mu_{t}, \sigma_{t})$ efficiently (like incrementally or online calculation)?...
• 447
409 views

How to calculate the evaluation metrics on streaming data for online ML algorithms

I am working on a binary classification problem where I need to develop an online ML model that can work on streaming data. However, I am not sure how can I use the evaluation metrics for ...
• 333
213 views

Bandit-like setup but taking max reward over sequential choices

Similar to my other question Bandit-like setup but taking max reward over multiple heads?, I'm interested in situations like the Multi-Armed Bandit setup, except where the reward is aggregated a ...
• 180
133 views

Bandit-like setting with maximum reward over multiple arms?

If I have a process where I can evaluate one of a number of options per 'round', with variable reward, and I want to maximise reward over time, the multi-armed bandit literature has lots of useful ...
• 180
87 views

98 views

Probability Density Estimation vs Function Approximation [closed]

I have a function $f: \mathbb{R} \to \mathbb{R}_+$ and I would like to estimate it. The data pairs $\{(x_i, f(x_i))\}$ arrive at different times $t$. I have two questions: In this case, since the ...
1 vote
149 views

Sequential Bayesian Linear Regression with Diagonal Covariance

The standard update rules for a sequential Bayesian linear regression are well-known (heck, they're even on wikipedia: https://en.wikipedia.org/wiki/Bayesian_linear_regression). However, in large ...
765 views

Change in standard deviation when a value is removed

Let's say a list of numbers $L$ has standard deviation $S$. Is there a formula for finding $S$ if I remove an element $l$ from $L$? Assume we know the mean of both $L$ and $L - l$.
37 views

Online Tree Based Algorithms

Linear regression and logistic regression can do online training(i.e. continuous training as new data arrives) via stochastic gradient descent. Are there any tree based algorithms which can ...
• 1,007
1 vote
2k views

Online Algorithm Implementation for the Median [duplicate]

Context My question is related to the binmedian algorithm which is suggested in this post and its implementation originally in C and its adaptation in python. My issue with these algorithms is that ...
• 1,399
1k views

How to calculate the running mean absolute deviation

I wish to calculate the running mean absolute deviation (MAD) without storing the previous n data points. This calculation is for a continuous stream of data, i.e. infinite length. I am trying to ...
• 141
36 views

Online learning problem formulation

I have been wondering about the usual formulation of online machine learning problems, as written in Wikipedia or in other papers I've read. What bugs me is the fact that this problem is written as ...
90 views

Classification of Imbalanced and Streaming Time Series Data

I have a question about classification of time series. Data has two features and I want to classify it into 5 classes. We have a stream of data and new data is generated every 5 seconds. Moreover in ...
• 1
400 views

Are Bandit Algorithms Considered as Online Algorithms?

I think bandit algorithms(such as multi-armed bandit algorithms) can be considered as online algorithms because they make decision and update the parameters as data arrives. However, I can't find any ...
• 1,007
1 vote
44 views

Which metrics should be used in preprocessing in continual learning?

So my idea is to train an LSTM - autoencoder for anomaly detection by continual learning, i.e., I want to update the model after each 10 time steps. Firstly I will train it on source data, then re-...
• 753
67 views

online machine learning vs traditional machine learning

Considering batch size=1 implies online machine learning?? What is the difference between an online machine learning model and traditional machine learning model with batch size=1
• 329