All Questions
Tagged with online-algorithms algorithms
15 questions
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 ...
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
4
votes
1
answer
357
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 ...
- 541
1
vote
1
answer
330
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 ...
- 143
1
vote
1
answer
90
views
References for learning about online random forests
I am new to concepts of random forest. Can someone provide relevant sites where I could get learn more about using random forests to learn incoming data like an online algorithm?
0
votes
1
answer
46
views
Algorithm to find centroid of historical datapoints without storing historical data
Is there an online learning algorithm for clustering that doesn't require storing historical data?
- 311
1
vote
0
answers
460
views
Online linear regression. Possible or not? [duplicate]
I don't have a strong background in statistics, but I'm a programmer and needed to implement some statistical aggregate functions in the DSL I'm writing. This DSL processes events in an online fashion,...
- 111
4
votes
1
answer
1k
views
Basic questions about stochastic gradient descent / Robbins and Monro algorithm
I have a LOT of time series observations and I would like to estimate a simple AR(1) model
$$
y_t =c+ \phi y_{t-1}+ \varepsilon_t \qquad \varepsilon_t \sim \text{N}(0, \sigma^{2})
$$
with parameters ...
- 41
1
vote
1
answer
2k
views
Single-pass algorithm for kurtosis
Here is a simple test I've run on MATLAB to check the validity of a single pass (online) algorithm for computing $3$rd moment and $4$th moment.
...
- 55
3
votes
1
answer
120
views
Algorithms/methods for detecting regime changes in data rates
I'm looking at multiple live data streams which I process on a daily basis and would like to monitor in real time.
The way I did it at first was to introduce a somewhat arbitrary upper bound for ...
- 1,003
6
votes
2
answers
1k
views
On-line detection of over-fitting in neural networks
As we train a neural network, we have access to the error-rate (both on training, and test patterns). What are standard techniques to use this information to stop the learning as quickly as possible ...
- 2,729
4
votes
2
answers
2k
views
Online fitting for normal distributions
I was wondering if there exist efficient online or dynamic algorithm for fitting a normal distribution to data as it comes in. I am interested in two variants:
The algorithm is fed data points one at ...
- 2,729
67
votes
6
answers
22k
views
Efficient online linear regression
I'm analysing some data where I would like to perform ordinary linear regression, however this is not possible as I am dealing with an on-line setting with a continuous stream of input data (which ...
- 1,035
17
votes
5
answers
5k
views
Online algorithm for mean absolute deviation and large data set
I have a little problem that is making me freaking out.
I have to write procedure for an online acquisition process of a multivariate time series.
At every time interval (for example 1 second), I get ...
- 2,001
57
votes
10
answers
32k
views
What is a good algorithm for estimating the median of a huge read-once data set? [duplicate]
I'm looking for a good algorithm (meaning minimal computation, minimal storage requirements) to estimate the median of a data set that is too large to store, such that each value can only be read once ...
- 1,882