業を積み上げ百合を組め 『総合タワーリシチ』

adventar.org
本 Advent Calendar 2日目の記事です.

最近『どうぶつタワーバトル』が流行していますね.
play.google.com
sasatanwwwww.hatenablog.com
hagyou.hateblo.jp
シンプルな操作性とは裏腹の高度な駆け引きが大量の廃人を生み出し,社会現象になろうとしています.
ぼくはNexus 5Xが文鎮化したのでプレイできないんですけど.

そんなときに心を癒してくれるのがこれ!『総合タワーリシチ』!『どうぶつタワーバトル』と大体同じ*1!!!!

二巻並べると顔が良い!!!!!!

感情が強い女が女とやっていく話です.
全体的に感情がデカい.
デカい感情に当てられて一週間ぐらい百合が厳しくなった.
今ではもう最高です.

*1:タワーリシチはロシア語の「同志」を英語読みしたようなのですが. タワーリシチ - Wikipedia

『オートマトン 言語理論 計算論 Ⅰ』

この記事は本 Advent Calendarの1日目の記事です.(1日目とは?)
adventar.org

本日の本は『オートマトン 言語理論 計算論 Ⅰ』.

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

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

J. Hopcroft, R. Motwani, J. Ullmanの3人による共著の日本語版です.
このうち,HopcroftとUllmanは昨日C&C受賞記念講演をした方です.
C&C受賞記念講演については講演メモを書いたのでそちらもどうぞ:
pandaman64.hatenablog.jp
pandaman64.hatenablog.jp
pandaman64.hatenablog.jp

ⅠとⅡの二巻構成で,Ⅰでは正規表現およびDFA*1,文脈自由文法およびPDA*2を扱います.反復補題もあるよ.
今学期の講義でオートマトンをやっているのでその教科書ですね.
Ⅱは持ってないので良く分からないのですが,決定性問題を扱い文脈自由文法のいくつかの性質が決定不能であることを示すようです.
DFAPDAチューリングマシンと扱う対象を広げていってるんですかね.

この本は帰納法の原理から初めて一歩一歩解説を進めていきます.
とはいえ,証明も形式的すぎずすいすい読み進めていくことができます.
例題や章末の演習問題・オートマトンの応用例が豊富なのも嬉しいですね*3
HopcroftやUllmanが計算機科学の教育でC&C賞を受賞したのも納得という感じの素晴らしい古典です.

今ならオートマトン力も付いているだろうし
www.jstage.jst.go.jp
にも再挑戦してみようかな・・・!

*1:Deterministic Finite Automaton

*2:PushDown Automaton

*3:XMLが出てきたのには時代性を感じますが・・・

C&C受賞記念講演行ってきた Ullman編

目次

Aho編:
pandaman64.hatenablog.jp
Hopcroft編:
pandaman64.hatenablog.jp
Ullman編: ここ

メモ

Aho, Hopcroftに続いて最後に話したのがUllmanです.

学生へのメッセージは言ってない気がする.聞き取れなかったのかもしれない.

最近はParallel Computationが良く使われている.
これは並列で計算することで高速化を図るためである.
しかし,並列計算を手でやるのは極めて辛い.そこで簡単に並列計算するためのシステムが作られてきた.
並列計算の中でも初期のアルゴリズムであるMapReduceについて詳しく見ていこう.

MapReduceの特徴としては

  • 並列処理を陽に書く必要が無い
  • 計算が失敗しても自動でハンドリングしてくれる

という点が挙げられる.
しかし,MapReduceにも制限があり,特に"reducer size"と"communication cost"にトレードオフが存在することを明らかにした.

MapReduceはMapとReduceの二つの部分からなる.
Map処理では,それぞれの入力に対してMapperを並列に適用する.
Mapperの戻り値はkey-value pairの集合となる.
このとき,入力に対して多段のmapperを適用することが多い.このような一連のmapperはMap Taskとしてひとつにまとめられる.

その後,並列計算システムが全てのMapperが返したkey-value pairをkeyでグループ化する.

グループ化したデータはkeyをキーとし,それに紐づけられたvalueのリストを値とするようなkey-value pairの集合になる.
これの各key-(valueのリスト)についてreducerを適用することで最終結果を得る.

MapReduceアルゴリズムの実行時間は

  • MapperとReducerの実行時間
  • Reducerにデータを送るときの通信時間(communication cost)

の二つの要因によって変化するが,多くの場合通信時間の方が影響が大きい.

薬の相互作用を突き止めるという課題で実際に生じた問題を紹介する.
これはStanfordのCS 341(data mining)で取り上げたトピックである.
医薬品は3000種類あり,それぞれの医薬品について1MB分の服薬データ(日時とか症状とか)がある.
この中から悪い飲み合わせといったような薬同士の相互作用を見つけたい.
これをMapReduceでやるとすると,ナイーブなアルゴリズムとしては

  1. Mapperは薬のペアをkey,片方の薬の服薬データをvalueとするデータを用意する
  2. Reducerは各keyのグループについてsignificantな相互作用が存在するか調べる

というものが考えらえる.
このアルゴリズムの問題点は,key-value pairの数が膨大になってしまうことである.
薬のペアは 3000^2 = 90000000個存在し,それぞれについて1MBの服薬データがくっつくので,全体で9TBのデータが発生し,これをネットワーク越しにReducerに送らなければならない.
これは1Gbps Ethernetでは全然終わらない量のトラフィックである.

このアルゴリズムを改良には薬をグループ分けしてやれば良い.
例えば,100個の薬を一つのグループとして扱うと,グループのペアの数は 30^2 = 900個になり,通信量も9TBから90GBに落ちるので数分待てば計算できる.
各ペアにくっつくデータ量は増えるが,計算時間は結局変わらないので全体としては大きく高速化された.

MapReduceの計算モデルを考えると以下のような特徴がある.

  • MapReduceアルゴリズムは一連の入力を取る
  • 入力に応じて出力を行う
  • 出力は入力のうち,一部分だけで決める

MapReduceアルゴリズムの解析で重要になる値を定義する.

  • Reducer Size(Q)*1は一つのReducerが処理する入力の最大のサイズである.Qは計算機のメモリサイズで上からバウンドされる.またQが小さいほど計算の並列度が大きくなって嬉しい.
  • Replication Rate(r)は一つのMapperが生成するkey-value pairの個数の平均である.rが大きいほどはcommunication costが大きくなってしまう.

先ほどの問題では,
 r \propto \frac{1}[Q}
という関係が成り立つ.
係数はグループの個数に依存する.
上式を見るとrとQの間でトレードオフが生じていることが分かる(Qを小さくすると並列度が上がるが,rも大きくなるのでcommunication costが増大する).

rをQの関数で表すという研究がある.
これができると,あるMapReduceアルゴリズムが上手いこと計算できているかを測定することができる.
rの上界をQの関数で表すことは既にできており,Ullmanは下界を調べた*2
これには,以下の性質が使える.

  • 1つのReducerが扱えるデータはQ個までである(Qの定義から)
  • 全ての出力について,その出力を計算するのに必要なだけの入力を受け取るようなReducerが存在する(さもなければその出力が計算できないため)

薬の問題で示した改良後のアルゴリズムはrが下界の2倍になる.
最良のアルゴリズムでは下界+1を達成できることが分かっている.
つまり,Ullmanの与えた下界は極めてタイトである.

他にも色々な問題に対してrとQの関係を調べることができる.
例えば行列の乗算をMapReduceでやることができる.
この場合には,MapReduceを2段にした方が効率が良いことが分かっているので,薬の問題で使った手法(これは1段MapReduce)は改善する必要がある.

ハミング距離1のビット列の問題*3についてもトレードオフが存在することを明らかにした.
一方ハミング距離が2になった場合にはopen problemである.

Marginals of a data cube*4についても調べた.

ここで全員の話は終わりで,16時を少し回ったぐらいだった気がする.
数分の休憩を挟んだ後QAセッションが開始.
最初の質問をした人が最前列の関係者席に座っていたご高齢の方で,聞き取りづらい英語でよー分からん話をグダグダ喋っていて時間がゴリゴリ溶けた.

QAセッションのメモはほとんどとってない.
Ahoが学生に対してNumber theory, Group theory, (量子コンピュータやるなら)Topological Theoryやるのが良いよとアドバイスしていた.
今の学部教育ではロクに数学やらないから考え直さないとかもねとも言ってた.

Hopcroftは人の直観は三次元空間用だから機械学習で出てくる高次元空間では通用しないよねとも言っていた.
また,教科書の話題では,本を書くのはお金を儲けるというよりも良い評判を得るためだよね(ただし中国語版は例外)とも発言していた.

結局3人のQAをした所で30分が過ぎてセッションは終了.
そのまま解散.

色んなトピックの話を聞けて凄い面白かった.
特に,Ahoは自分にとって完全に「ドラゴンブックの人」という扱いだったので,彼の口から量子コンピュータの話が出てきたときには驚いたし*5,最新の研究への言及もあって極めて良い刺激になった.

英語も大体聞き取れた.
メモ取ってる途中に喋られると厳しい~~~~という感じ.
相手も英語話者以外に話すつもりでやってるからね.

講演者後方30cmを陣取れたのも良かった.
UllmanはHopcroftの講演中眼鏡を開いた状態でつるをつまんでくるくるしていたのがかわいかったし,そのときAhoは飲み終えた紙コップを口に押し付けて左右に回転させながらスリスリしていたのが最高だった.

明日(今日?)からは本 Advent Calendarも書いていくのでよろしく.
ネタはまだ考えてません.
adventar.org

*1:UllmanはQを黄色い文字で書いていたので白背景では無限に見辛かった

*2:曖昧.上界を調べるのもUllmanがやっているのかな

*3:詳細不明

*4:これも不明

*5:そのままガッツリ解説し始めたのにもちょっと驚いた

C&C受賞記念講演行ってきた Hopcroft編 (2/3)

目次

Aho編:
pandaman64.hatenablog.jp
Hopcroft編: ここ
Ullman編:
pandaman64.hatenablog.jp

メモ

Ahoに続いて二人目の講演はHopcroftでした.

Hopcroftが若手に送るメッセージは「教官が勧めてくることはやらない方が良い.どうせできることだから.」という感じ*1

農業革命,産業革命,(後なんかあった気がする)に続く現在起こりつつある革命が情報革命(information revolution)であり,機械学習が情報革命の引き金を引きつつある.

データを分類するとき,データが線型分離できるとしたら簡単で精度も良い.
けど,現実には非線形なデータもたくさんある.
そんなときには高次元に移すような関数を用意して,高次元空間(無限次元なこともある)で線型分離すればいい.
実は個々の関数の値は必要なくて,内積だけ計算出来たら良い.
なので,カーネル行列を使うことで計算が簡単になる.カーネルが正定値なら対応する(高次元への)関数が存在する*2
カーネルを使って機械学習する手法の一つがSVMSVMは15~20年前は良く使われていた.

2012年にImageNetの誤答率ががくんと下がる.
これはニューラルネットワークが使われた結果.
今ではニューラルネットワークは人よりも精度が良くなっている.なんでうまくいくのかは分かってないけどね.

ここら辺にCNNの解説とかしてた気がする.どうでもよかったのでメモに無い.

ここから研究の紹介.
画像をNNに通して得られたベクトルをActivation Vectorと呼び,Activation Vectorの空間をActivatioin Spaceと呼ぶ.
Activation Vectorには画像の内容が入っていると考えられる.
画像→Activation Vectorの変換はNNに入れるだけだが,逆変換(Activation Vector→画像)はどうしたら良いだろう.
まずはランダムな画像を生成してNNに通す.
そこで得られたActivation Vectorから所望のActivaton Vectorの方向に勾配降下法で画像を変えていけば良い.

これをやると例えば画像のスタイル変換ができる.

  • 若い人の写真の年をとらせたり
  • コーネル大学の建物を中国風にしたり

できる.これを理論的に考えると,絵のスタイルや猫が写っているという情報は低次元の多様体としてActivation Spaceに埋め込まれていると考えられる.
ここからDeep Learningの学習理論に繋がるかもね.

コーネルの学生がDLの学習過程を観察中に気づいたことに次のことがある.
学習の初期の過程では,ニューロンのノードのうち3つが画像のサイズを学習していた.
しかし学習が進むにつれて,この3つのノードのうち2つは画像のサイズを学習するのを諦めて,他のものを学習し始めた.
時間が足りなかった*3ので,現象を見つけただけで理由は分かっていない.
これは一体どうしてなんだろうね*4

DLではパラメータに対して大量の極小点が存在するので,これらから良いものを選ぶ必要がある.
二つの極小点が同じ誤差値をとるが,片方は広い(傾きの変化がゆるやか)極小点でもう片方は狭い(傾きの変化が急)とする.
このときどっちの極小点を選ぶのが良いだろうか?
Hopcroftは広い方が良いと思っている.
まず,汎化誤差は訓練誤差から少しずれている.
広い極小点の場合は変化が小さいので,訓練誤差の極小点が汎化誤差の対応する極小点からずれていてもあまり問題は無い.
一方,狭い極小点の場合は位置の微妙なずれが大きな差になってしまう.
だから広いほうが良い.

同じネットワークに別々のタスクを学習させて,その学習結果のネットワークを混ぜて使うという研究がある.

GANいいよね・・・

5歳の女の子*5は写真を1枚見ただけでそれがどういうもの*6なのか分かる.
一方で,DLの場合はそれぞれの対象について数千枚の写真が必要.
人間は「写真を見たときにどうやって対象を理解するのか」を学ぶことができるが,今のAIつまりパターンマッチングではそれはできない.

*1:曖昧

*2:ここ聞き間違えてるっぽい.カーネルは関数のことで行列はグラム行列と呼ばれるもののようだ. c.f. xiangze.hatenablog.com

*3:その学生は1ヵ月しかいなかった

*4:たまたまだと思う

*5:Hopcroftの娘だった気がする

*6:曖昧

C&C受賞記念講演行ってきた Aho編 (1/3)

目次

Aho編: ここ
Hopcroft編:
pandaman64.hatenablog.jp
Ullman編:
pandaman64.hatenablog.jp

NECのC&C財団が出している賞をAho, Hopcroft, Ullmanの三人が受賞したのでその記念講演.
2017年度 C&C賞 受賞記念特別講演会 「若きコンピュータサイエンティストたちへのメッセージ」を見よ.

この3人は有名な教科書を書いていて,例えばAhoはドラゴンブックの著者だしHopcroftとUllmanが書いたオートマトンと計算理論の教科書を今期の講義で使っている.
以下講演のメモ,自分が興味あることだけメモって知ってることは書いてないので内容には偏りがあります.

メモ

会場は最前列が関係者席で2列目から自由席だったので,2列目ど真ん中という最高の位置を確保.
講演の開始数分前に3人が入ってきたらなんと目の前に着席.
毛穴まで見える!*1

最初に座長がうだうだ紹介したあと,講演本体のスタート.
トップバッターはAho.
Ahoの若者へのメッセージは「最高の人間と働けるところにいけ*2」とのこと.

掴みはインターネットの話から.
全人類の半分以上がインターネットを使っていて,それはネット越しに様々なサービスにアクセスするためである.
それらのサービスはソフトウェアに依存しており,コードベースはどんどん肥大化している.
巨大なソフトウェアの行数を調べた研究*3によると,

にもなる.
これらのソフトウェアはみんなアルゴリズムによって構成されている.
アルゴリズム大事*4

アルゴリズムが何故大事かというと,計算効率に関わってくるからだ*5
Aho–Corasickという文字列マッチングアルゴリズムがある.
これはCorasickが見つけたもので,ある日相談を受けたので「そのままこのアルゴリズムの研究を続けなさい」と言った.
その後Ahoが一般化した.

AWKのAはAhoのA←かっこいい
AWKはパターンとアクションを組にしたものを並べて記述する.
AWKの文字列マッチングはPythonPerlと比べて極めて速い.
アルゴリズムの力*6

ここからは量子コンピュータの話をします.←マジ????????
量子コンピュータの計算モデルは量子力学に基づいていて,状態は複素ヒルベルト空間で表現.
状態の変化はユニタリ行列を掛けることで表される.これは可逆だね.
複数のQubitをまとめた系はヒルベルト空間のテンソル積.なので計算基底が 2^nで増えていく.
測定によってQubitから古典bitに落とすことができる.測定は可逆ではない.

量子コンピュータの嬉しいところは古典よりも速く計算できる分野があるところ.
因数分解の現在見つかっている最良の古典アルゴリズムは指数オーダー*7なのに対し,量子コンピュータ(Shor's Algorithm)だと O(n^3)で解ける.
今の暗号は因数分解の困難さに依っているので量子コンピュータができると大変.1GHzの量子コンピュータがあるとすると,1024bitの因数分解が31時間で終わる.
なので,今では耐量子*8暗号が考えられている.

量子コンピュータのモデルにも色々ある*9
一つは量子回路.
量子断熱計算というのもある.DWaveはここに属する.
Microsoftがやっている量子コンピュータはTopological Quantum Device*10というもの.
トポロジカル量子計算は一つの粒子を二つに分裂させたquasiparticleを使って計算を行う.
バイス上ではquasiparticleを並べておき,そのうち一つをつまんで他のquasiparticleの周りをぐるっと周らせる*11
この回転が量子ビットにユニタリ変換を加えることに相当する.
最後に二つに分裂したquasiparticleを一つに戻すと計算結果の量子状態が得られる.
ぐるっと周らせるquasiparticleは一つだけで量子回路と等価になることが知られている.

トポロジカル量子計算では,どのquasiparticleの周りを周らせるかだけが重要で,実際の周るルート(ノイズが乗る)は関係ない(ここがトポロジー).
なのでノイズに対して強いだろうと言われている.
一方量子回路の場合は量子誤り訂正のために10倍ぐらいはQubitが必要.

量子プログラミングにもコンパイラ必要.
高級言語→Device-independentな言語(QASMなど)→Device-dependentな言語(QPOL)→具体的なデバイス用の記述
と変換していく.
量子プログラミングにはコンパイラだけでない開発スタックが必要で,例えばシミュレータが必要.
MSのLiquidはこの開発スタックの一つ.
LiquidはKrystaというMSコロンビアの人がメインメンバーの一人としてやっている*12
MSはVisual Studioに統合した量子プログラミングの開発スタックを来月公表予定.

最近やってる分野としてはQuantum Approximate Optimization Algorithmがある*13
難しい組み合わせ最適化問題を解く.

この本がお勧めらしい

Homo Deus: A Brief History of Tomorrow

Homo Deus: A Brief History of Tomorrow

感想: 量子コンピュータの話を聞くとは全く思ってなかったので興奮した.量子プログラミング言語チューリング賞取りたい!!!!
あとHopcroftの講演中に飲み終わった紙コップを口元で左右にくるくるしてたのがかわいかった.

*1:ホンマか?

*2:work with the best people as you can

*3:これはAhoのやったものなのかは分からん

*4:ちなみに,アルゴリズムを1つだけ教えるとしたらユークリッドの互除法を教えるべきだそうだ.2500年前のアルゴリズムで今でも使われているものが他にあるだろうか?って言っていた

*5:これ言ったか記憶が曖昧

*6:記憶が曖昧

*7: \exp(O(n^\frac{1}{3}\log^\frac{2}{3}n) ) とのこと

*8:Quantum-proof

*9:筆者注: 以下の三つは計算能力の上で等価.ただしDWaveは量子断熱計算のサブセット

*10:日本語だとトポロジカル量子計算

*11:PowerPointのアニメーションでquasiparticleが激しく動く

*12:この人とAhoは面識あるっぽい

*13:研究室のドクターがやってるっぽい?

#技術書典3 振り返り


これは説明責任です(書いてあるのはCivilization IVというストラテジーゲームのことです)


これは売り上げで食った立ち食い焼肉です.

申し訳ない申し訳ない

今回の本は「自作言語の処理系を自作CPUのアーキテクチャ向けの機械語を吐くように作り,それを自作CPUの(シミュレーションで)動かす」という本です.
言語は虎本の下位互換なやつで,CPUも16bit RISCです.
情報系学部生がやることをやったってだけです...*1

画像の通り未完成版で,具体的にはコンパイラのバックエンド部分(生存解析とかレジスタ割り付け)の文章がまだ書けてません.
そんな本を60人以上の方がお買い求めくださって本当にありがとうございます.
「完成版期待してます」とおっしゃった方もちらほら居まして痛み入ります.頑張ります.



現在のPDFも定期的にアップデートするつもりです.
そのときにはTwitterとメールで告知するのでお願いします.
「ここ間違ってるぜ」「読みにくいぞ」みたいな指摘でも何でもご意見お待ちしています.

ありがとうございました.
やっていくぞ.

*1:何か後になって開示するみたいでごめんなさい.

#技術書典3 に自作言語&自作CPU本を出します

ごめんなさい原稿終わってません

今A4で42ページです
アップデート配布するんで許してください...

明日の技術書典3で本を出します.
f:id:pandaman64:20171021140836p:plain
自作言語のコンパイラを書いて自作CPUの上で動かしてみよう!という本です.
電子書籍(PDF配布)オンリーで200円で頒布します.

当日は「か03」までお願いします.