2019-10-21

Hadoopの勉強をはじめました。

Hadoop Distributed System

Hadoopはレイテンシを犠牲にIOを分散させて高速なバッチ処理を実現する技術、という程度のことしか知りません。*1

今在籍している会社分散処理やメニーコアコンピューティング、Spark,Hadoopなどをコアにやってて、エンタープライズ用のHadoop関係のFrameworkを開発・保守したり、そのSIをやっています。

ユーザーとしてFrameworkを使っている分には特にHadoopの知識は特に必要ない*2 *3のですが、自分の関わってる案件でもHDFSとかの生のHadoop要素が使われ始めてきたので危機感を持って勉強し始めました。

主に勉強した内容はサブブログに連載する予定です。

yuyubu-sub.hateblo.jp

*1:この理解が正しいかどうかは不明

*2:知っとけやという話もある

*3:というかFrameworkの目的がHadoopわからないJavaエンジニアでも簡単にシステムを保守できるというものであるように思っている

2019-10-20

論理学をつくる練習問題80(2)解答

論理学

本に回答が乗っておらず、ネットに載せておく意義があると思ったので公開。練習問題80(2)はND公理系(自然演繹)で式集合が矛盾するか、どうかの解答と矛盾していればそれを証明(自然演繹で示す)をする問題。 (a),(b),(c)とあるが式集合は全て矛盾しているためその証明(自然演繹による⊥の導出)のみを示す。

※間違ってたらすいません

論理学をつくる

作者: 戸田山和久
出版社/メーカー: 名古屋大学出版会
発売日: 2000/10/10
メディア: 単行本（ソフトカバー）
購入: 27人クリック: 330回
この商品を含むブログ (108件) を見る

問題
回答
- (a)
- (b)
- (c)

問題

Γ⊢_NDA, Γ⊢_ND¬Aなる論理式Aがあるとき、ΓをND矛盾しているということにする。次のうちND矛盾している論理式の集合はどれか、そしてそれがND矛盾していることを示せ。

(a) {P∨Q, ¬P→Q, ¬P}
(b) {P∨Q, ¬(P∧Q), P↔︎Q}
(c) {P→Q, P, ¬Q}

回答

(a)

P∨Q      Prem
¬P→¬Q    Prem
¬P        Prem
--------------
¬P→¬Q    Rep
¬P        Rep
¬Q        → elim

    Q    Prem
    ---------
    ¬Q    Reit
    ⊥    ¬intro*

Q→⊥    →intro

    P    Prem
    ---------
    ¬P   reit
    ⊥   ¬intoro*

P→⊥   →intro
Q→⊥   Rep
P∨Q    Rep
⊥      ∨elim

ポイント:演繹三行目で∧intoroをつかって¬P∧¬Qを導けるが、これが前提のP∨Qと矛盾していることは明らか(真理値表を書けば真になる割当が見つからない)。またド・モルガンの法則により¬P∧¬Q = ¬(P∨Q))だが、自然演繹に¬P∧¬Q,P∨Qから⊥を導くルールがなく、自然演繹の中のルールで他の式から⊥を導く必要がある。

(b)

P∨Q       Prem
¬(P∧Q)    Prem
P↔Q       Prem
---------------
    P    Prem
    ---------
    P↔Q    Reit
    Q       ↔elim
    P∧Q    ∧intro

P→(P∧Q)    →intro
     
    Q    Prem
    ---------
    P↔Q    reit
    P       ↔elim
    Q       Rep
    P∧Q    ∧intro

Q→(P∧Q)    →intro
P→(P∧Q)    Rep
P∨Q         Rep
P∧Q         ∨elim
¬(P∧Q)      rep
⊥           ¬intoro*

(c)

一番簡単と解答に書いてあったやつ。これを(a)にして最初に解かせてほしかったな。

P→Q
P
¬Q    Prem ⊥
--------------
P→Q    Rep
P       Rep
Q       →elim
¬Q      Rep
⊥      ¬intor*

なにかあればコメントください。

ちなみに、論理学をつくるはまだ挫折しておらず、ノートをサブブログの方に書き出しています。Twitterやめた僕が悪いんだけど、アクセス数3とかなので悲しい(涙)

yuyubu-sub.hateblo.jp

2019-10-06

フィッチスタイルの自然演繹のやり方

論理学

完全に個人のメモ。復習+忘れた時に思い出す用。範囲としては論理学をつくるp214~p235。気が向いたら述語を自然演繹で導出対象にするやり方も書くかも。

導出線と前提棒
演繹規則
自然演繹の攻略法

論理学をつくる

作者: 戸田山和久
出版社/メーカー: 名古屋大学出版会
発売日: 2000/10/10
メディア: 単行本（ソフトカバー）
購入: 27人クリック: 330回
この商品を含むブログ (108件) を見る

式集合の充足可能性の検査には真理表、タブロー、などの複数のやり方があり、自然演繹もそれの一種。

導出線と前提棒

(1) P → Q (前提)
(2) Q → R (前提)
(3) R → S (仮定)
(4) P      (仮定)
(5) Q      (4)と(1)より {P → Q, P}
(6) R      (2)と(5)より {Q → R, Q}
(7) S      (3)と(6)より {R → S, R}
(8) P → S (4)と(7)より {P⊨S}
(9) (R → S) → (P → S) (3)と(8)より

上記だとどの式がどの前提に依存しているのかわかりにくい。仮定が生きてるスコープを表すために、導出線、仮定の宣言に前提棒というシンタックスを導入する

パソコンでノートを作る都合上、導出線をインデントで表す。
前提棒を式下の---------で表す。

(1) P → Q (前提)
(2) Q → R (前提)
-----------
    (3) R → S (仮定)
    -----------
        (4) P      (仮定)
        ------
        (5) Q      (4)と(1)より {P → Q, P}
        (6) R      (2)と(5)より {Q → R, Q}
        (7) S      (3)と(6)より {R → S, R}
    (8) P → S (4)と(7)より {P⊨S}
(9) (R → S) → (P → S) (3)と(8)より

導出棒上の演繹は自分が書かれた導出棒より浅い(左)に存在する前提を参照することはできない。

演繹規則

表記

適応した演繹規則を導出した論理式の右側にやや空白をあけて表記する
- 本ブログではスペース4個とする
みやすさの観点から、同じ階層の導出ではこの規則表記を一番長い論理式のスペースに合わせる

例

P       Prem
P→Q    Prem
Q       →elim

前提規則(premiss rule:Prem)

(1)導出開始時の最初の前提棒状に書ける論理式の個数に制限はない。例:(i)
(2)それ以外の前提棒の上には一つしか論理式をかけない。例:(ii)

(i)

P → q Prem
¬Q∧R   Prem
S→¬P  Prem
------

(ii)

P → q Prem
¬Q∧R   Prem
S→¬P  Prem
-----------
    P  Prem
    -------

繰り返し規則(rule of repetition: Rep)

その導出の前提棒の上にある式を繰り返し書いて良い。

    P    Prem
    ---------
    P    Rep
P → P    → intro

復活規則(rule of reiteration:Reit)

依存している導出(有効なスコープである前提)を繰り返し書いても良い。

例

(P → Q) ∧ ¬Q    Prem
---------------------
P → Q    ∧ elim
¬Q        ∧ elim
    P         Prem
    ---------
    P → Q    Reit
    Q         → elim
    ¬Q        Reit

→除去規則(→ elimination: → elim)

A → B と A が同じ導出に出てきたら、Bをその導出中に書き加えて良い

P →Q    Prem
P        Prem
---------
P →Q    Rep
P        Rep
Q        → elim

→導入規則(→ introduction: → intro)

前提AからBへの導出を含んでいるならば、A→Bをその導出後の項目に書き加えて良い。

P→Q    prem
Q→R    prem
    P         prem
    ----
    P → Q    reit
    Q         → elim
    Q→R      reit
    R         →elim
P → R    → intro

∧除去規則(∧ elimination: ∧ elim)

A ∧ Bが導出の一項目として現れているなら、A,Bいずれもその同じ導入の項目として書き足して良い。

A ∧ B    Prem
A        ∧ elim

あるいは

A ∧ B    Prem
B        ∧ elim

∧導入規則(∧ introduction:∧ intro)

AとBがいずれも同じ導出の項目として現れているなら、A∧Bをその導出の一項目として書き足して良い。

A
B
A ∧ B    ∧ intro

↔︎除去規則(↔︎ elimination:↔︎ elim)

A ↔ ︎BとA(あるいはB)が導出に一項目として現れていたら、その導出にもう片方のB(あるいはA)を書き加えて良い。

A ↔︎ B
A
B        ↔︎ elim

↔︎導入規則(↔︎ introduction:↔︎ intro)

A → BとB → Aが一つの導出に一項目として現れてきていたら、その導出にA ↔ ︎︎︎Bを書き加えて良い。

A → B
B → A
A ↔︎ B    ↔︎ intro

¬削除規則(¬ elimination: ¬ elim)

¬¬Aの導出に¬Aを書き加えて良い

¬¬A

A    ¬ elim

¬導入規則(¬ introduction:¬ intro)

Aを仮定とした導出から矛盾(contradiction)が発生した場合、導出の次の項目に¬Aを加えて良い

    A    prem
    ---------
    ...
    B
    ...
    ¬B    contradiction !
¬A    ¬ intro

∨除去規則(∨ elimination:∨ elim)

A ∨ B,A→C,B→Cが導出に出てきた場合、Cを書き加えて良い

A ∨ B
A→C
B→C
C      ∨ elim

∨導入規則(∨ introduction:∨ intro)

AかBが同じ導出において以前に一項目として出てきているなら、A ∨ Bを書き加えて良い

A
A ∨ B    ∨ intro

B
A ∨ B    ∨ intro

矛盾記号(⊥)の導入

contradiction!を論理定項として使うとほかの∨ elimや→ introなどのオペランドとして使えるのでより演繹の自由度が上がる。
矛盾記号⊥を導入する。

¬elim*

矛盾する式集合(A,¬A)が導出に現れた場合、⊥をその導出に書き加えて良い

A
¬A

⊥

※矛盾記号の¬elim*を導入する場合、これまでの¬elimの規則はDNという名前に変更する

¬intro*

    A
    --
    ⊥
¬A

自然演繹の攻略法

【攻略法:→を目指すには】

A → Bに達したい時,Aを前提とし、一番下にBが出てくるような導出を構成し、→ introによってA → Bを得るようにする

【攻略法:∧を目指すには】

A ∧ Bに至りたかったら、AとBをそれぞれ別個に得るようにし、そのあとに∧ introを用いると良い。

【攻略法:間接証明】

¬Aを仮定して矛盾を起こして¬¬Aを導出し、¬elimでAを得ることができる。
- 個人的に背理法のような戦略だと思う

2019-09-25

NPクラスのNondeterministic polynominal algorithmについて

complexity computer science

4部作その3。組合せ最適化のページ(p422~423)の理解メモです。100回くらい同じページを読んだ結果、本書の記述だけだと不十分に感じたの類書を参考にしています｡

組合せ最適化第2版 (理論とアルゴリズム)

作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
出版社/メーカー: 丸善出版
発売日: 2012/02/29
メディア: 単行本
クリック: 5回
この商品を含むブログ (1件) を見る

余談:NP(Nondeterministic polynominal)という特性

※重要だと思って精読しましたが、乱択アルゴリズムを考えないときはあまり重要ではないので個人の判断で読み飛ばしてください。本書でもnon-deterministic polynominalを何かの前提・準備として紹介していません。

NPで扱える決定問題の種類はdeterministicに限らない。NPのNondeterministicという名前は決定問題のアルゴリズムとして採用できるアルゴリズムの制約からきている。

以下は同値である。

決定問題に多項式時間非決定性アルゴリズム(nondeterministic polynominal algorithm)がある
決定問題がNPに属する

命題15.14 決定問題は、多項式時間非決定性アルゴリズムを持つとき、そしてそのときのみ、NPに属する

非決定性アルゴリズムはランダム化アルゴリズム(randomized algorithm)の一種。

ランダム化アルゴリズムはf(s)→Tに対して以下のものと定義されています。

関数g:{s#r:s∈S,r∈{0,1}^k(s)}→T
- S:元の問題のインスタンスの集合
- r:ランダムビット
- 関数k:引数に対して整数を返す関数(k:S⇨Z+)。引数sに対して多項式サイズであることを表しています。

ランダム化アルゴリズムはある問題f(s)インスタンスのサイズに依存する多項式時間個のランダムビットrを使って元のアルゴリズムと近い決定ができるアルゴリズムです。元のアルゴリズムとどの程度精度が一致しているかで以下のように分類されています。

algorithm	definition (※全てp422からの抜粋)
モンテカルロアルゴリズム	インスタンスによらず少なくとも正の確率pで正しい答えを出力する
片側誤差のあるランダム化アルゴリズム	f(s)=0となるどのs∈Sに対しても、全てのr∈{0,1}^k(s)でg(s#r)=0となる
非決定性アルゴリズム	f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}^k(s)が少なくとも1個存在する
ラスベガスアルゴリズム	すべてのs∈Sに対してg(s#r)=f(s)である理想的な場合

下図のような閉包関係があります。

f:id:yuyubu:20190613181315p:plain

ここまで読んでまともな人ならお気付きかと思いますが、非決定性アルゴリズムの

f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}^k(s)が少なくとも1個存在する

という特性はモンテカルロアルゴリズムの

インスタンスによらず少なくとも正の確率pで正しい答えを出力する

という特性がすでに満たしているように読めるはずです。すなわち本書の記述のみを頼りに考えると「片側誤差のあるランダム化アルゴリズム」と「非決定性アルゴリズム」の集合のサイズは完全一致になるはずです。

本棚があったので類書を少し調査してみました。

乱択アルゴリズム (アルゴリズム・サイエンス・シリーズ―数理技法編)

作者: 玉木久夫
出版社/メーカー: 共立出版
発売日: 2008/08/08
メディア: ハードカバー
購入: 4人クリック: 52回
この商品を含むブログ (8件) を見る

すると、この本のp12を読むと片側誤差のあるランダム化アルゴリズムについて興味深いことがわかりました。

乱数の出方に寄らず常に正しい結果を与える乱択アルゴリズムをラスベガスアルゴリズム(Las Vegas algorithm)と呼ぶ。これに対して、乱数の出方によって誤った結果を与えることが実際にあるアルゴリズムをモンテカルロアルゴリズム(Monte Carlo algorithm)と呼ぶ。(中略) 対象とする問題が、判定問題(decision problem),つまりYESかNOと答えるタイプの問題である場合、モンテカルロアルゴリズムはさらに、片側謝りアルゴリズム(one-sideed error algorithm)と両側謝りアルゴリズム(both-sided error algorithm)の二つに分類される。真の答えがYESの時だけ、あるいはNOの時だけ誤る可能性があり、反対の場合には必ず正しく答えるアルゴリズムは片側誤りアルゴリズムである。どちらの場合にも誤る可能性のあるアルゴリズムは両側誤りアルゴリズムである。

黄色い本と白い本のone-sided error algorithm(片側謝りアルゴリズム、片側誤差のあるランダム化アルゴリズム )について定義を比較してみましょう

本	定義
黄色い本	f(s)=0となるどのs∈Sに対しても、全てのr∈{01}^k(s)でg(s#r)=0となる
白い本	YESあるいはNOの時だけ誤る可能性があり、反対の場合には必ず正しく答える

白い本のone-sided error algorithmの定義がより厳密と仮定すると、片側誤差ありアルゴリズムはYESインスタンスまたはNOインスタンスのどちらかは正しく決定することができるアルゴリズムということになります。黄色い本は"YES sideに誤差がありNo sideは完璧に答えるアルゴリズム"を暗黙の前提にしています。

上記を踏まえて乱択アルゴリズムの表は次のように再構成できます。

algorithm	definition (※全てp422からの抜粋)
モンテカルロアルゴリズム	インスタンスによらず少なくとも正の確率pで正しい答えを出力する
片側誤差のあるランダム化アルゴリズム	YESインスタンスもしくはNoインスタンスのどちらかを完全に正しく決定できる
非決定性アルゴリズム	NOインスタンスを正しく決定できる
ラスベガスアルゴリズム	すべてのs∈Sに対してg(s#r)=f(s)である理想的な場合

f:id:yuyubu:20190923043342p:plain — 再整理した乱択アルゴリズムの分類

上記の分類は黄色、白い本の内容と矛盾なく乱択アルゴリズムをうまく分類できているように思えますが、専門家ではないのですこし自信がありません。*1 　

非決定性アルゴリズムが存在する↔︎クラスNP なのはなぜか　

証明をそのまま載せてしまうのはアレなので概略だけさっと書きます。ランダムビットrをcertificateと読み替えて、ランダム化アルゴリズムをそのまま証明検証アルゴリズムに置き換えることが出来ます。

非決定性アルゴリズムの定義

f(s)=1となる各s∈Sに対してg(s#r)=1を満たすr∈{0,1}^k(s)が少なくとも1個存在する

から、NP問題の定義

任意のyes-インスタンスに対してのみ多項式時間で検証できる証明の存在だけが要求される。

補足:検証アルゴリズムの定義 Y = {y∈X:y#c∈Y'であるようなc∈{0,1}[p(size(y))]が存在する}

を導くことが出来ます。

補足情報

具体例としては以下の資料で2-SATをランダム化アルゴリズムを使って解く方法が挙げられています。

http://www-imai.is.s.u-tokyo.ac.jp/seminar/reading/resume/02summer_11.pdf

若干この本ではnondeterministicの話はわかりにくかったので、アルゴリズムイントロダクションという本を参照したところ、NP問題の特にnondeterministic側の問題に焦点を当てた本として以下のものが提示されていた。

アルゴリズムイントロダクション第3版総合版：世界標準MIT教科書

作者: Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson
出版社/メーカー: 近代科学社
発売日: 2018/01/09
メディア: Kindle版
この商品を含むブログ (4件) を見る

Hopcroft and Ullman [180] give a good presentation of NP-completeness in terms of nondeterministic models of computation.

[180] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition (English Edition)

作者: John E. Hopcroft,Rajeev Motwani,Jeffrey D. Ullman
出版社/メーカー: Pearson
発売日: 2013/10/03
メディア: Kindle版
この商品を含むブログを見る

和訳もあるようです

オートマトン言語理論計算論〈1〉 (Information & Computing)

作者: J.ホップクロフト,J.ウルマン,R.モトワニ,John E. Hopcroft,Jeffrey D. Ullman,Rajeev Motwani,野崎昭弘,町田元,高橋正子,山崎秀記
出版社/メーカー: サイエンス社
発売日: 2003/04/01
メディア: 単行本
購入: 1人クリック: 172回
この商品を含むブログ (19件) を見る

オートマトン言語理論計算論2 <第2版>

作者: ジョン・E・ホッブクロフト,R・モトワニ,J・D・ウルマン,野崎昭弘,高橋正子,町田元,山崎秀記
出版社/メーカー: サイエンス社
発売日: 2003/08/13
メディア: 単行本
購入: 3人クリック: 22回
この商品を含むブログ (11件) を見る

note:本エントリでは深入りしませんが、非決定性アルゴリズムより広い乱択アルゴリズムを考えたときの計算クラスもあるようです。

*1:余談ですがyes-sideが完璧になってる片側誤差ありアルゴリズムはco-NPで出てきそうだなと書いてて思いました。

2019-09-23

PとNPについて

complexity computer science

4部作その2。組み合わせ最適化第二版のp419~421の理解メモです。前回の決定問題の知識を前提に記事を書いています。　

yuyubu.hatenablog.com

組合せ最適化第2版 (理論とアルゴリズム)

作者: B.コルテ,J.フィーゲン,浅野孝夫,浅野泰仁,小野孝男,平田富夫
出版社/メーカー: 丸善出版
発売日: 2012/02/29
メディア: 単行本
クリック: 5回
この商品を含むブログ (1件) を見る

Nondeterministicについてちょっと小話

ちょっとわかりにくいのがNPですね。Not Pではありません。この話題に入る前にNondeterministic Turing Machineはドラえもんの秘密道具並みにヤバイ存在だということを頭に入れておくと、理解が深まります。NP問題を多項式時間で解くとされる「非決定性チューリング機械」は思考実験的アナロジーであり、任意のNP問題の非決定性アルゴリズムを多項式時間で解く計算機は実存していません。

またNondeterministicという単語が一般的なシステム用語と少しスコープが違う使われ方をしているように感じます。*1