Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

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

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

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

平均値の逐次計算

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つだけサンプルするといったことももちろん可能。

awakia
検索とか推薦とかやってきたエンジニア。早稲田の山名研出身。大学院の頃、論文を書こうとしない僕を見かねた教授に、北京のMSRAに追放されるが3ヶ月後無事帰還。 大学を卒業後、エンジニアのブラックホールとの別名を持つGoogleに吸収されそうになるが1年2ヶ月後無事生還。 現在は、Wantedly(https://www.wantedly.com/ )の4番目のエージェントとして救出活動に専念。
http://awakia-n.hatenablog.com/
wantedly
「シゴトでココロオドル」ためのビジネスSNS「Wantedly」の開発・運営をしています。
https://wantedlyinc.com/ja/presentations
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした