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
0 votes
1 answer
19 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 ...
user avatar
  • 101
1 vote
1 answer
28 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?
user avatar
  • 11
0 votes
0 answers
8 views

Prediction with probability of a match

I would like to understand better what solutions are available from existing ML frameworks to achieve the following. I have set of "sentences" (its not NLP task but is easier to explain). ...
user avatar
1 vote
1 answer
20 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 ...
user avatar
2 votes
0 answers
15 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 ...
user avatar
  • 21
1 vote
1 answer
49 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 ...
user avatar
1 vote
1 answer
37 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 ...
user avatar
  • 123
0 votes
0 answers
20 views

How do you estimate the mode of a histogram with logarithmic bin width?

For the purpose of estimating the median and other quantiles, I summarize samples in a histogram whose bins grow logarithmically in width. For example, to guarantee a 1% worst case absolute relative ...
user avatar
3 votes
1 answer
216 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 ...
user avatar
  • 23
3 votes
3 answers
148 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 ...
user avatar
  • 1,388
0 votes
1 answer
60 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 ...
user avatar
  • 189
2 votes
1 answer
100 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, ...
user avatar
  • 217
1 vote
0 answers
26 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 ...
user avatar
0 votes
0 answers
34 views

Confidence/Prediction Interval in Recursive Least Square(RLS)

I am trying to implement RLS based on the given algorithm: https://en.wikipedia.org/wiki/Recursive_least_squares_filter The missing piece is how to update residual mean and variance for a given data ...
user avatar
  • 111
0 votes
0 answers
27 views

Online Batch Estimation of low-dimensional covariance matrix

The problem - I'm getting data in a batch manner. So in every timestep $i$ I get data as $$B_i = \{x_1, x_2 ..., x_m\}$$ ,where $m$ is batch size. Every batch does not cover whole population, but only ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
  • 101
1 vote
1 answer
57 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)?...
user avatar
0 votes
0 answers
18 views

Are there other reasons to do offline training than computational efficiency in machine learning?

I am reading about online versus offline algorithms, and I cannot think of any machine learning algorithm that is truly offline. I mean, yes, neural networks are, for computational reasons, trained ...
user avatar
  • 112
2 votes
0 answers
170 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 ...
user avatar
  • 173
4 votes
1 answer
92 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 ...
user avatar
  • 180
3 votes
1 answer
64 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 ...
user avatar
  • 180
1 vote
1 answer
60 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 $...
user avatar
  • 131
0 votes
0 answers
5 views

How can I evaluate smoothed offline predictions for later real-time use without future bias?

I have a system that makes predictions in real time. Whenever the system encounters a positive label, the process must be stopped. This, however, means that noisy predictions, such as the one shown at ...
user avatar
1 vote
0 answers
14 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'...
user avatar
  • 3,187
0 votes
0 answers
13 views

Is the training time of online transfer learning much less than that of offline transfer learning?

I have a question. Is the training time of online transfer learning much less than that of offline transfer learning?
user avatar
0 votes
0 answers
15 views

Existing solutions/approaches to this streaming classification problem?

I'm wondering if the following problem setup is one that can be tackled using models from existing libraries, e.g. scikit-learn, Keras, etc. I don't know if this problem is common/trivial or, at the ...
user avatar
  • 101
5 votes
1 answer
112 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)...
user avatar
1 vote
0 answers
42 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 ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
1 vote
0 answers
146 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$.
user avatar
1 vote
0 answers
8 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 ...
user avatar
  • 643
0 votes
0 answers
666 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 ...
user avatar
  • 1,180
2 votes
1 answer
441 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 ...
user avatar
  • 121
1 vote
0 answers
17 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 ...
user avatar
0 votes
1 answer
60 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 ...
user avatar
  • 1
2 votes
1 answer
146 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 ...
user avatar
  • 643
1 vote
0 answers
23 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-...
user avatar
  • 731
0 votes
1 answer
57 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
user avatar
0 votes
1 answer
73 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 ...
user avatar
  • 87
1 vote
1 answer
106 views

Does this exist: Recursive Least Absolute Deviation-Regression?

For least squares regression there exists the Recursive Least Squares algorithm which allows to find the least squares solution online. Does something similar exist for Least Absolute Deviation ...
user avatar
  • 131
5 votes
2 answers
164 views

What are good resources for online time series forecasting? [closed]

I have a project in which I'm given the state of the order book for a stock every 1ms, and I need to predict the return on the stock 2 minutes in the future using this information. I haven't been able ...
3 votes
1 answer
121 views

Recursive ARIMA

I am trying to implement recursive ARIMA that would just update the parameters with new data point, rather than re-estimate them from scratch, without taking into account the previous model. What I ...
user avatar
  • 51
3 votes
1 answer
194 views

What is the best strategy for the simplified version of the multi-armed bandit?

Consider a simplified version of the multi-armed bandit problem, where: like in the standard multi-armed bandit: when you pull the lever of 1 bandit you win/lose some amount from that bandit ...
user avatar
  • 1,048
0 votes
1 answer
27 views

How can I compute standard deviation without k observations

For a given variable $X$, we compute the standard deviation. Now I removed $k$ observations from $X_n$ and I would like to compute the new standard deviation $\sigma_{(k)}$ using $\sigma_{n}$. I ...
user avatar
  • 133
1 vote
1 answer
135 views

Doubt about definition of Regret in Online convex optimization setting

In online convex optimization, the regret of an algorithm $\mathcal{A}$ as defined in Introduction to Online Convex Optimization (Page 5) is: $$ regret_T(\mathcal{A}) = \sup_{\{f_1,...,f_T\}} \sum_{t=...
user avatar
3 votes
0 answers
217 views

Continuous time series classification with lstm in Keras?

I have been researching time series classification with LSTM. I've seen examples where they provide continuous predictions, i.e. the prediction is updated at each time step. Is it possible to train a ...
user avatar
  • 1,119
2 votes
1 answer
67 views

what is the simplest possible online learning model / algorithm

Let me define my vernacular here: I'm looking to understand what the simplest online learning algorithm is. By 'online' I just mean it doesn't have to see all the past observations in order to update ...
user avatar
  • 453
1 vote
2 answers
26 views

What’s the difference between online machine learning and software that updates the model automatically and reestimates when new data are entered?

Is online machine learning basically a software that updates the model automatically every time the data changes? So instead of having to run the same line of code again by a person and again by ...
user avatar
3 votes
1 answer
477 views

Efficient online (rolling window) estimation of a GARCH model

I have a time series $x_t$ of length $n$. I would like to model it using rolling window approach with window length (width) $w$: window $1$: $x_1,\dots,x_w$, window $2$: $x_2,\dots,x_{w+1}$, $\dots$, ...
user avatar
4 votes
1 answer
163 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 ...
user avatar
  • 511

1
2 3 4 5