An online algorithm is an algorithm that can be calculated even when data comes in sequentially. This is called in contrast to the batch (offline) algorithm, which calculates after seeing all the data.
Online algorithms are often used when dealing with large amounts of data where it is difficult to keep all the data in memory. You may often see it in the context of machine learning. In the context of machine learning, there are many things that are theoretically difficult, but since averaging, variance, sampling, etc. are used relatively often when creating a simple system, processing can be written even if data comes sequentially. You may be happy if you become.
This time, I will write the method only for the sequential calculation of the mean value.
ʻAverage is the average value you want to find, total` is the number of data processed so far.
The goal is to be able to describe in the following form.
ruby/python
average += x
total += y
Of course, in order to be valid as an online algorithm, the form ʻaverage * = z` may be targeted, but in the case of the (arithmetic) average value, the solution can be obtained if the above form is used.
First, y = 1 because total represents the number of times.
Next, since ʻaverage` is not trivial, it is calculated by expanding the formula as follows. Here, value is a value of data for which a new average is to be obtained.
math
average[new] = (average[old] * total[old] + value) / (total[old] + 1)
average[new] = average[old] + x
Than
average[old] + x = (average[old] * total[old] + value) / (total[old] + 1)
If you solve this
average[old] + average[old] * total[old] + x * (total[old]+1) = average[old] * total[old] + value
average[old] + x * (total[old]+1) = value
as a result
x = (value - average[old]) / (total[old] + 1)
Get
As a result of writing in the program,
ruby/python
average += (value - average) / (total + 1)
total += 1
Will be. here,
math
total[new] = total[old] + 1
Considering that, programmatically
ruby/python
total += 1
average += (value - average) / total
May be cooler.
There are 3 data, and the value is
20 -> 30 -> 40
Suppose that it was.
At this time, the final average is
30
And the average at that time is
20 -> 25 -> 30
It suffices if it changes.
I will actually try it.
math
x = (20 - ?) / 1 = 20 - ?
average = ? + 20 - ? = 20
math
x = (30 - 20) / 2 = 5
average = 20 + 5 = 25
math
x = (40 - 25) / 3 = 5
average = 25 + 5 = 30
And you can see that it is working.
By the way, the first ? Is the initial value of average, and any value may be entered.
Actually, it is 0, or if the average value can be estimated in advance, it is better to enter the estimated value.
math
V(X) = E(X*X) - E(X)*E(X)
use. Here, V represents the variance and ʻE` represents the mean.
In other words, it can be calculated by holding the average value of the squared values of the data.
For example, when you want to sample only one value from a large amount of data,
Let that data be sampled, and let the number of data seen so far be total.
At this time,
--The probability that the new data d will be sampled is 1 / (total + 1)
--The probability of using the previous sampled as it is istotal / (total + 1)
Then, the sampled result can be obtained with equal probability.
Of course, if you apply this, you can sample only three.
Recommended Posts