オンラインアルゴリズムとは、データが逐次的に入ってきた時にも計算できるアルゴリズムのことである。
データを全て見た上で計算するバッチ(オフライン)アルゴリズムと対比してこう呼ばれる。
オンラインアルゴリズムは、すべてのデータをメモリ上に保持しておくのが厳しいような大規模データを扱う場合などによく使われる。機械学習の文脈でよく見かけるかもしれない。機械学習の文脈だと割と理論的に難しい物が多いが、平均、分散、サンプリングなどは簡単なシステムを作るときにも割とよく使うので、データが逐次的に来ても処理が書けるようになっておくと幸せになれることもあるはず。
今回は、平均値の逐次計算についてだけやり方を書いておく。
平均値の逐次計算
averageを求めたい平均値、totalを今までに処理したデータの個数として、
以下の形で記述できるようにすることを目標とする。
average += x
total += y
もちろん、オンラインアルゴリズムとして成り立つためにはaverage *= zという形を目標にしても良いが、(相加)平均値の場合は上記の形ならば解が求まる。
まず、totalは回数を表すので、y = 1である。
次にaverageの方は自明ではないので、以下のように式展開して求める。
なお、ここでvalueは、新規の平均を求めたいデータの値である。
average[new] = (average[old] * total[old] + value) / (total[old] + 1)
average[new] = average[old] + x
より
average[old] + x = (average[old] * total[old] + value) / (total[old] + 1)
これを解くと
average[old] + average[old] * total[old] + x * (total[old]+1) = average[old] * total[old] + value
average[old] + x * (total[old]+1) = value
結果として
x = (value - average[old]) / (total[old] + 1)
を得る
プログラムに書く際の結果としては、
average += (value - average) / (total + 1)
total += 1
となる。ここで、
total[new] = total[old] + 1
を考慮すると、プログラム的には
total += 1
average += (value - average) / total
の方がかっこいいかもしれない。
具体例で検算
データが３つで、その値は
20 -> 30 -> 40
となっていたとする。
この時、最終的な平均は
30
であり、その時々の平均は
20 -> 25 -> 30
と推移していれば良い。
実際にやってみる。
１回目
x = (20 - ?) / 1 = 20 - ?
average = ? + 20 - ? = 20
２回目
x = (30 - 20) / 2 = 5
average = 20 + 5 = 25
３回目
x = (40 - 25) / 3 = 5
average = 25 + 5 = 30
となり、うまくいっていることがわかる。
ちなみに、１回目の?はaverageの初期値で、どんな値が入っていても良い。
実際には0か、事前に平均値が推定できる場合はその推定値を入れておくと良い。
おまけ
分散をオンラインアルゴリズムにする際のヒント
V(X) = E(X*X) - E(X)*E(X)
を使う。ここでVは分散、Eは平均を表す。
つまり、データの2乗値の平均値を保持するようにすれば計算できる。
サンプリングをオンラインアルゴリズムにする際のヒント
例えば大量のデータから、1つだけ値をサンプリングしたいとき、
そのデータをsampled、これまでに見たデータの個数をtotalとする。
このとき、
- 新しいデータ
dをsampledにする確率を1 / (total+1) - これまでの
sampledをそのまま使う確率をtotal / (total+1)
とすると均等な確率でサンプリングされた結果が求まる。
これを応用すれば、3つだけサンプルするといったことももちろん可能。