ICML読む会資料 (鹿島担当) 教師ナシ の 構造→構造 マッピング 読んだ論文: Discriminative Unsupervised Learning of Structured Predictors Linli Xu (U. Waterloo) , … , Dale Schuurmans.

Slides:



Advertisements
Similar presentations
はじめてのパターン認識 第1章 第4グループ 平田翔暉. パターン認識 パターン認識 o 観測されたパターンを、あらかじめ定められ たクラスに分類すること クラス o 硬貨: 1 円玉、 5 円玉、 10 円玉、 50 円玉、 100 円玉、 500 円玉 o アルファベット: 26 種類 o 数字:
Advertisements

G 問題 コードアート オンライン 原案:西出 ライタ:伊藤 テスタ:西出. 問題概要 0 大きさのさまざまな n 個の円に多角形 m 個を入れら れるか判定する問題 0 ただし、同じ円に複数の多角形を入れることはでき ない 0 もし、入れられる場合は、辞書順最小の入れ方を出 力 ① ② ③ ① ②.
大規模コーパスから獲得した 名詞の出現パターンを用いた 事態名詞の項構造解析
顔表情クラスタリングによる 映像コンテンツへのタギング
Building text features for object image classification
極小集合被覆を列挙する 実用的高速アルゴリズム
電子情報工学科5年(前期) 7回目(21/5/2015) 担当:古山彰一
ニューラルネットのモデル選択 村田研究室 4年  1G06Q117-5 園田 翔.
人工知能特論 6.機械学習概論とバージョン空間法
Pattern Recognition and Machine Learning 1.5 決定理論
実験 関数・記号付き文型パターンを用いた機械翻訳の試作と評価 石上真理子 水田理夫 徳久雅人 村上仁一 池原悟 (鳥取大) ◎評価方法1
部分木に基づくマルコフ確率場と言語解析への適用
芦田尚美*,髙田雅美*,木目沢司†,城和貴* *奈良女子大学大学院 †国立国会図書館
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
生命情報学入門 機械学習を用いたタンパク質の分類法 2011年6月7日
模擬国内予選2014 Problem C 壊れた暗号生成器
Semi-Supervised QA with Generative Domain-Adaptive Nets
自閉症スペクトラム障害児と定型発達児の識別に関する音響特徴量選択の検討
発表日:平成15年4月25日 担当者:時田 陽一 担当箇所:第3章 誤差評価に基づく学習 3.1 Widrow-Hoffの学習規則
パターン認識とニューラルネットワーク 栗田多喜夫 2018/11/8 早稲田大学大学院理工学研究科講義.
情報処理3 第5回目講義         担当 鶴貝 達政 11/8/2018.
サポートベクターマシン によるパターン認識
識別子の命名支援を目的とした動詞-目的語関係の辞書構築
[IBIS2011 企画セッション プレビュー] 大規模最適化および リスク指向最適化の最新解法
決定木とランダムフォレスト 和田 俊和.
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
Hough変換 投票と多数決原理に基づく図形の検出
人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅.
利用関係に基づく類似度を用いたJavaコンポーネント分類ツールの作成
Online Decoding of Markov Models under Latency Constraints
ICML2006勉強会 2006年7月29日 局所フィッシャー判別分析 東京工業大学 計算工学専攻 杉山 将.
あらまし アンサンブル学習の大きな特徴として,多数決などで生徒を組み合わせることにより,単一の生徒では表現できない入出力関係を実現できることがあげられる.その意味で,教師が生徒のモデル空間内にない場合のアンサンブル学習の解析は非常に興味深い.そこで本研究では,教師がコミティマシンであり生徒が単純パーセプトロンである場合のアンサンブル学習を統計力学的なオンライン学習の枠組みで議論する.メトロポリス法により汎化誤差を計算した結果,ヘブ学習ではすべての生徒は教師中間層の中央に漸近すること,パーセプトロン学習では
教師がコミティマシンの場合の アンサンブル学習
卒論の書き方: 参考文献について 2017年9月27日 小尻智子.
音響伝達特性を用いた単一マイクロホンによる話者の頭部方向の推定
訓練データとテストデータが 異なる分布に従う場合の学習
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
Internet広域分散協調サーチロボット の研究開発
Data Clustering: A Review
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
サポートベクターマシンを用いた タンパク質スレッディングの ためのスコア関数の学習 情報科学科4年 81025G 蓬来祐一郎.
Nightmare at Test Time: Robust Learning by Feature Deletion
顔特徴点移動量・点間距離変化量の組み合わせに基づく顔表情認識
論文紹介: “Joint Embedding of Words and Labels for Text Classification”
Number of random matrices
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
法数学のための 機械学習の基礎 京大(医) 統計遺伝学分野 山田 亮 2017/04/15.
教師がコミティマシンの場合の アンサンブル学習
サポートベクターマシン Support Vector Machine SVM
オブジェクトの協調動作を用いた オブジェクト指向プログラム実行履歴分割手法
「ICAによる顔画像特徴量抽出とSVMを用いた表情認識」
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
HMM音声合成における 変分ベイズ法に基づく線形回帰
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
人工知能特論II 第8回 二宮 崇.
メソッドの同時更新履歴を用いたクラスの機能別分類法
1ーQー18 音声特徴量抽出のための音素部分空間統合法の検討
分枝カット法に基づいた線形符号の復号法に関する一考察
欠陥検出を目的とした類似コード検索法 吉田則裕,石尾隆,松下誠,井上克郎 大阪大学 大学院情報科学研究科
Webページタイプによるクラスタ リングを用いた検索支援システム
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
グラフ-ベクトル変換を用いたグラフ構造表現による一般物体認識
Normalized Web Distanceを用いた音声認識の誤り訂正法 301-4in
雑音環境下における Sparse Coding声質変換 3-P-49d
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
教師がコミティマシンの場合のアンサンブル学習 三好 誠司(神戸高専) 原 一之(都立高専) 岡田 真人(東大,理研,さきがけ)
Presentation transcript:

ICML読む会資料 (鹿島担当) 教師ナシ の 構造→構造 マッピング 読んだ論文: Discriminative Unsupervised Learning of Structured Predictors Linli Xu (U. Waterloo) , … , Dale Schuurmans (U. Alberta), In proceeding of ICML2006

この論文では、教師ナシで、構造→構造のマッピングを学習する方法が紹介されます この論文の鑑賞ポイント 「構造→構造マッピング」は最近流行っている話題です。 でも普通、教師アリです。 じゃあ、教師ナシにするって一体どういうこと!? このお話の流れ 背景: 構造→構造マッピング問題 問題設定: 教師ナシ構造→構造マッピング問題 アプローチ: 「教師ナシSVM」の一般化による解法の提案

構造→構造マッピング問題は、構造データを入力として、構造データを出力する関数を求める問題です 品詞付け 単語列→品詞列のマッピング 構文解析 単語列→構文解析木のマッピング

構造→構造マッピング問題は、分類問題の一般化になっています 構造→構造マッピング問題は、多クラス分類問題の、クラスがものすごくたくさんある版 入力 X 出力 Y 2クラス 分類 構造 データ {+1, -1} 多クラス 分類 {1,...,K} 構造 マッピング 構造 データ

この論文は、著者が以前より提案している教師ナシ分類の手法を、自然に一般化したものです コレとコレが分かれば大体わかる 世の中の流れ 一般化 < 一般化 < 2クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 < 一般化 < 教師ナシ 2クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

まず、近年の教師アリ分類学習の発展について復習します 世の中の流れ 一般化 < 一般化 < 2クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 < 一般化 < 教師ナシ 2クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

教師アリ2クラス分類問題 を解くSVMは、部分構造を使った特徴空間において、正例と負例とのマージンを最大化するように学習します 構造をもったデータは、含まれる部分構造を使った特徴空間中の点として表現される この空間で正例と負例を最もうまく分ける(=マージン最大の)平面をみつける 部分構造を使った特徴空間表現 +1 +1 -1 +1 -1 マージン -1 -1

教師アリ多クラス分類問題 を解くSVMは、部分構造とクラスを使った特徴空間において、正解と不正解とのマージンを最大化するように学習します 構造をもったデータとクラスラベルの組は、含まれる部分構造とクラスラベルを使った特徴空間中の点として表現される この空間で正解と不正解を最もうまく分ける(=マージン最大の)平面をみつける 正解 部分構造とクラスを使った特徴空間表現 & 不 正 不正解 不 不 マージン 不 &

教師アリ構造マッピング問題 を解くSVMは、入力と出力の部分構造を使った特徴空間において、 正解と不正解とのマージンを最大化するように学習します 構造をもったデータとクラスラベルの組は、含まれる部分構造とクラスラベルを使った特徴空間中の点として表現される この空間で正解と不正解を最もうまく分ける(=マージン最大の)平面をみつける 正解 & 入力と出力の部分構造を使った特徴空間表現 不 正 不 不 マージン 不正解 不 &

近年著者が提案している教師ナシ分類法の発展に沿って、 この論文の成果をみていきます 世の中の流れ 一般化 < 一般化 < 2クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 < 一般化 < 教師ナシ 2クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

近年著者が提案している教師ナシ分類法の発展に沿って、 この論文の成果をみていきます 世の中の流れ 一般化 < 一般化 < 2クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 < 一般化 < 教師ナシ 2クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

教師ナシ2クラス分類問題 を解くSVMは、全ての正例と負例の割り当ての中から正例と負例とのマージンを最大化するように学習します ただし、正例と負例が大体半々になるような制約のもとで 部分構造を使った特徴空間表現 マージン最大 +1 +1 -1 +1 -1 -1 -1

教師ナシ多クラス分類問題 を解くSVMは、全ての正解と不正解の割り当ての中から正解と不正解とのマージンを最大化するように学習します ただし、各クラスが大体 1/(クラス数) になるような制約のもとで マージン最大 正解ってことで 部分構造とクラスを使った特徴空間表現 & 正 不 不正解ってことで &

教師ナシ構造マッピング を解くSVMは、全ての正解と不正解の割り当ての中から正解と不正解とのマージンを最大化するように学習します ただし、各部分構造の使用数が均等になるような制約のもとで マージン最大 正解ってことで & 入力と出力の部分構造を使った特徴空間表現 不 正 不 不 不 不正解ってことで &

教師アリSVMは2次計画であるのに対し、 教師ナシSVMは半正定値計画(SDP)になります 2値分類の場合でみてみる パラメータ w だけでなく、yについても最適化する クラスが均等になるような制約をいれる SDPに落ちる primal dual dual primal

性能はよさそうですが、たぶん、かなり遅いです 実験に使っているデータ小さい!→ たぶんムチャクチャ遅い! synthetic: 2状態2値のHMMから長さ8の配列を10個 protein: 長さ10のアミノ酸列を10個 提案 手法 既存 手法 小さいほうが性能イイ

この論文では、教師ナシで、構造→構造のマッピングを学習する方法が紹介されました この論文の鑑賞ポイント 「構造→構造マッピング」は最近流行っている話題です。 でも普通、教師アリです。 じゃあ、教師ナシにするって一体どういうこと!? このお話の流れ 背景: 構造→構造マッピング問題 問題設定: 教師ナシ構造→構造マッピング問題 アプローチ: 「教師ナシSVM」の一般化による解法の提案

考えうるネタ: 高速化 「パーセプトロン化」できるかな? SVM (2次計画) 遅い → パーセプトロン (オンライン逐次)で速くする SDP遅すぎ → パーセプトロン化など逐次学習化できれば速くなるかも?