Mac用プロットライブラリ-17「何をやっていたか思い出す」

ずいぶん前にたどり着いた、プロットライブラリでのはみ出し問題の解決法としての線形計画法のお勉強の続き。しばらくほったらかしにしていたので何をやっているのか忘れてしまった。がんばって思い出す。何を隠そう実は、「思い出す」ことは一番苦手な精神作業である。その逆は得意だけど。「思い出す」の逆って「忘れる」ではなくて「覚えない」なのか？ああ、書いててわからなくなる．．．

プロットライブラリのはみ出し問題

例えば座標軸

与えられたサイズのウィンドウの中に描かれる2次元のプロットで、例えばプロットオブジェクトの外に描かれる座標軸やそのラベルなどを描こうとするとき、それらを避けてその内部にプロット領域を設定する必要がある。座標軸の専用領域を先に確保すれば簡単だけど、そのためには座標軸オブジェクトを他のプロットオブジェクトと別扱いする必要がある。アルゴリズムとしてはその方が簡単だけど見通しは悪くなってデバグは難しくなる。そういうやり方はしたくない。座標軸も他のプロットオブジェクトと同じ扱いをしたい。

他にも似た問題

それ以外にも、文字列をプロット領域に描画することは、プロットしたポイントごとにラベルを貼りたい場合なんかとして普通にある。文字列の描画領域の大きさは当然読める大きさでなければならない。もっと言えば大宇宙の進化をシミュレートしたプロットの場合でも水素原子の電子雲のプロットの場合でも描かれる文字は標準で12ptでなければならない。それがプロット領域の端に描かれたときはみ出るかどうかは、描画領域に大きさと文字の大きさで決まってしまう。はみ出した場合、それが描画領域に収まるようにプロット領域の方を小さくしなければいけない。

座標系の階層化による一般化

最終的に描画される大きさが、例えば文字列なら12ptになるように大宇宙の場合には文字列の大きさをパーセクで、電子雲ならオングストロームで指定すればいいが、それをユーザにやらせるのは親切なライブラリとは言えないし、ライブラリ側でその指定をするにはもっと一般的な表現ができなければいけない。

こういった問題はまず座標系を、少なくとも

• プロット座標系
• 描画座標系（View座標系）

のふたつの種類に分け、プロット座標系は最終的に描画領域の大きさで決まる描画座標系に変換される、ということにすれば一般化できる。つまり描画領域での大きさが決まっている文字列などははじめから描画座標系で大きさが与えられているとする。今回のプロットライブラリの場合、変換を簡単にするため、この中間に

• 規格化座標系（Normalized座標系）

というのを挟むことにしたが、そのことははみ出し問題には直接影響しない。

このとき、例えば文字列の描画はプロット座標から相対指定された描画座標で表現されることになる。プロット領域の外に描かれる座標軸なども同じである。最終的に描画座標に変換されるプロット座標は、その文字列が描画領域からはみ出すかどうかで変換も変わってくる。

前回までにこの問題が「線形計画問題」であることがわかって、それを解くために「シンプレックス法」などのアルゴリズムがあることがわかった。前回まででそのアルゴリズムを勉強して、だいたいわかった。

今回のはみ出し問題特有のアルゴリズムの簡単化の可能性があるが、それは実装の時点でもう一度まとめようと思う。ここの残りでもうちょっと一般的な点を整理しておこう。

収束性

このアルゴリズムは収束が保証されるか？収束が保証されていないアルゴリズムを使ったライブラリは「もぐる」ことになるので使えない。

元の問題はN次元空間内の、ずっと前に出てきた式-11を満たすM次元部分空間のなかで、N-M個の座標の値が0である点のなかから評価関数の値を最小にする点を選ぶ、ということになる。その点の個数は

N!/(M!(N-M)!)

だけある。

ある点から始めて評価関数が小さくなるように0になっている座標をひとつずつ入れ替えていく、という作業をしていることになる。入れ替えに制限はないのでいずれは行き着くような気がする。きっともとのn次元の問題の凸性から証明できる気がするけど、よくわからない。

収束するまでにどのくらいかかるか、というのは出発点をどれに選ぶか、ということと、そこから途中何回入れ替え作業をする必要があるか、による。
効率の良い出発点を選ぶ方法は、今時点ではわからない。たぶんそんな都合のいいアルゴリズムは存在しない、と言う気がする。
途中の入れ替え回数は、一つ入れ替えるときに評価関数の変化量がなるべく大きくなるものを選べば少なくてすむようになる。これは前回の式-40の負の要素について式-41を計算して、実際に評価関数の変化量がもっとも大きいものを選べばよい。式-40の負の要素の数が多いときは計算が無駄になるけど、Mが大きな問題の場合、行列のサイズが大きくなるのでどちらが効率的かは判断した方がいい。

計算量と精度

精度の問題を考えると一般的な線形の問題と同じで解xBを求めるときに逆行列を直接計算しないで、Householder法でQR分解するなどして解を求める必要があるだろう。Householderも自分で実装しなければいけないね。う、めんどう。VDSPとかの標準で入ってるライブラリにHouseholderなかったかなあ。

ラッキーでなかったら

xBが負の要素を持っていたら、そのときは何らかの方法でまず、最適解ではないかもしれないけど、要素が全部非負の解を見つけ出さないといけない。簡単なのは原点、つまり0ベクトルが解だったら次のラッキー。でもなかなかそういう問題ばっかりでは無いだろう。僕が解きたいと考えているはみ出し問題では、あきらかに左側へはみ出す場合は原点は解にはならない。

そのために「２段階シンプレックス法」や「ビッグM法」なんかがあるらしい。このへんは実装と搦めて考えた方がいい。実装に入れるのはまだ先だけど。