Parabola Journal

情報と職業(4/11): NII宇野先生

 


午前中に健康診断を済ませて目が極端に悪くなっていないことを確認して一安心.(左1.2,右1.0で,今までずっと良かった右を左が抜いてしまった.たぶん左が測りミスで,実際両方1.0ぐらいまで悪化したのだろう.やれやれ.)
 
午後はNIIの宇野先生の話(2コマ分, 13:00-16:15).1コマ目の話はいわゆるPattern Miningに関する手法の話(宇野先生曰く「いかにしてF1マシンを設計するのか?」についての研究)で,資料としては宇野先生,そして北大の有村先生の書いている資料が参考になる.講演タイトルは実利用で超高速性を持つマイニングアルゴリズム

 
概ね4点(全て上の資料にある)技術の話で,


列挙アルゴリズムの解として出力される個数は最悪の場合,また難し目のセッティング(しきい値を小さくしてひたすら網羅する,など)をすると指数個に跳ね上がるので,最初の段階でオーバーヘッドとして余計なコストを払ったとしても,最終的に(全体として)高速化が有効になる,というのが列挙アルゴリズムのアイデア.もう1つのアイデアは逆探索で,考えているパターン言語の中で親が1つに決まるような精密化演算子を定義し,その全域木を辿ることで列挙する.

頻出集合の個数(アイテム集合でも順序木でも無順序木でもグラフでも)は一般にたくさーん出てくるので,それを圧縮する/制約をかけるということが研究としてたくさん行われている.アイテム集合の場合飽和アイテム集合と極大頻出アイテム集合がある.木やグラフの場合についてもあるかどうかは僕は知らない.もしくは頻度(更に一般化してinteresting measureが上からk位までのTop-k pattern miningをする).ちなみに飽和アイテム集合はデータベースを二部グラフ化したときの極大二部クリークに対応して,もしアイテム集合を多次元のものとする場合,二部グラフを一般化してk-partiteグラフのクリークを探索するとすると,もう少し複雑な解析も可能になる.必要かどうかはともかく.


第二部については(F1と比較すると大衆車の発明的な感じか)データ研磨に関する話.論文としては宇野先生が研究会等で発表しているものが参考になるだろうか.残念ながら自分の調べた限りではインターネットアクセス可能な文献はなさそうであるが・・・.

  • 宇野毅明, 中原孝信, 前川浩基, 羽室行信: データ研磨によるクリーク列挙クラスタリング(
    CiNii), 情報処理学会研究報告, AL:アルゴリズム研究会報告 2014-AL-146(2), pp.1-8.若しくは第92回人工知能基本問題研究会(SIG-FPAI)報告
  • (PDF直リンク)多様性の獲得に向けた次世代マイニング技術

本来データマイニングは「蓄えられたデータから何かを発見したい」という動機があったはずだけど,あるパターン言語(アイテム集合,木,区間,グラフ,・・・)を定めた問題設定を一度研究し始めると,方法論・アルゴリズムの開発にどうしても重みがいってしまい「本当にしたいことは何なの?」という観点から問題を眺めたときにつらいものがある,ということから研究されている話の様子.

基本的なアイデアは「アルゴリズムばっかり研究しないで,データ眺めてそっちの研究ももうちょっとやろう」っていう話という感じだろうか.本当は局所的に特別なもの・違っているものを発見する(余談: このlocal pattern miningという考え方は時々data miningと,globalなmodelを計算する(主に二条誤差最小化+正則化)機械学習手法との対比として語られることがある)のに,技術が進歩したお陰でアルゴリズムが頑張ってたくさん答え出して(出しすぎて)くれる.これをなんとかしたい,というアイデアの1つがデータ研磨.他に思いつく手法としては,クラスタリングとかconstrained mining, interactive miningあたりがあると思うけれども,基本的に大規模データにぶつけるとそういう手法は上手く動かないことが多いので,せっかく高速化された列挙アルゴリズムとその知見を使うことで,この問題を解決しよう,という試みのよう.

実際使う手法はクリーク列挙で,こう考えると列挙アルゴリズムの汎用性凄いっていう話になる.「だいたい似ている構造はちょっと変更してまとめてしまう」というデータ修正を積極的に行うことで,類似している列挙解をくっつけていくという逆転の発想がキーポイント.

うーん,面白かった.ちなみに来週は知能情報学専攻の教授になられた鹿島教授とのこと.