Parabola JournalプログラミングMachine Learning

Subgroup DiscoveryとPython Orangeで遊んでいた

 
Machine Learning Advent Calendar 2013の一環で書いてます.動かしてみるつもりだったんですが,諸般の事情で動かなかったものもあったりして・・・.機械学習関係で比較的メジャーなタスクは分類と回帰だと思うのですが,RのEcdatパッケージに含まれているHousing data(data(Housing)で使う)を線形回帰してみます.

入力
output

出力(回帰直線を重ねたもの)
output_line

わーい嬉しい.まぁ細かいところを見てみたらこのデータに線形回帰を突っ込むのがそもそもどうなのか,という問題はありますが,別に2次の項を入れた曲線で近似したところでどうこうなる問題でもないでしょう.そこで,結局横軸(x: lotsize)と縦軸(y: price)がダメなんでしょ?という話を考えたい.いえ,別に積極的に考えたくはないのですが.あと問題にもよりますが.

なんとなく線形回帰ダメっぽいという話からすると,このグラフ(軸のとり方)がそもそもあかんのや,という話を考えるしかないでしょう.別にどこかの特徴空間に写像してもらって,うまく回帰するならそれはそれでもちろんいいですけどね,そのあたりはよく分かりません.Housingデータはもともと,price, lotsize, bedrooms, bathrms, stories(謎), driveway, … と他にも属性ありますので,そのあたりもコミコミで計算したらもっといい感じの回帰式にはなると思います(何がいい回帰式なのか,はとりあえず考えない).

  1. とりあえずデータがあります(離散値,整数値,カテゴリ値,二値,etc.で構成される)
  2. なんか処理したい(←今ココ
という状況を思い浮かべていただきたいと思います.こういう状況になるとさすがにパッケージにぶち込んで\(^o^)/というわけにはいかないので,データの整形・特徴抽出・正規化などなどをやる必要があるかもしれません.結局データ事態が言うほどキレイでない,というのが問題なんですね.データの生成がそもそもi.i.d.でないとか,いろんなデータの種類が混じっているとか,要因はいろいろでしょうが,なかなか難しい.

全部ごちゃまぜのデータを扱うのももちろんそれはそれで良いのですが,出来ればなんかキレイなデータにしてから処理した方が,扱いやすくなります.例えば先にクラスタリング(何でもいいので,レコード間の距離か類似度を決めて,例えば階層クラスタリングにぶち込んでグループ分け,みたいなことする)などの手法をかけたデータの前処理を職人芸でやって,さらに機械学習の諸手法で大域モデルを学習すれば,そのグループの中での精度は高くなるでしょう,仮にただの線形回帰だとしても.

ここでようやく表題なのですが,Subgroup Discovery(日本語訳不明)というのはデータマイニングの諸手法の一つで,簡単に言えば,与えられたデータの中で特徴的な部分集合を発見してあげる手法の総称です.(教師あり学習+教師なし学習)/2みたいなポジションです.なんでかというと,目的変数(target; 決定木とかでも決めているあれ,いわゆる目標変数)を決めた上で,マイニングとルール生成と評価を繰り返していくからでしょうね.もちろんこういう手法だけでなく,RやPythonの可視化(Numpy/Scipy->Matplotlib), Wekaほげほげを利用して可視化しながらデータをよーく眺めるというのが,まず最初にやる作業となるとは思いますが,前処理にデータマイニング処理使ってもいいじゃないか.そこで今回はPythonのOrangeという環境でそれをやろうとしました,という話です.データマイナーを名乗るための道のりは長く険しいですね.

パッケージとしてはよく分かりませんが,Python Orange用(http://kt.ijs.si/petra_kralj/SubgroupDiscovery/),Rapid Miner用(http://kt.ijs.si/petra_kralj/SubgroupDiscovery/rm.html),R用(詳細未確認)(http://www.subgroup.cc/)をとりあえず見つけました.

特徴的な部分集合とはどういうことか

線形回帰の例を続けます.全体の回帰式Y_{\mathrm{Price},i} = A + B X_{\mathrm{lotsize}, i} + \varepsilon_iが得られているとします.次にやることは,ある部分集合D (つまり,subgroup)を検索します.この部分集合Dにおいて回帰式を学習すると,例えば別の回帰式Y_{D,\mathrm{Price},i} = A_D + B_D X_{\mathrm{lotsize}, i} + \varepsilon_iが得られるとします.もし,2つの例えば回帰直線の傾きが統計的に有意に異なるなら(つまり帰無仮説H_0\: B_D = B)をチェックする.もし有意に異なるなら,今見ている部分集合Dを,何らかの特徴によって全体と異なる部分だ,と見なす(´・ω・`)

部分集合の作り方: 簡単なイメージ

例えば離散値属性がある場合(性別: 男/女,年齢層:10代/20代/30代/…),これをそのまま条件としたサブグループというのを作ることができる.
  • サブグループ1: 男性
  • サブグループ2: 10代男性
  • サブグループ3: 10代男性既婚
ある条件が有意に異なるサブグループを発見した場合,さらに条件を加えて条件1∧条件2,条件1∧条件2∧条件3,…と頑張って条件を難しくしていく.この探索空間はデータベースの次元(属性数,か)が上がると当然のように手に負えなくなるので,近似的な探索(例えばグループを表現するルールの精度やカバー率を定義して,その値が大きいものから決められた個数だけ発展的に検索するなど.要するにビーム探索)をすることも.というか,基本的に全列挙は諦めていると思う.

上のHousingデータの属性pref_area(Yes/No二値)を例えば対象とすると,Yes(好ましい)とNo(好ましくない)という+/-がデータ中の各レコードに付いていると考えることができる.次にやるのは上で考えた空間の探索で,簡単な規則から難しい規則を生成して,空間を走査していく.

ある条件(ルール)が得られた時,ルールで表現されるレコードのうち,pref_areaが,例えばYesが75%以上であれば,そのルールを特徴的な部分を表現していると見なす.アイテム集合発見における出現割合(# of occurrences / The entire size of DB)みたいなもの.もちろんそういう評価の仕方だけでなく,いろんな評価があってもいいのだけど,空間内のルールと評価関数においてdownward-closure propertyが成立していた方が,探索は簡単になる.

必要なもの

真面目に考えると,Subgroup Discoveryを適用するには次のことを決める必要がある.
  • 何を対象として集合を分けるのか
  • 決定木作るときの対象属性と同じ.Subgroup Discoveryは基本的に1つの対象変数のみを扱う.2つ以上を同時に扱うような拡張は,一部でExceptional Model Miningと呼ばれる.
  • そのようにしてサブグループを表現するのか
  • 命題論理式,述語論理式,数値区間,その他いろいろを使う.定式化的には探索空間を効率的に検索するための精密化演算子が上手く定義出来,下で述べる基準について単調性が保証される方が望ましい.
  • サブグループ選択のための基準
  • ルールを評価するために使う.カバー率や頻度,エントロピーなど.
  • 探索をどのように効率化するか
  • いくら枝刈りを頑張っても全列挙はだいたいしんどいので近似探索手法も同時に使う.

Orangeで動かしてみる

Subgroup Discovery用のWidgetをインストールしたOrangeにデータをぶち込む
Orange_1

見たい場合はData Tableに通す
Orange_2

インストールしたSubgroup Discovery Widget群を使って
Orange_3

Subgroup Discoveryを動かすと
Orange_4

楽しい✌(‘ω’✌ )三✌(‘ω’)✌三( ✌’ω’)✌ここでは相関規則系のSubgroup Discovery手法を利用しているので,出てきているサブグループの記述もそういう形です.(条件→嬉しい✌(‘ω’✌ )三✌(‘ω’)✌三( ✌’ω’)✌)とりあえず家賃400(単位はポンド・・・か?)あたりでいいらしいです.
Orange_5

データマイナーへの道のりは長く険しいですねぇ(二度目).機械学習手法を用いるとき,自分のデータがどういうデータなのかに注意をはらって,楽しい学習ライフを送りましょうということで,ひとつ.

参考文献
  • F. Herrera et al. An overview on subgroup discovery: foundations and applications

参考リンク



Scala

Scala用の機械学習関係ライブラリ関係を調べてみる

 
Scala Advent Calendar 2013の一環として記事を書いてます.内容としてはScala Advent Calendar 2011の記事(Scalaは機械学習に使えるかな?)の続きみたいなものかな・・・.

まずScalaからJava系のライブラリ各種を呼び出す場合ですが,Scala Days 2013のトーク : Scalable and Flexible Machine Learning With Scala (http://parleys.com/p/51c2e0f3e4b0ed877035684f)や,関係のスライド Scalable and Flexible Machine Learning With Scala @ LinkedInあたりをまず見てみます.
 
要するにMapReduceの処理にどうやって持っていくかという話になるのですが(暴論),紹介されているScalding(Github: https://github.com/twitter/scalding)などのように,ScalaでDSLの実装をして,裏ではJavaライブラリやScalaで書かれた部分に頑張ってもらう,と.ScalaでDSLという話はScalaスケーラブルプログラミングにも出てくる程度には普通の話だと思うので,まぁ普通に嬉しいですね,ということになります.
 
自前で実装するという話をもう少し見ていくと,メソッドを演算子のような形で使うことで(この表現は怪しい?)普通に自作クラス間での計算式を賭けるようになるので,機械学習で使うような計算(線形代数: ベクトル,行列, 確率統計: 分布からのサンプルその他)を実装していくという方向になります.2年前に調べたときはScalalaという線形代数(Linear Algebra, LA)のライブラリ開発がされていましたが,今はbreezeというプロジェクトになりました.

Github: https://github.com/scalanlp/breeze

ScalaNLPというNLP(自然言語処理; 人間が読み書きや話しに使う言語で書かれた文書や,文書の集まり(コーパス)をコンピュータで処理すること. ibisforestさんより)のための開発の一環でしょうか.

Breeze is a library for numerical processing, machine learning, and natural language processing. Its primary focus is on being generic, clean, and powerful without sacrificing (much) efficiency.

 
Scalalaの時代はそこまでドキュメントが整理されていなかったですが,最近ではMatlabやPythonでのNumpy/Scipyと比較してどうこう・・・Breeze Linear Algebra · scalanlp/breeze Wiki · GitHubというページが整備されていて,普通の行列計算やベクトル計算をそのまま書き写すことが一応出来るでしょうか.

なぜ一応と言っているかというと,Pythonでいうndarrayの機能が全てないようなんですね.全て無いこと自体は欠点ではないですが,平たく言うと多次元配列をそんなに上手く扱えないようので,そのあたりが本当にMatlabやNumpy/Scipyからの書き写しが出来るのか疑問に思っています.というかできなかったんだよ.

val c = DenseMatrix.zeros[Double](n,m) 
c(::, 2) 

このようにそれっぽく要素アクセス出来るので,たぶんちゃんと調べたらもう少し使い方分かるような気がするのですが.上の対応表ページで紹介されているSpecial “reduction” functions.とか面白いのですけどね.肝心の性能ですが

Breeze uses netlib-java for its core linear algebra routines. This includes all the cubic time operations, matrix-matrix and matrix-vector multiplication. Special efforts are taken to ensure that arrays are not copied.

ということらしいです.僕は詳しいことは分からないので,そのうち実験したいです.DenseMatrixと他のMatrixの違いとか.

breeze自体は上に書いた通り,自然言語処理関係の一部分で開発されているようなので,線形代数計算以外にもパッケージがあります.機械学習関係(breeze-learn)や可視化関係(breeze-viz)があります.一番ドキュメントが整理されているのは線形代数関係(UserGuide: https://github.com/scalanlp/breeze/wiki/UserGuide)だと思いますが.ホームページ上ではEpicというパーサ(文を区切ります)を作ってるっぽいですが,正体は謎です.

ただ,ScalaDocで吐き出されているAPIページを見てみると,breeze.classify(分類器), breeze.corpora(コーポラ), breeze.data(データ関係,おそらくファイルとか読み込んだりする用), breeze.inference, breeze.stat, breeze.optimize(推論,確率統計関係,最適化関係)とかいろいろあるんですよね.まぁ開発中なんでしょ,きっと.

ちょっと試したい場合,build.sbtにライブラリ依存を書いて使って見て下さい.

scalaVersion := "2.10.2"

libraryDependencies ++= Seq(
  "org.scalanlp" % "breeze_2.10" % "0.5.2",
  "org.scalanlp" % "breeze-viz_2.10" % "0.5.2"
)

resolvers ++= Seq(
  "Sonatype Snapshots" at "https://oss.sonatype.org/content/repositories/snapshots/",
  "Sonatype Releases" at "https://oss.sonatype.org/content/repositories/releases/"
)



さて,もう少し別の方向にDSLが発展した(と言っていいのか,ちょっと自信がないですが)ものにOptiMLという開発中のものがあります(Stanford PPL).これは全体的にもっと大きなフレームワークの一部だと思いますが,機械学習用のDSLを目指しているように見えます.

OptiML is a domain-specific language for machine learning written in Scala. This project primarily explores how scalable data and task parallelism can be implicitly extracted out of high level abstractions such as vectors, matrices, factor graphs, decision trees, and neural networks.


現在はアルファ版(OptiML — Welcome)で遊ぶことができます.結構容量あります.Scalaで書かれているものを.degファイルで書かれたものにコンパイルして実行します.大きなフレームワークってどういう話かというと,OpenCLやCUDA使ったり,C++と絡ませたり,そういうことです.全然Scalaで完結してないじゃん・・・.

それはともかく,サンプルとしてGDA(って何?), ロジスティック回帰,ナイーブベイズ,RBM,kNNのscalaファイルが入ってます.余計な部分を省いてちょっと見てみます.

val x = readMatrix(args(0))
val y = readVector(args(1)).t

val theta = DenseVector.zeros(x.numCols)
// gradient descent with logistic function
val alpha = 1.0
val w = untilconverged(theta, maxIter = 30) { cur =>
  val gradient = sum((0::x.numRows) { i =>
    x(i)*(y(i) - sigmoid(cur *:* x(i)))
  })
  val z = cur + gradient*alpha
  z
}

ってまぁ上のbreezeみたいな計算,中で書いてます.普通だった.んでoptimlの中身に上のbreezeのコアで使われているっぽいですがnetlib-java使ってるようです.あらあら.もう少しの中身はExampleページをどうぞ(Example: OptiML — Examples).実際中身でどんなことしてるか,よくわかりませんでした.


と,ここまで順番にbreezeとOptiMLを見て見ましたけど(書いてないですが,breeze.linalg使って一応ナイーブベイズまで書いたんだよ…),正直なところ例えばMatlabからScalaに,PythonからScalaにと,移行してくるほどかというと,全然そうでもないですね.また来年に期待しましょう.もう少し真面目に,ドキュメント/API読んでみようかなぁ.

Parabola Journal

[日記]学生生活で必要そうなメタ的なものについて


就活したことない Advent Calendar 2012のエントリです.TwitterのIDは@taki__taki__です.2度目です.博士後期課程の1年です.博士の奨学金が始まりました.ありがてぇ…ありがてぇ….博士課程学生になって2ヶ月+αぐらい経過したので,学生生活で必要そうに感じたメタ的ななにかについて書きました.(もはや後輩に向けて勧誘すらしてない…)

健康と嬉しい

もはや,説明の,必要も,ない.体力は気づかないうちに落ちていくものなのネ…

時間を自分で管理できるとうれしい

博士課程は授業がない場合が多いと思うので,基本的に一週間のうちのほとんどを自分の裁量で活動出来るはずです.そのあたりは自分で自制して管理出来ると,全体的に幸せになれると思います就職活動をしていても同じ,もちろん就職した後も,自分の貴重な時間を上手く回せるかどうかは大事.僕はここ3ヶ月ほど自分の自制には失敗していましたが,ようやく整って来ました.今まで
  • 月: 1日自由
  • 火: 6限目講義(18:15-19:45)
  • 水: 3限目講義(14:45-16:15)
  • 木: 1日自由
  • 金: 研究室セミナー(週1)
という感じで生活していましたが,今は火と水まで1日自由になりました.ヤバイ.遊んでるときもあれば,遊んでないときもあります.定時の時間帯に帰ることもあれば,深夜まで研究室にいることもあります.こういった波のある生活は余計に労力ばかりかかるのだなぁと学びましたナ規則正しい生活,とても大切.

ちゃんとした文章を書けるとうれしい

自分自身に突っ込まないとダメな気がしますが,文章を書く機会が多くなります.ちゃんとした文章を書けるようになる必要がありますね.
  • 諸々の報告書
  • 研究計画書(学振,大学内のRA等,他奨学金,研究費申請,etc.)
  • 原稿(日本語,英語問わず)
文章作成の技術などは,結局書籍で学ぶのが一番効率が良いという説もあります.どんな方法で習得するにしても,文章を誰が読むのかということを想定するのは大事だとよく言われます.

理科系の作文技術 (中公新書 (624))
木下 是雄
中央公論新社
売り上げランキング: 675
どう書くか―理科系のための論文作法
杉原 厚吉
共立出版
売り上げランキング: 184096
しかし,いつもいつも文章を順調にかけたらそんなに楽なことはないわけで,文章をひねり出すことも大事になります.忍耐も集中力も必要なものもあります.

毎日研究室に行くと、まず目覚めのコーヒーを入れながら考える。一文も浮かんでこない。気がつくと昼である。(中略) 研究室に戻ると、晩御飯をどこで食べるかについての議論を他の学生としなければならない。やっと食事が済むと再びコーヒーを飲んだ後、コンピュータに向かう。英語の辞書を片手に文章を一行書いては、読み直して意味がわからず消去、こんなことを何度か繰り返すともう深夜近くである。ついに、「英語圏の研究者は楽でいいな。高校の先生が『理系の人こそ英語が重要』といっていた意味をやっと認識したよ。また明日やろう」といった一応の結論を得て家に帰るわけである。
息子のエッセイ 大学生活・勉強編(博士時代)

というような苦労が時には必要な場合も,怖いだが避けられない.

コミュニケーション能力が高いとうれしい

id:kanojikajino氏が書いてくれました
就活してない博士課程がコミュニケーションを取る必要がある相手といえば,だいたい
  • 研究室のスタッフ(教授,准教授,助教,秘書さん,etc.)
  • 研究室の先輩(いる場合)
  • 研究室の同期(いる場合)
  • 研究室の後輩(必ずいる!!!!1111)
あたりになるのでしょうか.先輩がいない場合はあっても,後輩がいないというのは結構レアだと思います(学部学生を取っていない場合を除く).どうしても博士課程に進むと同級生が少なくなってしまうので,いろんな場所に出ていくのは重要になってきます.こうしたとき,博士課程の学生といえども,コミュニケーション能力が問われることになりますね就職活動をしていてももちろん同じ.

ところで,研究室に引きこもってるようなイメージがある博士課程学生の,どこでそんなにコミュニケーション能力が必要になるのか?と思われる方もいるかもしれないですが,意外と必要なんですよ.
  • 例えば夏の学校(???? summer school)的な行事に参加する
  • 研究会・学会発表に行く
  • 企業の方と一緒に研究する
  • 勉強会に行ってみる
などなど.こういったものは研究を促進させてくれる上に,ヤル気を充填してくれて,さらにアイデアが降ってきて人脈が増えるといった効果あるので,実際こういうものを毎月,または季節ごとの目標にして生活していくのは,長い博士課程で中だるみしないためには効果的だと聞きましたヨ(伝聞)気合と惰性で生きていくのに,博士課程も人生も長すぎる気がする.

英語が出来ると凄く助かる

少なくとも読めて書けないとイカンな…人のことは言えない.

チャンスを逃さない運と実力が必要になるときも

時々CMで,「じゃあいつ始めるか…,今でしょ!」というセリフを聞きますが,これは博士課程だけではなく,いろんな人に成り立つことだと思います.将来に,その能力が必要になったとき,そのときに後悔してもどうしようもない,なんてことはよくあるでしょう.だからその時に備えて,今から始めておかないといけません.明日できることを明日に先送りしていくのはいいのですが,それを続けていると,どんどん後ろの方にやらないといけないことだけが貯まっていってしまいますそれでも原稿を書くとなれば,締め切りギリギリまで引き伸ばしてしまういきものなのだが….今できることは今のうちに消化するように少しだけ心がけると,いろいろ幸せになれそうです.

例えば,明日英語を話さないといけないような状況になったとき,やはり今日明日で対応するのは難しいのですナ.将来そのような状況にならないためにも,今から準備しておく必要があると思うのです.

例えば,留学したいと思ったとして,たまたま機会がやってきたとします.応募すれば可能性があります.こういうときに,「あーでもやっぱり英語だと…」とか「あーでも実際に行くのは…」とか言い出さずに,やってしまうという選択肢が取れるように備えておけばもちろん全部が全部,事前に備えておくのは当然ムリなのではあるが…,何かいいことが返ってくることがあるかもしれません.

最後に,そういったチャンスはどうやったら降ってくるのかという話について考えたいところです.これは僕が個人的に思うに,何か叶えたいことを広く公言しておくことでしょう.例えば教授に直接言ってみたり(どこそこに行きたい,なになにがしたい),TwitterやFacebookなどで常にアピールしてみたり.意外な場所で誰かが見ていてくれたり,覚えてくれていたりして,効果あるのですヨ.

Parabola Journal

[日記]思えば遠くまで来てしまったなぁ


就活したことない Advent Calendar 2012のエントリです.TwitterのIDは@taki__taki__です.博士後期課程1年になりました.最近研究がはかどっていないので半分ぐらい現実逃避のために書いているらしいです.あとこの記事は基本的に理系・情報系のことしか想定してないです.ちょっとでも分野が変わると,当然思うことも変わるでしょうしね.そもそも博士課程にいる自分が就活のことを真剣に書くのは難しいというか無理なような気がするので,少し考えて,やはり進学のことを書いてみようと思います.僕もすでに進学してしまった立場の人ですし

いつ頃から進学を意識するのか

最初の方で書いていた@caesar_wanyaさん( 進学か、就職か – あしたからがんばる ―椀屋本舗 )や@yonetaniryoさん( 就活したことない話 – おいしいお米の話 )らのように,どういう経緯で進学を選択したかはともかく,実際に進学している人は,博士課程という得体のしれないものをぼんやりと意識しながら生活しているように思います.僕の場合については後述します.特にM1の冬になる頃には就活の時期がやってきますので,その影響もあるでしょうかね僕の周辺の年代だと,建前上12月1日が解禁.もしD1でDC1を狙いに行くのであれば,この時期には成果が出ていないといけない,僕は落ちました

なぜ進学したくなるのか

これを言語化するのはとても難しいと考えています.もちろん,学部でやる卒業研究や,修士でやる研究から研究を続けてみたくなった,といった素朴な欲求や,就活失敗したので博士で自分を見つめなおすなど,どんなきっかけでも実際は進学する人は進学してしまうのでしょうが….目的を明確に持ちなさいとは言われると思いますが,明確に持ったからといって,言語化したからといって,何も偉いわけではないですから.自分で考えた研究テーマを自由に突き詰めていくというのは,なかなか言語化しづらい快感ですしね.

1つの要因として,自分の周辺の人から影響を受けるというのがあるのではないかと考えてます.自分の周辺に博士課程の人がいる場合といない場合で,結構大きく違うと思います自分の場合,B4で来た時に日本人のドクターが複数人いるというおそらく珍しいケースだった.自分の所属する研究室に,特に日本人の博士学生がいる場合のほうが,博士課程の生活というのは当然イメージしやすくなりますから,進学する確率も多少上がるのではないでしょうか上がると言っても1厘ぐらいでしょうけど…

僕自身の考えを端的にまとめておくと,ある程度意識した人なら学部の頃から研究したり,論文書いたりしていると思います.ですので,とりあえずどんな場所でもいいので自分の研究を発表するという経験をしてから考えるのがよいと思います.研究して,論文を書いて,外部で発表するまでのプロセスを一度は体験してみて,もう一度やってみたいとか,これをまだまだやりたいと思うのであれば進学すればいいのではないでしょうか.博士課程の仲間になる人達を僕自身は歓迎したいですし,お互い励まし合いながらでも頑張って生きたいものです.あ,もう書くことなくなった.

ここまでが就活したことないアドベントカレンダーに対する僕の考えになります.以下には,このブログを書いているときにぼんやりと下書きしていたことを書いておきます(捨てるとなんとなくもったいないので).

個人的にいつ頃博士課程進学を覚悟したか,昔話など

せっかくの機会だったので,もう少しだけ僕自身の状況について書いておきたいと思います.まずはじめに,僕はセンター試験を経由してくる普通の入試で大学に入ってきたわけではなく,学部3年生に編入学してきたということを言っておきたいです.それを前提にしておいていただくと助かります.

多くの大学生がいつぐらいに進学・就職ということを考えだすのかよくわかりませんが,早い人なら大学入ったあたりから,遅くても大学院の院試や学部卒の就職が始まるころではないかと思います,3年生ぐらいでしょうか.そう考えると大学に入ってから2年ぐらモラトリアムをしている期間があるのでしょうが,私の場合はモラトリアムの期間がほとんどなく,大学に馴染んできたところでいきなり院試を受けるという流れで大学院に来ました.ですので,あまり博士課程についてゆっくり考える余裕がなかったのですね.結果的にインターンシップを通じていろいろ考えた結果進学したのです.M1の夏にインターンシップに行っていたとき,一度強制的に大学から切り離されたのがいいきっかけになったのだと思います.今の大学に来てずっと感じていたおぼろげな何かから一度離れられたのですね.決してインターンが悪かったとかではなく,いろいろ考える中で,大学に帰ってくる頃には進学しようと思っていたというだけのことです.

高専生に対して

とりあえず大学来るのも楽しいのでオススメしています.専攻科から大学院に直接来るのもいいですが,学部に入ってくるのもそれはそれで楽しいですよ.

高専について今思うこと

よく思えば自分の出身高専についてこんなにいろんなことを考えたのは初めてかもしれません.今はだいぶ変わりましたけど,1年から微分積分の雰囲気を醸し出したり,微分方程式が出てきたり,ある意味むちゃくちゃな教育システムだったきがしますが,中学生を5年間拘束するシステムとしては今から考えると優秀だった気がします.自分は電子情報工学科というところにいたので,今よりもかなり電気電子よりのことばかり興味を持っていたのですが,そのおかげで大学に来てからむちゃくちゃ苦労することになってました例えばコンパイラとかオートマトンとか聞いたことがなかった

高専の教員は概ね一般科目チームと専門教育チームに分かれていまして,普通の高校相当の授業を一般科目チームが,専門科目と実験実習を専門教育チームが担当し,年が上がっていくごとに専門科目の比重が上がっていくというシステムでした.高専の教員は面白いことに教員免許を持っていなくても博士号を持っていればなれたりするため基本的に高校3年+短大2年の構成で,4年5年の担当は博士号が必要という噂がある.,ある意味大学のような教育を最初からずっと受けたり,自分の科の教員の部屋に入り浸って遊んだりできて,早くから専門科目に触れられたのは大きな財産になっています.

すごく変な経路で大学(院)に到達したことで,大学に来てから独学で学ばなければなかったり,不足分を補わなくてはいけなかったりしたことがたくさんありましたし,今もあるのですが,そういうのは研究活動していても同じことだと思うのです.新しいテーマを模索したり,新しい技術を学ぼうとすれば,必ず今の自分では対応出来ない範囲というところに踏み出さないといけないときが来ます.そういうときに助けてくれるのは,自分が今までやってきた基礎的な勉強と,それを通じて身に着けてきたメタ的な技術だったりするのではないかと思います時間とヤル気の管理とか,体調の管理とか,メタ的な学び方とかそういうの

決して高専のステマではない

あとがき

就活したことない Advent Calendar 2012,とても濃い記事が揃っていますので,僕も楽しみながら読みます.こういうことを博士課程の人や進学した人,就職した人,悩む人,決断した人が表明するというのはすごくいい機会ですよね.こんな無謀な企画における25人分の枠を確定させた@yonetaniryoさんの人望スゴイナー.

悩んだら周りの人に聞くのもいいですし,博士課程の人に聞いてみるのもいいですし,教員はなんていうかは人によって違うと思いますが…,悲しいけど最後に覚悟するのは自分なのよね.もし新しく博士課程進学の決断をする人がいたら,歓迎したいです.

Parabola Journal

[日記]制約充足問題についてのゆるふわな話

 
この記事はMachine Learning Advent Calendar 2012の12日目の記事として書いています.最初スカスカだった気がするのですが,いつの間にかガチ勢に囲まれてしまった気がして既に文章書くだけで怖いのですが,気のせいでしょうか.今日はゆるふわな話として制約充足問題についてやりますなぜMachine Learning Advent Calendarで書くのかというと本人も謎なのですが,当時は枠が開いていたので…

制約充足問題について

制約充足問題(CSP: Constraint Satisfaction Problem) [Wikipedia]とは,その名前の通り「こんな感じの条件1.,条件2.,…を全部満たしてくれることは可能ですか〜?」というような問いに関わる問題のことを言います.もうすぐ衆議院選挙がありますが,選挙の投票をするときに「政策1についてはこういう立場で〜,政策2についてこういう立場で〜.....を全部満たす議員さんが自分の選挙区にいるかな〜」みたいなことをぼんやり考えるようなことをやります.もう少し真面目な問題例としては,数独とかnクイーンとかがあります.

ミニ数独の例


  • どの行も数字が重複してはいけない
  • どの列も数字が重複してはいけない
  • どのブロックも数字が重複してはいけない

数独を解く



例えば,全部総当りしますもちろん普通に考えたらこんなこと当然しなくていいです.しかし4×4ぐらいならこれでも問題ないような雰囲気が少しだけありますが,こんな無茶なことしているといつかお姉さんみたいになってしまう気がします.


もちろん,普通に考えて無駄なことをしないようにバックトラックすればよいのです.



列方向を考えるとき,列方向に数値が重複してはいけないという制約を知っているので,バックトラックをしているとき,こんなことを考えています.



これを制約の数だけ行うと,そもそもチェックしなければならない数字というのがちゃんと少なくなるはずです.普通に数独を解いているときと同じことを,毎回やってあげればよいのですね.そうすれば最初みたいな無駄なことをしないでいいので,答えの探索が大分簡単になります.



真面目な制約充足問題の定義,解放の真面目な話を知りたい場合は,もちろん真面目な資料を読むのが良いです.制約充足問題自体は一般にはNP完全問題らしいですが,多くの場合で高速に解くことが可能らしいです.実際に高速に解いてもらうには,CSPソルバーというツールを使うのが一般的であります.

CSPソルバー: 制約充足問題を解くための道具

上で簡単なミニ数独を考えましたが,実際に制約充足問題を解く場合,自分でプログラムを書かなくても,便利なライブラリやツールがちゃんと公開されています.今回はCSPソルバー: Sugarを後ろで使いつつ,表面的にはScalaで書けるというおいしいライブラリであるCoprisを使ってみます.Scalaやってる人向けに言えば,必要なjarファイルを落としてきてsbtで管理するディレクトリのlibに入れておけばとりあえず使えます.以下のソースは基本的にCoprisのサンプルコードを借りてきました.

import jp.kobe_u.copris._
import jp.kobe_u.copris.dsl._

object MiniSudoku {
  def main(args: Array[String]) = {
    val puzzle = Seq(
      Seq(4, 0, 3, 0),
      Seq(0, 3, 0, 0),
      Seq(0, 0, 2, 0),
      Seq(0, 2, 0, 3))

    // ブロックの幅と数字の数		
    val (m, n) = (2, 4)
		
    // 4×4のマスでx(0,0)からx(3,3)までを整数値を取るべき変数として用意
    for (i <- 0 until n; j <- 0 until n)
      int('x(i, j), 1, n)

    // 行・列は全て異なる(Alldifferent)という条件を追加(add)する
    for (i <- 0 until n) add(Alldifferent((0 until n).map('x(i,_))))
    for (j <- 0 until n) add(Alldifferent((0 until n).map('x(_,j))))

    // ブロック内は全て異なるという条件を追加する
    for (i <- 0 until n by m; j <- 0 until n by m) {
      val xs = for (di <- 0 until m; dj <- 0 until m) yield 'x(i+di, j+dj)
      add(Alldifferent(xs))
    }

    // 既にpuzzleに埋まっている数値があればそれと一致(===)しなければならない
    for (i <- 0 until n; j <- 0 until n if puzzle(i)(j) > 0)
      add('x(i,j) === puzzle(i)(j))

    // 見つかったら出力
    if (find) {
      for (i <- 0 until n)
        println((0 until n).map( j => solution('x(i, j))).mkString(" "))
    }
  }
}		


[info] Running MiniSudoku
4 1 3 2                  
2 3 1 4                  
3 4 2 1                  
1 2 4 3 


中身はブラックボックス(確かSATの問題にしてる気がした)だとしても,自分の望む条件を書いてあげると,その答えを可能な限り頑張って求めてくれるというのは凄くいい話ですね.

宣言型と手続き型のはなし

制約充足問題を解いたときのように,普通に探索を考えていけば,その処理を手続き型で書くことは難しくない問題もたくさんあります.実際にC++やJavaでプログラムを書くわけですし,パラダイムはどうであれ手続き的に問題解決を目指します.

制約充足問題を手続き型で考える
  • 解空間を全列挙して進んでみる:アカン
  • 効率的な枝刈りを考える:制約の伝搬をする
  • ヒューリスティックを入れる:知らん
  • 諦める:この問題は実は解けない(解がない)!
しかし,ある程度,問題がしっかりと研究されていくと,その問題をメタ的に記述し,解いてくれるソルバーが開発されていく場合があります.こういった内部の細かいことを気にすることなく,もしくはそういったものに極力悩まされることなく

制約充足問題を宣言的に考える
  • 解の満たすべき性質である制約を記述してソルバーに投げる
という短いステップで問題が解けてしまうかもしれません.


機械学習/データマイニングは宣言型的な解決が出来るようになるだろうか 宣言型な考え方,どうせソルバーに投げるなら手続き型だ!っていうあら探しはやめろ!!!!

ようやくMachine Learning Advent Calendarの周辺まで戻って来れた気がします.最近研究されているようなされていないような(どれぐらいかは不明)話として,データマイニングや機械学習の問題は宣言的に書けるのだから,宣言的に解けたら嬉しいよね,というテーマがあります.近年の統計的かつ数学的に非常に高度化した(少なくとも僕の目からそう見える)話からすると,お前はいったい何を言っているんだ?と思われるかもしれませんが,

「あ〜○○くん,ビッグデータ用意したから何か使えそうな結果頼む」


みたいなことをもし言われたらどうでしょうか.こういう抽象的な問いでデータを持っている人がやりたいことって,まさに宣言型の手法が合っているのではないか効率的に解けるどうこうでいじめてはいけない!!!!!!あとそういう現実的な話でいじめるのよくない!!! と,そう思うのです.

  • あるお店での売上データを持ってきた,○日以上継続して売れていて,売上のピークが1年に4回あるような商品セットを知りたい
  • 損失関数を最小化するような,モデルのパラメータが欲しい

宣言っぽいと言えるような,言えないような….

まとめ

この記事では制約充足問題の基本的な話をしました.オマケで機械学習やデータマイニングで宣言的な解き方が出来るようになったら面白い,というよりもただ使うだけの人からするとわかりやすいよね〜という話を本当はちゃんとやろうとしたのですが思っていたより筆が進まず…やりました.今回は制約充足問題を基本的な部分で使いましたが,他にもSAT使ったり,もっと確率的な話をするためにベイジアンネットみたいなことをベースでやったり,まぁいろいろな人がいるんだなぁと思っていただいたら嬉しいなぁと思います.なお書いている人はこういう研究を一切していない模様.

記事を書くためにお世話になった土下座すべき参考文献一覧