ここってRustのハイライトできんの？
>|rust|
use std::collections::HashSet;
type Pi = Vec<u32>;
fn calc_k(pi:&Pi, i:u32, n:u32) -> u32 {
// pi(i) + 1 .. n
let g0: HashSet<u32> = (pi[i as usize - 1] + 1.. n + 2).collect();
// pi(1) .. pi(i-1)
let g1: HashSet<u32> = pi[0 .. (i - 1) as usize].to_vec().into_iter().collect();
let diff = &g0 - &g1;
match diff.into_iter().min() {
Some(k) => k,
_ => 0
}
}
||<
あかんわ
組込Deep Learningで、量子化された状態での学習というのは離散最適化問題なのでは？と思い立ち組合せ最適化 第2版を読み始めました。最初のアルゴリズムとして、パス列挙アルゴリズム(path enumeration algorithm)が載っていたので、これまた勉強を始めたRustで書いてみました。
やりたいことは、nが与えられたときその順列を列挙したい。n = 2だったら(2,1)と(1,2)、n=3なら(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)の6つ。ちょうとn!の組み合わせが欲しい出力です。本の一番最初にでてきたアルゴリズムなので、これを最初の一歩として、この後に再帰バージョンなどがでてくるのでは無いかと思ってます。
本のアルゴリズムをそのまま実装してみた結果がこうなりました。明らかにエラー処理を握りつぶしにいってますが、初めてのRustプログラムなので勘弁してください。アルゴリズム的にmin()が失敗することはありえないのでpanicで落ちても良いですね。
use std::collections::HashSet;
type Pi = Vec<u32>;
fn calc_k(pi:&Pi, i:u32, n:u32) -> u32 {
// pi(i) + 1 .. n
let g0: HashSet<u32> = (pi[i as usize - 1] + 1.. n + 2).collect();
// pi(1) .. pi(i-1)
let g1: HashSet<u32> = pi[0 .. (i - 1) as usize].to_vec().into_iter().collect();
let diff = &g0 - &g1;
match diff.into_iter().min() {
Some(k) => k,
_ => 0
}
}
fn enumlation(n: u32) -> Vec<Pi> {
let mut pi : Pi = (1..n+1).collect();
let mut i = n - 1;
let mut result : Vec<Vec<u32>> = Vec::new();
let mut k = calc_k(&pi, i , n);
result.push(pi.clone());
// k == n + 1, i == 1
while k != n + 1 || i != 1 {
if k <= n {
pi[i as usize - 1] = k;
if i == n {
result.push(pi.clone());
}
if i < n {
pi[i as usize] = 0;
i = i + 1;
}
}
if k == n + 1 {
i = i - 1;
}
k = calc_k(&pi, i , n);
}
result
}
#[test]
fn test_k() {
assert_eq!(calc_k(&vec![1,2,3,4,5,6], 5, 6), 6);
assert_eq!(calc_k(&vec![1,2,3,4,6,5], 5, 6), 7);
assert_eq!(calc_k(&vec![1,2,3,4,6,5], 4, 6), 5);
}
fn main() {
let ret = enumlation(4);
println!("len = {}", ret.len());
println!("{:?}", ret);
}はてなダイアリーではrustの色分けができないのかな。ぐぬぬ。
n = 4で動かしてみるとちゃんと動いてそう。
len = 24 [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
unstableだけど、この辺が使えそう。
https://doc.rust-lang.org/1.1.0/std/slice/struct.Permutations.html
Qiitaに別の実装を見つけました。
https://qiita.com/aflc/items/d6fa617910092377e022
アルゴリズムをさっと動かして試してみたいって時には、Listに入れておけば配列としても集合としても扱えるし順列も簡単にとりだせるGauche便利。一方実務でやる場合は、Rustの制約のおかげでテストの工数がぐっと減らせそうで、かつ最初にアルゴリズム整理しないといけないので設計に時間がかかるが最初から完成度が高いコードができそうな気がしました。（小学生並）
土曜日に行われたなにわTECH道×TFUG KANSAI Deep Learning フェス2018のレポートです。
今回は発表も無く、当日の僕の役割は司会者の近くに座って何かあったらサポートするというポジションだったので、集中して発表内容を聞くことができました。当日は公演中でも「○○さん到着されました」とか連絡がメッセージで飛んできており、僕が対応しないといけない事もあって意外に忙しかったです。会場に来られた方々とゆっくりお話できなかったのは残念です。
毎回、Googleの最新情報を説明していただいて、なにわテックに来られる皆さんにとってもなじみの深いポジションになっています。タイトルにTPUが入ってますが、内部のアーキテクチャよりは、Deep Learningの基礎であったり、Googleの方向性、チップ開発の意図などの説明が多くわかりやすく聞くことができました。
Edge TPUについて質問があり、みんな気になっている様子。
同じ自社の技術を社外に伝える立場として、説明の仕方や発表資料の構成はいつも参考にしています。
CPUで物体検出させたら国内No1だと思っているモルフォさんの発表です。高速化の為の手法が一覧になっていて、これを使っている、これを使っていないと表になっていたのが良かったです。ここまでしゃべって良いのかなと心配していますが、同じ事を今からやっても抜かれませんよという自信を感じました。
実務で組込DLをやるときに、精度を落として良いのかどうなのかというのは、学習や実装の方針に大きく影響を与えるので、そういう問題があるよって事を話していただいたのは良かったです。
なにわテック初参加です。高位合成やツールの話から入り、ここで置いていかれる人が多いかなと思っていたのですが、みなさん結構真剣に見られてました。最後の方で、ようやくDeePhi Techの買収の話がでてきました。全体的に一本パスを通そうとしているのは分かるのですが、どうしても個別の技術を寄せ集めたように見えました。クラウドから機械学習までサポート大変そうだなという感想です。
発表後の内輪の懇親会でお話ししたところ、僕のFPGA全盛期に非常に近いところにいたことが分かり、懐かしい話題で盛り上がりました。業界せまい。
農業のAI事例を動画を交えて発表してもらいました。最初に、ドローンを飛ばしてオルソ画像から、農地に何が育てられているかを色分けするデモを見ました。このデモが良くできていて、動画の中から少しでもやっていることや精度を見ようと見入ってしまいました。はっと横を見るとモルフォの森広さんも食い入るように見ていたので、流石同業者だなと思いました。
いつも発表が面白く、発表の度に会社で抱えているスマート野菜の量が増えていて、経営的に大丈夫なんだろうかといつも心配しています。執行役員というポジションにありながら、技術的なこともやり続けますよというスタンスがかっこいいですね。こうなりたい。
戦略的データサイエンス入門 ―ビジネスに活かすコンセプトとテクニックを読みました。
タイトルにあるようにビジネス側からのデータサイエンスについて書かれた本です。データサイエンスの本は、ともするとアルゴリズムから手法を分類しがちですが、この本はやりたいことに対して、どういうアプローチがあるのかを説明しています。誤検出の話など、他の本に比べて事例を交えた説明が非常に詳しいです。共起についてはこの本で始めて知りましたが、お客さんによっては最重要視されるところも有り、画像処理とは違う世界が広がっています。
一方、数式に関しては中途半端な所があります。突っ込んで説明しないのは良いのですが、数式の一部が日本語になっていてかえってわかりにくいところもありました。
実例をベースに単純に考えると間違える事を詳しく説明されていました。手法の評価自体も今まで読んだ本の中では一番詳しく説明されていました。参考文献も充実していて、気になったら、さらに詳しく調べることもできます。全体を通して筆者の誠実さが伝わる本でした。
度々でてくる「（良い）データは投資」という概念はその通りだと思います。良い分析をするための良いデータというのは、お金と時間を大量にかけて取得しないといけないし、データの背後にある背景（ここで○○のサービス開始とか）も押さえている人が分析しないと、データが活きないのは感じました。
正直、作業者レベルの僕が読む本ではない気がしますが、もう少し実務になれて上のレイヤーの仕事になるか、社内のデータ分析の担当になったりしたらもう一度取り出して読みたいです。
Writing Compilers and Interpreters A Software Engineering Approach 3rd Editionを5月から読んでました。なかなか面白い本なので紹介します。コンパイラの勉強というとどうしてもパーサーで挫折してしまいがちです。この本は、まずはフロントエンドと、中間処理（intermidiate）、バックエンドまでを簡単に作って、そこから少しずつ進めていきます。前半はどうしてもパーサーよりですが、パーサーという章があるわけではないのでそこで詰まることなく、面白いところまで手を動かしながら読めました。
難しい理論は置いておいて、Pascalのコンパイラ、インタープリターをJavaで実装していく本です。本の内容は、タイトルの通りコンパイラを書くことに重点が置いてあります。実装上のテクニックは詳しく書いてありますが、背景のアルゴリズム説明や、別の実装方法の検討などは最後の方で少し出てくるレベルです。
目次はこうなっています。Kindleで読んだのでボリューム不明でしたが、紙の本だと800ページ越えですね。半分くらいはJavaのソースなので、見た目よりはボリューム少ないと思います。理解を確認するための演習問題は特にないですが、Pascalのソースコードがあるので、それがちゃんと動くかどうかで理解度を確認できます。
Chapter 1 Introduction 1 Chapter 2 Framework I: Compiler and Interpreter 11 Chapter 3 Scanning 55 Chapter 4 The Symbol Table 97 Chapter 5 Parsing Expressions and Assignment Statements121 Chapter 6 Interpreting Expressions and Assignment Statements167 Chapter 7 Parsing Control Statements 189 Chapter 8 Interpreting Control Statements 233 Chapter 9 Parsing Declarations 249 Chapter 10 Type Checking 331 Chapter 11 Parsing Programs, Procedures, and Functions 371 Chapter 12 Interpreting Pascal Programs 431 Chapter 13 An Interactive Source-Level Debugger 501 Chapter 14 Framework II: An Integrated DevelopmentEnvironment (IDE) 543 Chapter 15 Jasmin Assembly Language and Code Generation forthe Java Virtual Machine 577 Chapter 16 Compiling Programs, Assignment Statements, andExpressions 625 Chapter 17 Compiling Procedure and Function Calls and StringOperations 661 Chapter 18 Compiling Control Statements, Arrays, and Records719 Chapter 19 Additional Topics 791
ぱっと見て面白そうなのが、13章、14章のデバッガやIDEの作成ですね。インタープリターで動かしながら、最後はJavaのアセンブラを出力できるところまでやります。
12章までは手を動かしながら、あーだこーだやってました。いまいち仕組みが分かってない中、おかしいポイントを見つけて修正はできていたので、それなりには理解している気がします。
13章以降は、デバッガについては過去仕事で作ったことがあるし、構文ツリーができてしまえばSICP読んでいるからまあ読まなくても大丈夫かなと判断しました。
筆者がBeautiful Codeの執筆もしている事もあり、インターフェイスと実装をちゃんと分けたりソースコードはわかりやすく、教科書としても重点的に説明してありました。フロントエンドやバックエンドの単位でファクトリーパターンを使うのは理にかなっていて、すごく勉強になりました。コンパイラのバージョンアップで文法が変わったとき、オプションで昔の文法でコンパイルするとき等、この仕組みがあれば便利です。
コンパイラ全体を通して、オブザーバーパターンが使われています。例えば、変数が宣言される度にメッセージが飛び、簡単にログを取ることができます。インタープリタ実装時にも、変数の代入（更新）の度にメッセージを送ることでデバッグ可能な環境を作っています。パーサーのデバッグ時には、エラーメッセージを受信するところにブレークポイントを張っておけば、エラー発生時にスタックトレースを見て、どういう経路でエラーになったかが一発で特定でき、非常に開発効率が良かったです。
構文ツリーを構成するにあたって面倒なところは、どんどん辞書に入れて行ってデータ構造が難解になるのを防いでました。例えば、for文に相当するnodeは、インデックスの初期値（最小値）、終了の値（最大値）、それらの型、ステップなどを、全部辞書に入れて行くことで、ソースコードがすっきりしていました。構文ツリーをXMLでダンプするところも結構ページを割いて解説してあり、始めてコンパイラを作る人にはうれしい情報が満載でした。
Class名は非常にわかりやすい反面、関数名は微妙な物があり、悩ましい感じはします。標準関数arctan,cos,exp,ln,sin,sqrtを処理する関数名がexecuteArctanCosExpLnSinSqrtだったり。これは浮動小数点数を引数に、浮動小数点数を返す関数の処理ルーチンです。同じくabsとsqrを処理する関数はexecuteAbsSqrで、これは引数の型によって整数か浮動小数点数を返す関数です。もうちょっと良い名前はなかったのかと・・・。
コンパイラ・インタープリタの型システムの事を正直舐めてました。
修飾のバリエーション、ユーザー型、コンテナ、スコープ、再帰的な定義、オブジェクト指向だとこれに継承が入ってきます。型をパースして、その情報を管理するだけでも相当めんどくさい。手を動かしてみて始めて分かりました。TAPL読まねば。
二つとも適当に作れそうな気がしていたが、同じソースをコンパイラとインタープリタで全く同じ動きを保証するのがかなり大変と言うことが分かりました。特にコンパイラが最適化で計算順序を入れ替えたりしたとき、全く同じ結果を保証するのはそれはそれで別の技術ですね。
今回JavaのソースをPythonに移植しながら動かしました。良く分かってないコードを動かすときに、型をちゃんと宣言できないと何をやっているかさっぱり分からなくなりました。全然違うclassの列挙体(enum)を比較しても、しれっとFalseを返すところとかは泣きそうでした。比べても意味のないものを比較しているので、せめて実行時にワーニング出して欲しい。途中からPEP484 type hintを使ってアノテーションをつけていくと大分ましになりました。コンパイラ作るときは、F#みたいにコンパイル時にちゃんと型のチェックをしてくれる言語の方が良いですね。出遅れたけどRustは触ってみたいです。
あとディレクトリをまたぐ（一度上って別のディレクトリへ降りる）Classのimport方法が未だによくわからないです。ソースの一番上でなくて、classの中でimportすると若干規制が緩くなることが分かったがそこまでです。実際のコードでも、フロントエンド、中間処理、バックエンドが綺麗に分かれていることは難しく、すごくごちゃごちゃした参照関係になります。間に中間処理が入るので、フロントエンドとバックエンドなら独立しているかというとそうでもなく、バックエンド側でエラーが出たときに元のソースコードの情報（行数とか）と得ようとすると、フロントエンド側のclassにアクセスできる方が手っ取り早かったりします。実際に書いてみて気がついた事で、標準入力から読み込んだ文字列の処理は、ソースコードのリテラルと同じ処理をする事があり、インタープリタ側でスキャナーとかトーカナイザーの機能を使うケースがあります。何も考えずトーカナイザーだからフロントエンド側にソースを配置しちゃうと、全体としてぐちゃぐちゃしてきました。これも辛かったです。
機械学習プロフェッショナルシリーズのオンライン機械学習を読みました。
タイトルはオンライン機械学習となっていますが、機械学習の基本的な学習アルゴリズムについて説明されている本です。特にオンラインでしか通用しない話だけでなく、半分くらいは基本的な説明が書かれています。
最初に読んだときは、勾配の求め方とループしか書いていない全然意味が分からない本扱いしてしまいました。courseraのMachine Learningコースを受講後に読んでみて、始めていろいろと意味が分かりました。この本をぱっと取ってみて良く分からないと思ったら、courseraから始めることをお勧めします。誤差関数と正則化を足した物がコスト関数で、このコスト関数を最小化させることが目的、くらいが頭に入っているだけでも全然理解が違いました。
AdaGradよりもモーメンタムを使った方が良いケースが紹介されているなど、実践を通した中での理論を厳選して紹介しているような本です。
性能評価のリグレット解析が良く分からなかったので、また勉強したら戻ってこようと思います。機械学習の本棚に置いておきたい一冊です。
