論理パズル(鳩ノ巣原理とハミング距離編)
この記事はpaiza Advent Calendar 2024の1日目の記事になります。
paizaの開発チームにはそれぞれにトリの名前がついていて、今期にはピジョン(ハト)チームが存在します。
(毎期ごとにトリが変わるので、ネタが尽きるかと思いきやまだやりくりできているようです)
だからというわけではないですが、鳩ノ巣原理(Pigeonhole principle)とその応用にまつわる話を紹介します。
想定読者
頭の体操がしたい人
数学の現実世界の応用例を知りたい人
検索技術に関心がある人
前半は誰にでもわかることですが、後半はデータベース(インデックス)の知識がないと難しいかもしれません。
鳩ノ巣原理とは
鳩ノ巣原理は数学の有名な原理です。
数学と言ってもそんなに難しくはありません。
以下のようなハトの巣(?)があったとして、ハトをもう1羽追加しようとするとどこかの巣に2羽以上ハトが入ることになります。
9個の巣に10羽以上のハトを入れようとすると、どこかの巣では必ず2羽以上のハトがいるというのがこの原理の主張です。(当たり前すぎて何が主張なのか逆にわからなくなります。)
もう少し別な考え方をすると9個の巣に8羽のハトをいれると必ずどこか1つの巣が空くことになります。
(今回の記事ではこっちの性質の理解が重要です。)
鳩ノ巣原理の一般化
ここからがやや話が難しくなります。
9個の巣という前提は変えず、23羽のハトを巣に収めていくとします。
もっとも混んでいる(ハト密度が高い)巣には少なくとも何羽のハトがいるでしょうか？
以下では巣にいるハトの羽数を横並びで表現します。
[3, 3, 3, 3, 3, 2, 2, 2, 2]という割り振りをすると、もっとも混んでいる巣には3羽いることになります。
[4, 4, 4, 4, 3, 1, 1, 1, 1]という割り振りをすると、もっとも混んでいる巣には4羽います。
[23, 0, 0, 0, 0, 0, 0, 0, 0]という割り振りだと、もっとも混んでいる巣には23羽います。
他にいろいろ試してみても、もっとも混んでいる巣には少なくとも3羽ハトがいることがわかります。
もう少し別の表現をすると、もっとも混んでいない(ハト密度が低い)巣には多くとも2羽以上しかはいっていないということもできます。
もしも一番混んでいない巣にハトが3羽以上いたとすると、少なくともハトが27羽が必要になるからです。
この当たり前でちょっとだけ小難しい話が何の役に立つのか、先に話をすすめてみましょう。
ハミング距離
ここではうってかわって、ハミング距離の話をします。
例えば[0,1,0,1]のような数のならびを(長さ4の)ビット列と呼ぶことにします。
ビット列Aをビット列Bにしようとしたときに何回2進数を反転(1を0に、0を1に)させるかを数えたものがハミング距離になります。
例えばビット列Aが[0,0,0,0]でビット列Bが[1,0,0,1]だとすると、Aの一番左と一番右のビットを反転させればBになるのでハミング距離は2になります。
Aが[0,1,0,1]でBが[1,0,1,0]なら4つのビットを全部反転する必要があるのでハミング距離は4です。
ハミング距離は2つのデータがどれだけ似ているか(類似性)を表しています。
類似データの探索
ここではデータベースにデータ(ビット列)が1億個あると仮定します。
その中からデータAとすごくよく似ているデータ、具体的にはハミング距離が1以下のデータを探索するにはどうすればいいでしょうか。
Aとデータベース内のデータのそれぞれについてハミング距離を1億回計算し、ハミング距離が1以下のものだけ抽出すればOKですが、類似データを検索するたびに毎回1億回の計算が必要になるとかなり遅い処理になってしまいます。
鳩ノ巣原理で高速化する
計算したいハミング距離が小さい場合、鳩ノ巣原理を応用し計算を高速化することができます。
ここでは実用性を踏まえてビット列の長さは64ビットとします。
例えばハミング距離が7以下のデータを計算したい場合、どのように考えるべきか。
64ビットのビット列を8ビット×8組に分け、それぞれの部分ビット列についてインデックスを事前計算します。
インデックスを作成する理由は部分ビット列が完全一致するデータを高速に抽出したいからです。(インデックスというものはそういうことができます。)
ハミング距離が7以下であるということは、64ビットあるうち、ビットが異なるものが多くても7個しかないということです。
つまり鳩ノ巣原理より、8組あるうちの最大7組はビットが異なる可能性がありますが、どれか1組については、Aの部分ビット列とデータベースの部分ビット列がが完全一致しなければならないということがわかります。
8個の巣(部分ビット列)に7個のハト(ビット反転)を入れるとどのようにハト(ビット反転)を配置しても必ず1個の巣はハト(ビット反転)がない＝完全一致する、最初の問題と同じ形式をしていますね。
言い換えると8組ある部分ビット列のいずれか1つが完全一致するデータに集中してハミング距離を計算すれば高速化できます。
以下はハミング距離7以下のデータを抽出するSQLの例です。(p1~p8のそれぞれに事前にインデックスを作成する)
SELECT *
FROM vectors
WHERE (p1=? OR p2=? OR p3=? OR p4=? OR p5=? OR p6=? OR p7=? OR p8=?) -- ここでインデックスを使う。この条件を満たさないものは鳩ノ巣原理よりハミング距離7以下になりえない。
AND BIT_COUNT(p1 ^ ?) + BIT_COUNT(p2 ^ ?) + BIT_COUNT(p3 ^ ?) + BIT_COUNT(p4 ^ ?) + BIT_COUNT(p5 ^ ?) + BIT_COUNT(p6 ^ ?) + BIT_COUNT(p7 ^ ?) + BIT_COUNT(p8 ^ ?) <= 7鳩の巣原理の一般化を応用する
(ここの章は論理パズルとしてかなり難しい割に実用性は低いので理解できなくてOKです。)
ハミング距離が15以下のデータを計算する場合は、どのように考えるべきか。
ビット列を4ビット×16組に分けて考えるのもありですが、そうすると新たなインデックスを作成する必要がでてきます。
鳩ノ巣原理の一般化の例を応用すれば実は8ビット×8組のデータを再利用できます
ハミング距離が15以下であるということは、鳩ノ巣原理の一般化を応用するといずれかの部分ビット列のハミング距離が必ず1より小さくなります。(＝8個の巣のいずれかは必ずハトが1羽以下になっている)
言い換えるとハミング距離が15以下ならば、Aの部分ビット列に加えてAの部分ビット列とのハミング距離が1となる8つの部分ビット列(計9個の部分ビット列)集合を考えた時に、その9つのデータのいずれかと完全一致する部分ビット列が8組のうちのいずれかに必ず存在します。
(こういうひねった表現になるのは完全一致検索できる形式に持ち込み、インデックスを活用するためなのですがいずれかという表現が2回表れていてかなり難しいです。)
ベクトルDB
昨今ではベクトルDBという新しいDBが大規模言語モデル(LLM)への注目とともに一般的になりつつあるようです。
それを使えば上記で行った近傍データ探索よりはるかに高度な検索が実施できるようです。(例えばembeddingという技法を使うと、言葉がベクトルデータに変換され、近傍データを探索すると類似した言葉を探せるといった対応関係があります。)
まとめ
今回の記事ではほんのり頭の体操をしつつ、RDBなどを用いて高速な類似ベクトル(データ)検索に活用できる話を紹介しました。
個人的にはこうした論証力が試されるような数学は好みなのと、どう考えても実用化できなさそうな鳩ノ巣原理が実は生かせるみたいな構図がいいと思っています。
参考文献
この記事は下記論文の要点を簡略化して抽出したものになります。(非常に丁寧な論証がなされています。)
https://arxiv.org/pdf/1307.2982
タイトル画像について
タイトル画像はハトではなくシマエナガくんになります。
それは私がシマエナガチームだからです。
おわり