動的計画法
先に「これってDPマッチングとかもそのうち説明せんとあかんのか？」とか書いときました。まぁ必要っぽいです。
んで、前回は似顔絵とか書きました。で、輪郭とか似たパターンを引っぱってくるとか書いときました。でも、そうとう個性的な顔でないと、顔の輪郭とかそう個人差はないんですよね。なので、もしパターンのXが似てるとなったら、そのXをデフォルメしたX'とかに紐づけておいて、似顔絵としてはX'を使うとかが現実的になります。デフォルメされたX'に直接アクセスしようとしたって、まぁ、たぶん無理なので。まぁ、やろうと思えばできないでもないですが。
で、似たXとかを引っぱってくるのあたり。大雑把に言えばパターンマッチングとかが必要になってきます。
パターンマッチングの超基礎にあるのが「動的計画法」と呼ばれるものです。「DP(Dynamic Programming)マッチング」とも呼ばれます。ちょい手が入って、別の名前がついているものもありますが、DPマッチングを知っていると、そういうのの理解も早くなります。まぁ知ってて損はないものです。
DPマッチングはきちんと数学的に定式化されたりしてます。でも、それをそのまま読むとかは案外面倒だったりします。あと、同じことを書いてあるのに、本によってはまったく別物に見えるというようなこともあります。なので、ここでは定式化は無視して具体例で考えます。
あ、言葉の科学でなんでDPマッチングを扱うかというと、音声認識の超基礎としてDPマッチングを使うからです。ビタビというような名前のアルゴリズムもありますが、DPマッチングの変形と読めます。なので、DPマッチングは古いながらも息の長いアルゴリズムです。
まぁ、きちんと定式化しない分、これそのものの応用範囲は狭くなるかもしれませんが、実際に必要になった時には、頑張って勉強してください。
ところで、プログラムで何かの問題を解こうという場合、「分割統治」という考え方が重要になります。問題を分割して、それぞれについて解を得るというような方法です。この考え方自体は、プログラミングにおいて極めて重要なものです。プログラミングに興味がある方は、DPマッチングとは別に、その考え方を体得しとくことをお勧めします。
さて、定式化は無視すると書きましたので、まずA1-A2-A3-A4とB1-B2-B3-B4という文字列みたいなものがあったとしましょう。文字列というかA1なんかが、ある配列とかと考えてもらうと、その方がいいかもしれません。
さて、DPマッチングの第一段階では、例えばA1とB1とかの距離を求めます。これ、A1に対して、B1, B2, B3, B4との距離を原理的には全て求めます。
A1とかが、A1[0], A1[1], A1[2]という配列だとします。その場合A1とB1の距離は、(A1[0]-B1[0])^2+(A1[1]-B1[1])^2+(A1[2]-B1[2])^2と求めます。ここで "^2" は二乗を意味します。なんで二乗するかというと、(A1[0]-B1[0])の値として正の値の場合もあれば、負の値の場合もあります。二乗せずに足すと、本来結構距離があるはずなのに、正の値と負の値で打ち消したりして小さな値になってしまうかもしれないからです。
次の段階としてはA1からA4、B1からB4のあいだでどういう経路を取ったら、距離が最小の経路になるかを計算します。
ここで、これまでの経路の距離の和の最小のものをg(x)と書くとします。もちろんg(x)の初期値、たとえばg(0)なんかの初期値は0とします。で、今注目している、たとえばA3とB3とかの距離をf(x)と書くとします。f(A3,B3)とかでもいいです。これが第一段階で求めておいた個別の距離とします。
g(0)は0なのですが、A1の方を基準(?)にして、f(A1,B1), f(A1, B2), f(A1, B3), f(A1, B4)の中から最小値を求めます。そうするとg(1)=g(0)+min(f(A1, *))てな感じになります。ここだとg(0), g(1)と書いてますが、このg(x)も実際にはA1-A2-A3-A4とB1-B2-B3-B4から作られる平面の、各格子にgの値を埋めます。
んで、ここが重要なのですが、g(0)+min(f(A1, *))のmin(f(A1, *))を得らぶ時、g(0)から、平面だったら上を選んだのか、右上を選んだのか、右を選んだのかとかの経路も一緒に記録しておきます。
この第二段階で、A1-B1からA4-B4に至る平面の全ての格子点にg(x)が得られてます。
そして第三段階では、最小距離となる経路を求めます。まぁ、A4-B4の格子点でのg(x)が、A1-B1からA4-B4の最小距離となってますが、それが得られる経路ですね。第三段階では、その経路を求めます。A4-B4のg(x)を求めた時、その一つ手前からは上を選んだのか、右上を選んだのか、右を選んだのかの記録が取ってあるわけです。なので、A4-B4からその経路を逆に辿ると、どういう経路で最小距離が得られたのかがわかるわけです。経路が不要であれば、第三段階は無視してもいいです。
あ、えと、上とか右とか書いてますが、これは単純な経路でして、他にも目的に合った経路を使ったりします。
さて、今A系列とB系列の最小距離を求めました。これはこれでいろいろ使えます。で、その他に、A系列とB系列だけでなく、C系列、D系列……の最小距離を求めて、じゃぁA系列はB系列とかのどれに近いのかを求めるという使い方もあります。たとえば、A系列が「こんにちは」という音声の何かの配列だとして、B系列以降に「こんにちは」、「こんばんは」、「わたし」、「なまえ」……とかとかがあるとすると、うまく行けばA系列は「こんにちは」であるという結果が得られるわけです。
一応、かなりいいかげんなレベルでこれを書くと、こうなります。
格子点の距離を埋める。
g(i) = g(i-1) + min(f(i)) これを繰り返す
min(g(I)) を求める。IはA4の4とかです。
そうなる経路を逆算する
これ、真面目にやるとたとえばA系列の流さがnだとすると、それを基準にしてn^2とかの計算が必要になります。ですが、解こうという問題にもよりますが、そんなに真面目に計算しなくてもかまわない場合があります。例えばA1とB4とかは実際には考えなくてもいいというような場合があるわけです。その場合には、そのあたりは計算しなくていいということにして、計算の量を減らすこともできます。
えーと、これだとたとえば音声認識だと「こんにちは」とかの認識ができるだけです。「わたしのなまえはみやざわです」というような文も、これでやっても構わないのですが、だいたいの場合はこれを一括でマッチングすると不便になります。DPマッチングだけで「わたしのなまえはみやざわです」とかをやろうとすると2段階DPというような方法があります。これは……説明が面倒だ…… まぁたとえば単語のマッチング結果を、A1-B1とかの距離と同じように扱って、もういっちょDPマッチングをするような方法です。これだと任意の単語の任意の並びが、理想としては得られます。
あ、「こんにちは」とかじゃなくて、「あ」、「い」、「う」とかを基準にやってもいいんじゃないかと思われるかと思います。まぁ理想としてはそうなんですが。でも「こんにちは」とかの方が、普通は「あ」とかよりも長いですよね。こういうのはだいたい、短かいものよりも長いものでやった方が、確からしさは大きくなるってのは想像できると思います。もっとも、「わたしは」の「は」なんかは「は」でマッチングできると嬉しいので、それでのマッチングもするこたするわけですが。
今どきはこういうDPマッチングそのものではなく、別の方法の中に実質的にはDPマッチングが入ってるとか、場合によっては使ってないとかありますが。興味があったり、必要があったりする人は、きちんと勉強してください。
