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」までお願いします.

2017年度上半期成績

弊学では今年度よりGPAが正式導入され,そのついででABC+D(不合格)の四段階評価からSABC+D(不合格)という五段階評価に移行しました.
成績基準を見てみましょう:
http://www.gakuji.keio.ac.jp/academic/shoumei/3946mc0000001jyk-att/gakubuseisekikijyun.pdf
これまでは最高評価のAを取るには85点で十分だったのに対して,今学期からはボーダーが上がり90点が必要になりました.
厳しくなりますね.
同様に,今まで70点以上取ればBが出てGPAでは3換算になったのに対してこれからは80点必要です.10点分の基準変化は極めて大きいでしょう.
テストが失敗したら容赦なくGPA2が降ってくることになります.

それでは今学期の成績です.
f:id:pandaman64:20170905204128p:plain
・・・
モロに評価基準の変更を喰らった気がします.
GPAは3.933→3.858と2年前の水準まで下がってしまいました.悲しい.