All Questions
Tagged with data-stream or online-algorithms
239 questions
0
votes
0
answers
14
views
(Online) Multiple Testing with very low expected H1 proportion (very few discoveries)
It appears that most (online) FDR tests lose (almost all) of their power, as the non-null proportion of hypotheses tends to 0. Does controlling the FDR even make sense in those cases? Are there any ...
- 148
0
votes
0
answers
14
views
Lower bound for stochastic bandits with short horizons
I want to show that if the horizon $n$ is strictly less than the number of arms $k$ then every algorithm enjoys a regret of at least
$$
\frac{n(2k-n-1)}{2k}
$$
Now, Lattimore and Szepesvári start from ...
- 133
0
votes
0
answers
21
views
Lower bound for online binary decision making with expert advice
Suppose we want to make a sequence on $n$ binary decisions with advice from $k$ experts. We define the regret with respect to the best expert we get advice from. Now I want to prove that we are going ...
- 133
3
votes
1
answer
54
views
Exact regret of $\epsilon$-greedy algorithm for $k$-armed bandit
The $\epsilon$-greedy algorithm for $k$-armed bandit, tosses a coin with success probability $\epsilon$ at each round and does the following:
If not successful chooses the best arm till now, and
if ...
- 133
0
votes
0
answers
22
views
Regret bound of epsilon-greedy algorithm for multi-armed bandit problem
Consider $1$-subgaussian MAB with $n\geq 2$, consider the $\epsilon$-greedy algorithm: First choose each arm once and subsequently choose $A_t=\arg\max \hat \mu_i(t-1)$ with pr. $1-\epsilon_t$ and ...
2
votes
1
answer
99
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
2
votes
1
answer
73
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 ...
- 369
0
votes
0
answers
15
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
0
votes
0
answers
57
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
0
answers
24
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 ...
- 31
4
votes
1
answer
84
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 ...
- 141
1
vote
0
answers
52
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, ...
- 641
1
vote
0
answers
71
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 ...
- 91
5
votes
1
answer
788
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
1
answer
174
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
0
answers
20
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
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. ...
- 11
1
vote
1
answer
66
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
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.
...
0
votes
1
answer
81
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
2
votes
1
answer
59
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
3
votes
1
answer
38
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
33
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
5
votes
2
answers
157
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 ...
- 175
0
votes
1
answer
130
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 ...
2
votes
1
answer
47
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
881
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
57
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
280
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,571
1
vote
1
answer
386
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
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 ...
- 91
3
votes
3
answers
791
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
0
votes
1
answer
489
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 ...
- 243
3
votes
1
answer
653
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
0
answers
62
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
247
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
417
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
4
votes
1
answer
218
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
174
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
2
votes
1
answer
88
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 $...
- 151
1
vote
0
answers
24
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'...
- 4,129
6
votes
1
answer
246
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)...
- 667
2
votes
0
answers
99
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 ...
- 667
1
vote
0
answers
167
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
871
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
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,027
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,419
4
votes
1
answer
2k
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
2
votes
0
answers
41
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 ...
