2
$\begingroup$

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 its model. When it sees a new observation (or gets feedback that a previous prediction was violated) it updates its model without some large batch processing of data/observations it's already seen.

By simple, I'm not sure exactly what I mean. I mean fewest computational steps I suppose. or easiest to understand...

I thought perhaps some simplest recommender system would qualify as the simplest - hello world - version of online learning but I don't know for sure.

What would you say is the simplest online learning algorithm?

EDIT: someone suggested the averaging algorithm is the simplest possible online learning algorithm as it can be calculated incrementally (as long as you know the current average and number of observations). Allow me to make my question a little more clear. I want a model that learns, not a static algorithm. 'Average' is a calculation, it's an algorithm. A model, in this sense, is distinct from a static algorithm in that it has what you might call internal variables that change based upon what it has seen. It has an internal state. Without 'state', a "model" is just static calculations. There are no 'internal state' or 'hidden variables' or 'weights and biases' to the Averaging calculation. In essence, there is no learning. I know this kind of question is quite general and it's asked in layman terms which doesn't help it be specific. Thank you for your patience.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I don't think you are correct about averaging. The state at stage (observation) $i$ is $(n_i, S_i)$, where $n_i$ is the number of observations at stage $i$ and $S_i$ is the sum of the observations at stage $i$. The state evolves by $n_{i+1} = n_i + 1$, $S_{i+1} = S_i + X_i$, where $X_i$ is the $i^{th}$ observation. $\endgroup$
    – jbowman
    Commented Mar 9, 2020 at 20:59
  • $\begingroup$ @jbowman I stand corrected I guess. $\endgroup$
    – MetaStack
    Commented Mar 9, 2020 at 21:10
  • 3
    $\begingroup$ In the enlarged sense expressed in your edit, one of the simplest possible models is to store the value of the first observation and output that forever after. Because it truly depends on the observations, it "learns;" and under some very broad assumptions about the process, it can work better than any "static process" or procedure that does not respond to the observations at all. I hope this example illustrates why the question "simplest possible" is not likely to lead to interesting or useful answers. $\endgroup$
    – whuber ♦
    Commented Mar 10, 2020 at 10:51

1 Answer 1

Reset to default
4
$\begingroup$

You want to calculate the average height of persons. An online algorithm that implements this keeps track of the total height of the persons the algorithm has seen, and the number of persons the algorithm has seen. An update is achieved by adding to these totals, while the average height at any point can be calculated by dividing the total height by the number of people measured. This is a very simple online learning algorithm.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.