search
LoginSignup
59

More than 5 years have passed since last update.

posted at

updated at

Organization

オンラインアルゴリズムで平均値の逐次計算

オンラインアルゴリズムとは、データが逐次的に入ってきた時にも計算できるアルゴリズムのことである。
データを全て見た上で計算するバッチ(オフライン)アルゴリズムと対比してこう呼ばれる。

オンラインアルゴリズムは、すべてのデータをメモリ上に保持しておくのが厳しいような大規模データを扱う場合などによく使われる。機械学習の文脈でよく見かけるかもしれない。機械学習の文脈だと割と理論的に難しい物が多いが、平均、分散、サンプリングなどは簡単なシステムを作るときにも割とよく使うので、データが逐次的に来ても処理が書けるようになっておくと幸せになれることもあるはず。

今回は、平均値の逐次計算についてだけやり方を書いておく。

平均値の逐次計算

averageを求めたい平均値、totalを今までに処理したデータの個数として、
以下の形で記述できるようにすることを目標とする。

ruby/python
average += x
total += y

もちろん、オンラインアルゴリズムとして成り立つためにはaverage *= zという形を目標にしても良いが、(相加)平均値の場合は上記の形ならば解が求まる。

まず、totalは回数を表すので、y = 1である。

次にaverageの方は自明ではないので、以下のように式展開して求める。
なお、ここでvalueは、新規の平均を求めたいデータの値である。

math
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)

を得る

プログラムに書く際の結果としては、

ruby/python
average += (value - average) / (total + 1)
total += 1

となる。ここで、

math
total[new] = total[old] + 1

を考慮すると、プログラム的には

ruby/python
total += 1
average += (value - average) / total

の方がかっこいいかもしれない。

具体例で検算

データが3つで、その値は

20 -> 30 -> 40 

となっていたとする。

この時、最終的な平均は

30

であり、その時々の平均は

20 -> 25 -> 30

と推移していれば良い。

実際にやってみる。

1回目

math
x = (20 - ?) / 1 = 20 - ?
average = ? + 20 - ? = 20

2回目

math
x = (30 - 20) / 2 = 5
average = 20 + 5 = 25

3回目

math
x = (40 - 25) / 3 = 5
average = 25 + 5 = 30

となり、うまくいっていることがわかる。

ちなみに、1回目の?はaverageの初期値で、どんな値が入っていても良い。
実際には0か、事前に平均値が推定できる場合はその推定値を入れておくと良い。

おまけ

分散をオンラインアルゴリズムにする際のヒント

math
V(X) = E(X*X) - E(X)*E(X)

を使う。ここでVは分散、Eは平均を表す。
つまり、データの2乗値の平均値を保持するようにすれば計算できる。

サンプリングをオンラインアルゴリズムにする際のヒント

例えば大量のデータから、1つだけ値をサンプリングしたいとき、
そのデータをsampled、これまでに見たデータの個数をtotalとする。

このとき、

  • 新しいデータdsampledにする確率を1 / (total+1)
  • これまでのsampledをそのまま使う確率をtotal / (total+1)

とすると均等な確率でサンプリングされた結果が求まる。

これを応用すれば、3つだけサンプルするといったことももちろん可能。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
59