不動点とストライキの権限委任
Fixed Points and Strike Mandates (pvk.ca)
要約
この記事は、計算機科学における不動点計算の概念を、カナダ・ケベック州の学生ストライキの権限委任という現実世界の状況に適用しています。多くのアルゴリズムが不動点を見つける際に、意図せず最適でない(最小または最大の)不動点に収束してしまう傾向があることを指摘し、この現象が学生ストライキの意思決定においても同様に発生しうることを論じています。適切な初期値の設定やアルゴリズムの選択が、望ましい結果を得るために重要であることを示唆しています。
全文翻訳
不動点とストライキの権限
コンパイルやプログラム解析(シンボリック計算全般でそうだと思いますが)における多くのタスクは、(x = f(x)) の形の連立方程式の解を見つけることに帰着します。しかし、不動点を見つけるアルゴリズムを定義するように求められたとき、私たちは「どの不動点を探しているのか?」と立ち止まって問うことはめったにありません。
実際には、私たちは単調関数の不動点に関心を持つ傾向があります。順序 ((\prec)) が与えられたとき、(a \prec b \Rightarrow f(a)\prec f(b)) となります。この条件は、かなり妥当な仮説であることに加えて、通常、タルスキの不動点定理を利用することを可能にします。もし (f) の定義域((\prec) と共に)が完全束を形成するならば、(f) の不動点の集合もまた完全束となります!その系として、(\prec) の下でただ一つの最小不動点とただ一つの最大不動点が存在します。
これは非常に有用です。なぜなら、通常、有用な最小元(meet)と最大元(join)の演算を定義でき、完全束の恩恵を受けることができるからです。例えば、ある集合のべき集合である定義域の場合、(\subset) を順序関係、(\cup) を join、(\cap) を meet として使用できます。しかし、私が興味深いと思うのは、どの不動点を見つけたいのかに注意を払わないとき、人間は問題に応じて、最小または最大の不動点に収束するアルゴリズムを一貫して開発するように見えることです。まるで私たち全員が、一方の極端な不動点を覆い隠す共通の盲点を持っているかのようです。
単純な例は、デッドバリュー(無用な変数)の除去です。人々がプログラム中のそのような変数をどのように特定するか尋ねると、素朴な解決策は非常に似通ったものになる傾向があります。それらは、値がそれ自体無用な値の計算にしか使われない場合、その値は無用であるという観察を利用します。ルーチンは、すべての値をライブ(使用されている)として開始し、無用な値を削除していき、何も削除できなくなるまで続きます。
これらのアルゴリズムは、正しいが最適ではない(サイクルフリーコードを除く)解に収束します。私たちは可能な限り多くの無用な値を特定し、可能な限り多くの計算を削除したいと考えています。しかし、もしすべての値がライブであると仮定して開始すると、私たちのアルゴリズムは、以下のようなコードの x のような、明らかに無用な値をいくつか特定できなくなります。
for (...)
x = x
さらに特殊ケースを追加し続けることもできます。しかし、正しい(最も単純な)解決策は、デッドな値ではなく、ライブな値を特定しようとすることです。値は、ライブな値を計算するために使用される場合にライブです。さらに、戻り値とメモリへの書き込みは常にライブです。私たちのルーチンは、後者の値だけがライブであると仮定して開始し、見つけ次第ライブな値を追加していき、何も追加できなくなるまで続きます。
この場合、直感的な解は最大不動点に収束しますが、私たちが探しているのは最小不動点です。適切な初期値を設定することで、正しい不動点への収束が保証されます。
このパターンの他の一般的な例としては、マーキングではなく参照カウント、あるいはすべての値にトップタイプを初期値として割り当てる(SBCLのような)ことによる型伝播があります。
# 最近、数学やコンピュータサイエンス以外の分野で不動点計算の用途を見つけました。
ケベック州のほとんどの大学またはCEGEPの学生組合は、この冬と春に大学の授業料の値上げに反対する抗議活動を組織するために、ストライキの権限(ストライキを許可する投票)について投票します(またはすでに投票しました)。州全体に何百ものそのような組合があり、合計で約40万人の学生を代表しています。これらの組合の大多数は数百人(またはそれ以下)の学生で構成されており、少数の学生だけがストライキを行うことは逆効果だと感じる組合が多くあります。したがって、ストライキの権限には、他の学生がストライキの権限をどれだけ多く持っているかという最小数、および関与する組合や大学・カレッジの数に関する追加の下限条件が含まれることがよくあります。私の知る限り、これまでに採択されたすべての権限は単調です。つまり、ストライキ中の組合の集合によって満たされる場合、その集合のすべての超集合によっても満たされます。
タルスキの定理が(ここでも、学生組合のべき集合上の ((\subset, \cup, \cap)) で)適用されます。私たちが探している不動点はどれでしょうか?
私にとって明らかなのは、ストライキ中の組合の集合が最大の不動点を探しているということです。状況によっては、最小不動点は空集合(または権限採択時に下限を設定しなかったすべての組合)に自明に収束する可能性があります。さらに、権限は通常、少なくとも (n_0) 人の学生を代表する組合が同じ権限を採択した場合、その権限を採択したすべての組合が同時にストライキに入るといった説明と共に提示されます。
私はコンピューターサイエンスの大学院生仲間に、どの組合がストライキに入るべきかを決定するアルゴリズムをスケッチするように依頼しました。彼らは現在ストライキ中の学生組合の集合から始め、すべての条件が満たされた組合を追加していきました。このようなアルゴリズムは最小不動点に向かって収束します。例えば、それぞれ5,000人の学生で構成され、同じ10,000人のストライキフロアを持つ2つの組合があった場合、これらのアルゴリズムは両方の組合を、相手がストライキに入るのを待つというデッドロック状態に陥らせるでしょう。
代わりに、私たちはすべての組合(ストライキの権限を持つ)がストライキに入ると仮定して開始し、条件が満たされなくなった組合を繰り返し削除していき、最大不動点に到達するまで続けるべきです。これが純粋に理論的な懸念になることはほぼ確実ですが、抽象数学が現実世界の状況を解釈するのに役立つ非常に興味深いケースです。
最適ではない解に直感的に収束するというこのパターンは、不動点の計算においてしばしば現れるようです。これは必ずしも悪い選択ではありません。保守的な初期値は収束を速める傾向があり、中間的な解が常に正しい(実行可能である)という特性を持つこともよくあります。迅速な結果が必要な場合、最適ではない解で妥協することが理にかなっているかもしれません。しかし、それは他の可能性を考慮できなかった結果ではなく、意図的な選択であるべきです。