| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-04-18 14:55 ラベル付きグラフからのウォークの多項式時間学習 ○筒井淳平・有村博紀（北大）  COMP2008-6 |
|
| 抄録 | （和） | 本稿では，未知の歩行$\pi_*$をグラフの正例から学習する問題を考察する． ここでは，学習モデルとしてAngluinの質問学習モデル(Angluin, Machine Learning 2, 1988)を採用する。 任意のグラフ$G$は$\pi_*$が埋め込まれているとき，$\pi_*$の正例であるといい，それ以外のとき，$\pi_*$の負例であるという．所属性質問とは，任意のグラフを与えて、それが正例であるか，負例であるかを問うことである． 主結果として，辺が重ならないような（辺非重複）埋め込み写像だけを許した歩行のクラスに対して，未知の歩行を一つの正例と$O(m+n)$個の所属性質問から学習する多項式時間アルゴリズムを与えた．ここで，$m$は未知の歩行の長さであり，$n$は正例として与えられたグラフのサイズである． さらに，頂点が重ならないような場合と辺が重ならないような場合の両方のクラスで，未知の歩行を正負例だけから予測する問題は，DNF（積和形論理式）の正負例からの予測問題と同程度に難しいことがわかった． |
| （英） | In this paper, we study the problem of learning an unknown label sequence, called a walk, that is embedded in a collection of vertex-labeled graphs. We present a polynomial time learning algorithm that learns all walks $\pi_*$ from one positive example and using $O(m+n)$ membership queries, where $m = |\pi_*|$ is the size of the walk and $n$ is the size of the positive example, respectively. Based on prediction preserving reduction, we also show that the prediction problem for the class of walks from positive and negative examples of graphs under both of vertex-non-overlapping and edge-non-overlapping embeddings are as hard as the prediction problem of DNF (disjunctive normal form formulas) from positive and negative examples. |
|
| キーワード | （和） | グラフの推論 / 質問学習モデル / 所属性質問 / 多項式時間学習 / 正例 / / / |
| （英） | graph inference / query learning model / membership queries / polynomial time learning / positive examples / / / | |
| 文献情報 | 信学技報, vol. 108, no. 11, COMP2008-6, pp. 35-40, 2008年4月. | |
| 資料番号 | COMP2008-6 | |
| 発行日 | 2008-04-11 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2008-6 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-04-18 - 2008-04-18 |
| 開催地（和） | 大阪府立大学 |
| 開催地（英） | Osaka Prefecture University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-04-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | ラベル付きグラフからのウォークの多項式時間学習 |
| サブタイトル（和） | |
| タイトル（英） | Learning Walks from Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフの推論 / graph inference |
| キーワード(2)（和/英） | 質問学習モデル / query learning model |
| キーワード(3)（和/英） | 所属性質問 / membership queries |
| キーワード(4)（和/英） | 多項式時間学習 / polynomial time learning |
| キーワード(5)（和/英） | 正例 / positive examples |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 筒井 淳平 / Junpei Tsutsui / ツツイ ジュンペイ |
| 第1著者 所属（和/英） | 北海道大学大学院 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 有村 博紀 / Hiroki Arimura / アリムラ ヒロキ |
| 第2著者 所属（和/英） | 北海道大学大学院 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-04-18 14:55:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2008-6 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.11 |
| ページ範囲 | pp.35-40 |
| ページ数 | 6 |
| 発行日 | 2008-04-11 (COMP) |
[研究会発表申込システムのトップページに戻る]