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
0
votes
0
answers
20
views
The hunt for a 'nice' flexible distribution
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, ...
- 581
1
vote
0
answers
44
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 ...
- 43
4
votes
1
answer
369
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)$$
...
- 245
0
votes
0
answers
20
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 ...
- 81
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 ...
- 133
0
votes
0
answers
11
views
Significant difference detection on a stream of data
Let's there are 2 groups of user. Based on their query I return some search results to them (p1,p2,p3). The search results could vary based on either the group that user belongs to or some user ...
- 111
0
votes
0
answers
13
views
Regret for deterministic algorithm
I am learning the weighted majority algorithm in "foundation of machine learning" by Mohri. But I can not understand the conclusion from the book and other reference.
It has the statement
...
- 205
1
vote
0
answers
15
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
1
answer
40
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
0
votes
0
answers
23
views
error bound for semi-online Learning problem
I want to solve the following problem:
Consider the noise-free classification setup. Let $\mathcal{F}$ denote an infinite class of (binary) classifiers with finite
VC dimension $d$. Let $f* ∈ \...
- 1
0
votes
0
answers
46
views
What are the advantages of model drift vs concept drift in online learning?
Let's say I have a simple linear predictor model and I want to update my model to adapt to the changes that have happened in the environment.
I mainly have two tools to detect dynamic changes:
Model ...
- 115
0
votes
0
answers
34
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.
...
0
votes
1
answer
33
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
0
votes
0
answers
79
views
Can I use the raw output of a model as input to the same model?
I would like to train a machine learning model where the training data represents points along a path/trajectory in an environment for a robot to follow. Once trained, the model is responsible for ...
0
votes
0
answers
12
views
How to ensure sampling quantity from stream of items while sampling based on risk
Assume that there is a process where items pass a decision point where a decision can be made to audit/inspect the item (or not). Once the item passes that point in the process it can't be retrieved ...
- 61
2
votes
1
answer
41
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
0
votes
0
answers
22
views
Radius of Cluster for DenStream algorithm on Normalised Data Points
I am trying to implement a clustering algorithm that uses DenStream's method for calculating radius of a cluster using sqrt(|SS|/N - (|LS|/N)**2). However when implementing the algorithm, the value (...
3
votes
1
answer
33
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 ...
- 283
0
votes
0
answers
27
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
4
votes
2
answers
135
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 ...
- 65
0
votes
1
answer
81
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 ...
- 101
2
votes
1
answer
45
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
1
answer
491
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
2
votes
0
answers
53
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
2
votes
1
answer
163
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,521
1
vote
1
answer
224
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
3
votes
1
answer
1k
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 ...
- 43
3
votes
3
answers
560
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,504
0
votes
1
answer
367
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 ...
- 171
2
votes
1
answer
428
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, ...
- 247
1
vote
0
answers
58
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
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 ...
- 101
1
vote
1
answer
167
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
2
votes
0
answers
361
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 ...
- 323
4
votes
1
answer
191
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
3
votes
1
answer
110
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
1
vote
1
answer
80
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 $...
- 131
1
vote
0
answers
22
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'...
- 3,449
6
votes
1
answer
178
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)...
- 655
2
votes
0
answers
82
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 ...
- 655
1
vote
0
answers
113
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 ...
- 11
2
votes
0
answers
522
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$.
- 143
2
votes
1
answer
35
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 ...
- 887
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 ...
- 1,242
3
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 ...
- 131
2
votes
0
answers
32
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 ...
0
votes
1
answer
81
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
2
votes
1
answer
259
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 ...
- 887
1
vote
0
answers
42
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-...
- 743
0
votes
1
answer
63
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
- 319