Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
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 ...
Sprotte's user avatar
  • 123
2 votes
1 answer
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 ...
Foobar's user avatar
  • 359
0 votes
0 answers
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 ...
ummg's user avatar
  • 145
0 votes
0 answers
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 ...
Vassily's user avatar
  • 141
1 vote
0 answers
23 views

Residuals in Online Gradient Descent

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 ...
sebHan1234's user avatar
4 votes
1 answer
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 ...
PaulWH's user avatar
  • 161
1 vote
0 answers
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, ...
Tom Chen's user avatar
  • 621
1 vote
0 answers
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 ...
litmus's user avatar
  • 83
5 votes
1 answer
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)$$ ...
z611's user avatar
  • 255
1 vote
1 answer
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 ...
zxzx179's user avatar
  • 93
1 vote
0 answers
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 ...
causative's user avatar
  • 133
1 vote
0 answers
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. ...
Qazaz's user avatar
  • 11
1 vote
1 answer
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 ...
Bach05's user avatar
  • 11
0 votes
0 answers
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. ...
sam chakerian's user avatar
0 votes
1 answer
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 ...
Rowing0914's user avatar
2 votes
1 answer
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 ...
V.V.'s user avatar
  • 21
3 votes
1 answer
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 ...
candied_orange's user avatar
0 votes
0 answers
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 ...
causative's user avatar
  • 133
5 votes
2 answers
156 views

Doubt about level of confidence

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 ...
miticollo's user avatar
  • 175
0 votes
1 answer
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 ...
Constantin Müller's user avatar
2 votes
1 answer
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?
Zuz's user avatar
  • 21
1 vote
1 answer
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 ...
John Doe's user avatar
2 votes
0 answers
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 ...
Ali's user avatar
  • 21
2 votes
1 answer
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 ...
Vladimir Belik's user avatar
1 vote
1 answer
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 ...
Jag's user avatar
  • 123
4 votes
1 answer
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 ...
litmus's user avatar
  • 83
3 votes
3 answers
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 ...
Lucas Morin's user avatar
  • 1,665
0 votes
1 answer
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 ...
Mas A's user avatar
  • 223
3 votes
1 answer
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, ...
Shew's user avatar
  • 297
1 vote
0 answers
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 ...
Elise Le's user avatar
0 votes
0 answers
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 ...
newleaf's user avatar
  • 101
1 vote
1 answer
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)?...
Alex Craft's user avatar
2 votes
0 answers
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 ...
Amhs_11's user avatar
  • 333
4 votes
1 answer
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 ...
Oly's user avatar
  • 180
3 votes
1 answer
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 ...
Oly's user avatar
  • 180
2 votes
1 answer
87 views

Evaluating Data Stream Clustering Algorithms

I am quite confused regarding the evaluation of data stream clustering algorithms. Assuming I have some data stream (finite for now) $(X_1,X_2,...,X_n)$ with labels $(Z_1,Z_2,...,Z_n)$, where each $...
Dinari's user avatar
  • 151
1 vote
0 answers
23 views

Trainable decision tree? A decision tree that relearns decision boundaries based on new examples?

Trainable decision tree? A decision tree that relearns decision boundaries based on new examples? Does this exist? Application: I can draw good boundaries on the data I have based on intuition, but it'...
mavavilj's user avatar
  • 4,119
6 votes
1 answer
215 views

Using Gaussian Processes to learn a function online

I would like to approximate a function $f:\mathbb{R} \to \mathbb{R}_+$ based on a set of samples. I obtain these samples online (i.e. sequentially in time). That is, at time $t$ I receive $(x_t, f(x_t)...
Physics_Student's user avatar
2 votes
0 answers
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 ...
Physics_Student's user avatar
1 vote
0 answers
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 ...
user1467068's user avatar
2 votes
0 answers
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$.
Mistakamikaze's user avatar
2 votes
1 answer
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 ...
etang's user avatar
  • 1,007
1 vote
0 answers
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 ...
NoVariation's user avatar
  • 1,399
4 votes
1 answer
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 ...
mr_js's user avatar
  • 141
2 votes
0 answers
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 ...
Stratos supports the strike's user avatar
0 votes
1 answer
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 ...
MoYa's user avatar
  • 1
2 votes
1 answer
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 ...
etang's user avatar
  • 1,007
1 vote
0 answers
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-...
pikachu's user avatar
  • 753
0 votes
1 answer
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
SS Varshini's user avatar
0 votes
1 answer
104 views

Forecasting in time series (ARMA, GARCH etc.)

I've read here https://otexts.com/fpp2/arima-forecasting.html how we do forecasting in time series models like the ARMA model, but I'm wondering if we recalculate estimates of parameters of our model ...
P Lrc's user avatar
  • 97

1
2 3 4 5