順序のはなし・その3

今日扱うのは「前順序」(preorder) です. (しつこいようですが「全順序」の typo ではないです.)

私の事情で今日は短めにします. 細かいところは端折りますが内容は漏らさずに書くので, 質問などあればコメントや Twitter ( http://twitter.com/cocoatomo ) の方へお気軽にどうぞ.

前順序の定義

さていつも通り定義から入りましょう.

1. どんな a でも a ≦ a
2. a ≦ b かつ b ≦ c ならば a ≦ c

昨日の「半順序」から2つ目のルールが消えている形ですね.「a ≦ b かつ a ≧ b でも a = b とは言えない」という性質の順序です.「全順序」よりも弱い「半順序」と比べてさらに弱い順序ということですね.

前順序の例

かなり条件の緩い順序なので, いい加減な比較をしている例を出せば良いことになります.

例えばグループごとの人数で順序付けをする場合,「5人のグループの方が4人のグループよりも大きい」ということは言えますが,「どちらのグループも5人のグループだから同じグループだ」と言うのは違和感がありますね.

グループのメンバーが異っているのにそれらを一緒くたに扱うところに違和感があるのでしょう.「グループの人数」という観点のみで比較しているため,「グループのメンバー」という細かいところまで把握できていないのです. こういう「大雑把な比較」が前順序です.

明日以降

さて, 最初に挙げたネタが尽きたわけですが, 順序に絡めてグラフの話をしていこうと思います.「BFS」「DFS」「topological sort」あたりを取り上げる予定です.

「圏と絡めた順序の話とかも紹介できたらいいなぁ」とも思ってますが, 自分の勉強のペース次第です^-^;

おまけ

最近, 太郎の「男女」が「順序」の歌にしか聞こえません.

♪先生, 男子が列を乱して並びません
先生, 女子がおしゃれな順序でもめています

うるさい, 並べ, 整列結果を乱すな

順序のはなし・その2

さて今日は「半順序」の話をします.
昨日の全順序 (total order) に比べやや足りないところがあるので,「半順序」(partial order) と言います. どこが足りないかをこれから見ていきましょう.

半順序の定義

さて, まずは定義から行きましょう. 全順序のときと同じように記号「≦」が満たすルールを並べて定義します.

1. どんな a でも a ≦ a
2. a ≦ b かつ b ≦ a ならば a = b
3. a ≦ b かつ b ≦ c ならば a ≦ c

昨日の全順序と比べてどこが違うでしょうか?

そうです, 1つ目のルール以外は全く一緒です. そして, 全順序の1つ目のルール「a ≦ b または b ≦ a が成立する」から b が a だった場合を考えると,「a ≦ a」が出てきます. 今何を示したかというと, 全順序の1つ目のルールから半順序の1つ目のルールが導き出せることを示しました.

その逆はどうなるかと言うと導き出すことはできません. つまり全順序のルールは半順序のルールよりも強い (別の言い方だと「厳しい」) ものなのです. ここに全順序と半順序の違いがあります.

全順序の1つ目のルールが何を言っていたかと言うと,「a ≦ b または b ≦ a」つまり「どんな2つのものでも比較できる」ということでした. 半順序では「自分自身とは比較できる」ということしか保証されていません. この性質が足りないことを指して「半」(partial) という名前なのだと思います.

半順序の例

さて, 昨日扱った「全順序」は「順序」と呼ぶに相応しい感じがしましたが, 今日の「半順序」にはどんな例があるのでしょうか? 果たして自然な例はあるのでしょうか?

私はある集団を考えたときに, そこに入る順序はほとんどは「半順序」で「全順序」は無理矢理付けないと付けられない序列だと思っています.

例えば, とある試験の5教科の成績があったときにそれ比較するときのことを考えてみましょう.

A 君は「国語: 50, 数学: 100, 理科: 80, 社会: 60, 英語: 60」B 君は「国語: 80, 数学: 70, 理科 50, 社会: 70, 英語: 70」という成績だったとします. さて2人のうち「成績が良い」方はどちらでしょうか?

良くある評価方法は合計点で競う方法です. A 君は合計点 350 点, B 君は合計点 340 点なので A 君の方が成績が良いと言うことができます.

他には教科ごとに点数を比較する方法があります. A 君は2勝 (数学, 理科) B 君は3勝 (国語, 社会, 英語) なので, この観点では Β 君の方が成績が良いと言えます.

しかしどちらもあまり釈然としないところが残らないでしょうか?
合計点で競っても,「国語の1点」と「数学の1点」は本当に同じものなのでしょうか? 単純に足してしまって良いのでしょうか? また教科ごとの勝敗で見ても大差で勝っているものもあれば, 僅差で負けているものもあります. そんな状況でそれらを同じ1勝として数えて良いのでしょうか?

ここで全て100点だった人 (C 君) がいれば比較は簡単ですよね? その人はどんな人と比べても, 同じかより成績が良いと言えます.

ここに「半順序」が現れているのです. 1つ目のルールで全順序に対し欠けているのは比較可能性でした. 別の言い方をすると「ある2つのものが比較できないこともある」ということです. 上の例では5教科の成績というものに無理矢理全順序を入れようとしたためやや不自然な順序が入りましたが,「そもそも全順序を入れるのがおかしい」と考える考え方も有りです.

そこで半順序です.「A 君が B 君に対し全ての教科において同じか負けているときに A ≦ B」と定義すれば, これは半順序のルール (公理) を満たします. さすがにこのルールで順序を付ければ文句は無いでしょう.

さて, 今日はこれくらいにします. 順序のイメージが付いてきたでしょうか?
明日は「前順序」(全順序の typo ではない) を扱います.

それでは.

おまけ

順序の例として学校が舞台に上がるのは偶然なのでしょうか. (反語)

余談

このネタは @kinaba さんのブログの 正規表現しちへんげ！ シリーズだったり, @alg_d さんの一連のつぶやきに刺激されて書いています.

順序のはなし

古来より日本のプログラマの間には、「正月はフラクタル」という風習があります。

http://d.hatena.ne.jp/ku-ma-me/20110101/p1

ほぉ〜寡聞にして知らなんだ。

じゃあ、俺は「正月は数学」という風習を始めてみようと思います。

よしっ、今年のテーマは「順序 (ordering)」。順序に関わる話題を1ヶ月続けてみます。
「大学数学に興味があるけれどどう勉強していいか分からない。とっかかりが欲しい。」という人を対象に、平易なところから始めてみることにします。

全順序 (total order) の定義

最初は各順序の定義から始めます。

順序には色んな種類があるのでまず全順序から話をしていきます。
この順序は普段使っている「順序」のことで、どんな2つのものに対して大小が付けられるものを言います。

順序を記号で「a ≦ b」と書いて、「a は b 以下」と読みます。

定義の形で書くと、以下の3つのルール (公理) を満たすものとなります。

1. どんな a でも a ≦ a どんな a, b でも a ≦ b または a ≧ b のどちらかが成り立つ
2. a ≦ b かつ b ≦ a ならば a = b
3. a ≦ b かつ b ≦ c ならば a ≦ c

どれも当たり前のことを言ってると思いますが、それを改めてルールとして抽出するのが重要なのです。
ある命題を示すときには、この抽出したルールのみを使って証明を進めていきます。

余談

「<」じゃなく「≦」を使うのはなぜか? と思われたかもしれませんが、特に大きな意味は無いと思います。
上記の全順序に対して「<」を「≦ かつ ≠」と定義できます。そして、逆に

1. a < b, a = b, a > b のどれか1つのみ成立する
2. a < b かつ b < c ならば a < c

と「より小さい」ことを定義して、「≦」を「< または =」と別の定義を与えることができます。
(「『=』の定義は何だ!?」というツッコミは確かにあるのですが、今回は「順序」シリーズなので同値に関してはまた別のシリーズで扱いたいと思います。
ひとまず、普通にイメージする等号「=」と思ってください。)

こうやって「<」を経由して「≦」を定義することができ、当然最初に出した定義と同じことを言ってます。

ちょっとそれを確かめてみましょう。さて、何を示せば良いのでしょうか?

定義が同じことを言うには、片方の定義に出てくるルール (公理) からもう一方の定義のルール (この場合は気分的には「命題」と読んだりしたいです。) が成り立っていることを示せば良いです。
つまり、「<」が上のように定義されているとき「≦」=「< または =」についての3つの命題を示します。

1. どんな a でも「a = a」は成立しているので、「a < a または a = a」も成立しています。 a < b, a = b, a > b のどれかが成立しているので, a ≦ b または a ≧ b のどちらかが成り立ちます.
2. 「「a < b または a = b」かつ「a > b または a = b」」を変形すると「「a < b かつ a > b」または「a < b かつ a = b」または「a = b かつ a > b」または「a = b かつ a = b」」となり、定義より a < b, a = b, a > b のどれか1つのみ成立するので「a = b」が成立することが分かります。(この変形はいわゆる分配法則です。)
3. 「「a < b または a = b」かつ「b < c または b = c」」を変形すると「「a < b かつ b < c」または「a < b かつ b = c」または「a = b かつ b < c」または「a = b かつ b = c」」となり、まとめると「a < c または a < c または a < c または a = c」つまり「a ≦ c」となって欲しかった結論が出ます。

定義が同等である、ということのイメージが付いたでしょうか?
こういう議論はある程度の慣れが必要かと思いますので、何度も考えてみてください。

全順序の例

さて余談が長くなりましたが、本筋に戻って全順序が出てくる例を見ていきます。

まず自然数 (ここでは正の整数、1、2、3… とします) には全順序が出てきます。
通常の意味での大小関係があり、上の「≦」が満たすべきルール (公理) を満たしているので自然数には全順序があります。
(より正確に言うと「自然数は通常の大小関係が全順序となる集合」のような表現になるのですが、ここでは敢えて端折った不正確な表現をしています。)

次に整数 (0、±1、±2…) を考えてみましょう。
これにもさっきの自然数と同じく通常の意味での大小関係が全順序となります。

自然数と大きく違うところは整数には最小元はありません。自然数には「1」という「一番小さい数」がありますが、
整数では常にどんな数にもそれより小さい数 (例えば1つ小さい数) が存在して底無しに続いていきます。
この特徴は後で無限降下法を扱うところで効いてくるので、覚えておいてください。(そして俺も書くのを忘れないようにします!)

ちょっと複雑な例を出しましょう。
文字列の辞書順について見てみましょう。

辞書順とは「先頭の文字から比較していって50音順で早いものが前の方に、同じだった場合は次の文字で比較。さらに同じだったらさらに次の文字へ。」という比較の仕方でしたね。「は」と「ば」など細かいところに関しては今は解説は省きます。

当然、辞書は単語を辞書順で並べています。また学校の出席番号も姓名に関する辞書順です。
(私のときは男女別に番号を振っていたが、今は男女一緒に番号を振ったりするのだろうか?)

そしてこの並べ方だとどっちの出席番号がより後ろに来るのかはっきり決まります。
「こっちの人が前だけれど、考えようによっては別の人の方が前」というような曖昧さはありません。
この順序に関して曖昧さが無い、というのは別の言い方をすれば「1列に並べられる」ということです。
ここが「全順序」の特徴が強く出ているところなので、よく意識に焼き付けておいてください。

小学校の算数や国語の授業中は出席番号順に並んで勉強することが (特に新学年が始まった頃は) ありますが、体育の時間はまた別の順序で並びますね?
そうです「身長順」です。同じ集団に2つ以上の順序が入ることがあるのです。

これは裏を返せば、「ある集団 (集合) には好きに全順序が入れられる」ということです。もちろん上記の定義の3つの公理 (ルール) を守っている必要はありますが。

なので「誕生日の早い順」だったり「住所の辞書順」だったり色々な順序を作ることができます。順序はただ与えられるものではなく自分で定義できるものなのです。

明日以降は「半順序」「前順序」について扱っていきます。

おまけ

ただの思い付きです。

♪順序全順序順序、順序半順序順序、順序前順序ポセット順序、序順序順序最小元
(ポセット (poset) とかについては今後扱っていきます。)

読書会#2に行ってきました。

まぁ色々あったりして16:00くらい開始でした。

今日やった範囲

P.66 5.2.9 から P.71 5.3.5 まで。
P.72, P.73 は各自復習(何!?)するということで、めでたく Chap5 が終わった。
分からないとこなどは Google Group に書き込みをしましょう。

内容

5.2.9

factorial を作るところで補助的に出てきた項 g の中の if を test で書いたらどうなるの? という問題。

まぁ、素直に if then else を test に書き直せばいいんだけど、評価順序の違いによって答えの形式が違ってくるのが嫌なので abstraction でもってガードして最後にダミー変数を食わせましょう。という話。

5.2.10

0、1 とかの数値を Church 数に変換する churchnat という関数を作れ。という問題。

Church 数が再帰の構造をしているので、churchnat も再帰 (fix) を使って作れば OK。

5.2.11

pure lambda で実装された Church 数要素のリストの、全ての要素の和を求める関数を書け。という問題。

ここらへんを解いていると、Lisp で実装してる気分と同じになってくる。同じものなんだから当たり前か。

Representation

pure lambda の世界では Church 数の表現は色々有り得るけど、「振る舞い」だけ見たら全部一緒。
「iszro と問うたら tru と答えるのが c_0 だ。」みたいな感じ。これをダックタイピングと呼んでいいんだっけ??

んで、pure lambda term の集合をその「振る舞いを見れば一緒」という同値関係で割っておいて、普通の自然数の世界との対応を見ると、構造まで含めて一緒だよね。というのが最も言いたいこと。
こういうのは数学では「同型」と言ったりする。

5.3 Formalities

lambda term の meta-variable を使った定義は P.53 でもう扱ったんだけど、改めて集合の言葉で述べる話。
特に内容的には難しいところは無いが、meta-variable と variable の違いなどで感覚的に引っ掛かるようだ。
自分の感覚では meta-variable が 5.3.1 で出てくる (大文字の) T や V に相当する感じ。

5.3.2

Free Variable の定義。
素直なのですぐ理解できる。

5.3.3

FV(t)

≦ size(t) を示せ。という問題。

実は size は lambda term に対して厳密には定義されていないので、自分で上手く定義しなきゃいけないところ。

• size(x) = 1
• size(λx.t) = size(t) + 1
• size(t_1 t_2) = size(t_1) + size(t_2)

これでいいだろう。

Substitution

β reduction で面倒な代入の話。
スコープを越えて変数が移動するため、気を付けないと意図しない変数解放や変数束縛が起きる。その様子を安直な代入の定義からちょっとずつ改善していく話の流れ。P.69 からスタートして P.71 の最後 5.3.5 で一応定義の完成を見る。微妙に残っているのは、変数束縛を避けるための α conversion (名前付け替え) が「自然言語でしか定義されていないこと」。

[x -> y](λx.x) では変数解放 (束縛変数 x が非束縛変数 y になってしまう) が起きたり、[x -> z](λz.x) では変数束縛 (非束縛変数 x が束縛変数 z になってしまう) が起きたり災難が続く。特に変数束縛を回避する手段として出ている「名前付け替え」がまたなんというか苦しい。α conversion を実装に落とすと、かなりその場対応色の強い実装になりそう。

ちなみに読書会で話題に出した Common Lisp で macro を定義するときの変数束縛を避ける gensym という関数について。使用例を On Lisp から取ろうとしたのですがほど良いサイズのものが無かったので、→Scheme:マクロ:CommonLispとの比較←この記事でも読んでください。

ではお休みなさい。

追記

振り返りの内容で分かんないとこがあったら、ここのコメント欄でも Google group の方でもいいので質問ください。かなりはしょって説明してる気がしてます。

とあるブログにコメント

なぜか http://www.goodpic.com/mt/archives2/2008/01/openid_oauth.html にコメントが書けなかったので、ブログからトラックバックでコメントの代わり。

以下コメント

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

「エンタープライズでは、信頼性の担保されたシステム、ユーザーが前提」の項にある、

・ユーザーという実在する人間のアイデンティティを認証（Authentication）
・本人性を認証するため、Identityをもとにアクセス制御などの認可（Authorization）

は英単語が逆だと思うのですがいかがでしょうか?

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

認証と認可はどっちがどっちが分かんなくなるので、俺も自信は無いですが。。。

追記: [2010/11/23 23:59:59]
いや, やっぱり「認証」Authentication,「認可」Authorization で良かった.
英語でも日本語でも紛らわしい……

[algorithm] その他の SSSP アルゴリズムは並列処理に向くのか?

(見ての通りの書きかけです.)

Dijkstra 法がなぜ並列処理に向かないか?

※[2010/09/21 9:00] 用語を「並列」(parallel) に統一しました. まだ「並行」「並列」「分散」の使い分けがいまいち飲み込めてないので, 変だったらツッコミをいただけると幸いです.

さてここでは前のエントリで書いた Dijkstra アルゴリズム がなぜ Hadoop などの並列処理に向かないかを書いていきます.

玉入れとリレー

まずは比喩で話を進めていき, 並列処理に向いているアルゴリズムとそうでないアルゴリズムの区別を考えていきましょう.

運動会の種目から「玉入れ」と「リレー」という 2 つの競技を取り上げます. これらはどちらも団体でそれぞれ入れた玉の数やタイムを競うものです.

ただし, 同じ団体競技でもその性質は違います.

玉入れは競技人数を増やせば増やすほど得点の期待値は上がります. 例えば, 10 人で玉入れをしているチームと 20 人で玉入れをしているチームが競争すれば, 20 人のチームの方が断然有利でしょう. さらに 40 人, 80 人と増やしていけば, 落ちている玉を拾うコストがボトルネックになるまでスケールアウトできます.
極端なことを言えば, 玉入れの玉や籠を増やすという手段も採れます. こうしてしまえば際限無く得点の期待値を上げていくことができます.

逆に, リレーでは人数を増やしても玉入れほどには劇的にはタイムの期待値は上がりません. スタートとゴールがあらかじめ決められてしまっているため, 増えた人数の分だけ 1 人あたりの距離が短くなります. ある程度までは選手の疲労が少なくなる効果でタイムは伸びるでしょうが, すぐにバトンパスのコストがボトルネックになりタイムは落ちていくはずです.
そして, 玉入れの玉や籠を増やすようなボトルネックの解消手段がありません.

玉入れとリレーの違いは??

さて, なぜ玉入れとリレーでスケールアウトする/しないが分かれたのでしょうか?

それは処理の性質にありました.
玉入れでは玉が十分に転がっていれば玉を取り合うこともなく, 別の人の動作が自分の動作をじゃましません.

しかしリレーでは, バトンという 1 つしかないリソース (Singleton!) に対して各選手が処理を行っているため依存関係が生じ, どうしてもそれぞれの処理を並列で動かすことができません.

これを小難しく数式で書くとアムダールの法則とグスタフソンの法則になります. とは言ってもこの式は算数レベルの話なので, 覚えるほどの価値はありません. 式の字面を覚えるのではなく「並列処理基盤に載せても, 並列に処理できるとこしか処理時間の圧縮はできないよ」という式の意味の方を, 自分の言葉で噛み砕いて脳みそに染み込ませておきましょう. どうせ現実問題はこれより複雑で, とうてい計算なんぞできる代物ではないので.

余談ですが, 最近拾った面白い話にこんなのがありました.
秀吉とMapReduce : サルノオボエガキ
これも見事に部下の人数に対しスケールアウトするようにジョブを組んだ秀吉の頭脳の勝利と言えるでしょうか.

Dijkstra 法を復習

前置きがだいぶ長くなりましたが, 「処理の順序に依存関係があるかどうか?」という視点で Dijkstra 法を見ていきましょう.

Dijkstra 法では「スタートノードからの距離が最小のものから順に, 最短経路を確定していく」のでしたね. 忘れていたら前回のエントリで復習しておいてください.

以下のようなグラフに対して Dijkstra アルゴリズムを適用します.

まずスタートノードへの最短経路が決定します. 今回からは最短経路が決まったノードには色を付けていくことにします.

次に, 最短経路が決定したノードたちから 1 ステップで行けるノードのうち, スタートノードからの距離が最短のノードを探します.「い」ノードが選ばれ, 最短経路「S→い」, 最短距離 1 が確定します.

さらに同様に処理をしていくと,「は」への最短経路「S→は」と「S→い→は」, 最短距離 2 が確定,

「ろ」への最短経路「S→は→ろ」, 最短距離 3 が確定,

「に」への最短経路「S→は→に」, 最短距離 4 が確定,

「ほ」への最短経路「S→は→ろ→ほ」, 最短距離 5 が確定,

となり無事全てのノードの最短経路と最短距離が求まりました.
途中説明を省略したところはちょうど良い練習問題なので, どういったアルゴリズムで決定されていったか考えてみてください.
(というのが講義などでの便利な言い回しですよね〜.)

どこがボトルネックなのか?

さてここで問題ですが,「上の Dijkstra 法での解放では S, い, は, ろ, に, ほ, の順に最短経路が決まっていったが, この順序は前後することがあるか? もしくは前後させることができるか?」についてはどうでしょう?
つまり, Dijkstra 法は「玉入れ」なのか「リレー」なのか? という問いです.

答えは少し下に書くのでちょっと考えてみてください.

分かりましたか? 答えは「リレー」です.
その理由も答えられますか?

Dijkstra 法のポイントは, 『まだ最短経路が決定していないノードのうちスタートノードからの最短距離が「最短なもの」』を選んでいくことにあります. 最短という言葉がたくさん出てきましたが, 着目すべきは鉤括弧でくくった「最短なもの」です.

並列処理が得意な処理は, 小分けにできてそれぞれが独立している処理です. しかしこの Dijkstra 法では各ステップは「最短なもの」という 1 つしかないものを扱うことになります. 1 つのものはどうやったって小分けにはできません.
確かにどれが「最短なもの」かどうか調べるのに並列処理が使えますが, 最短かどうか比較するデータが全て出揃わないと「最短」が決定できません.

こういった他の処理の待ちが発生してしまってはせっかくの並列処理の恩恵が減ってしまいます.

ちょっと難しい言い方をすると,「ローカルな処理に還元するのが並列処理の特徴なのだが, グローバルなデータが必要になってしまってそのメリットを阻害している」となります.
(ちょっと自信が無いのですが, 「グローバルなデータ」の「グローバル」は CAP 定理 (仮説) で言うところの Consistency でしょうか?)

かと言って勝手に処理を進めてしまっては,「最短なもの」だと思って処理を進めていたが実は違った, という事態が発生し計算のやり直しになります.

どう解消したらいいのか?

上で述べた通り, そもそもアルゴリズムが並列処理に向いてないので, そのまま使うのは諦めます. (これこそ CAP 定理か?)

今欲しい並列処理のメリットは速度なので, そのために以下のデメリットを甘受します.

1. 解の完全性を捨てる
2. 対象とするグラフを絞る

1 番目の方法は, 最短経路が完全に決まる前に「これが最短なものだ」と仮定して, 次の探索を始めてしまう方法です. この方法ならそこそこ速く解が求まりますが, 再計算が必要になる可能性があるのが痛いところです.

2 番目の方法は, グラフの形をある程度規定してしまってアルゴリズムのチューニングをする方法です. 「解の完全性」と「求解のスピード」のトレードオフをチューニングする感じです.

ここから先はさらに個別の話になるので, また次の機会に記事を書こうと思います.

コメントでも Twitter でも感想もらえると嬉しいです! さらなる要望だともっと嬉しいです!!
つ【http://twitter.com/cocoatomo】

それではっ!