講演抄録/キーワード |
講演名 |
2016-12-22 15:40
等価性構造保持仮定の下での等価性構造抽出における探索数削減 ○佐藤聖也(産総研)・高橋良暢(電通大)・山川 宏(ドワンゴAIラボ) ISEC2016-87 COMP2016-48 |
抄録 |
(和) |
$K$個の系列IDからなる$K$-タプルにより指定される$K$次元系列を考える.$N$個ある系列IDから取り得る$K$-タプルの内,等価と思われる$K$次元系列を指定する$K$-タプルの集合を$K$次元の等価性構造と呼ぶ.2つの$K$次元系列が等価であるかの判定はそれぞれの$K$次元系列から取り出した連続部分系列を基に判定する.$N$個の系列IDから取り得る$K$-タプルの総数は$_N {mathrm P}_K$であるため,$K$の増加に伴った比較回数の組み合わせ爆発が問題となる.本稿では,$K$次元の等価性構造の全てのタプルから任意の$k$番目にある系列IDを取り除いたとき,その$(K-1)$-タプルからなる集合は$(K-1)$次元の等価性構造の部分集合であるという等価性構造保持仮定を認めることで,$(K-1)$次元の等価性構造から$K$次元の等価性構造を生成できることを示す.さらにこの定理から,逐次的に$K$を増加させながら等価性構造を探索でき,考慮する$K$-タプルの数を減らすことができることを示す. |
(英) |
We consider $K$-tuples that are composed of IDs that identify $K$D sequences where the number of IDs is $N$. An equivalence structure (ES) is defined as a set of $K$-tuples that identify $K$D sequences considered equivalent. Whether or not two $K$D sequences are equivalent is determined based on their continuous subsequences. Since the number of possible $K$-tuples taken from $N$ IDs is $_N {mathrm P}_K$, the comparisons cause combinatorial explosion along with the increase of $K$. In this paper, we show that a $K$D ES can be generated from a $(K - 1)$-D ES when we have an assumption that a $(K - 1)$-D ES is a superset of a set of $(K-1)$-tuples that are taken from a $K$D ES removing the $k$th ID of all the $K$-tuples. In addition, we show that we can obtain ES's successively increasing $K$ and reduce the number of tuples to consider. |
キーワード |
(和) |
等価性構造 / 見真似学習 / 組み合わせ爆発 / 高速化 / 系列データ / / / |
(英) |
equivalence structure / imitation learning / combinatorial explosion / speed-up / sequence data / / / |
文献情報 |
信学技報, vol. 116, no. 381, COMP2016-48, pp. 81-86, 2016年12月. |
資料番号 |
COMP2016-48 |
発行日 |
2016-12-14 (ISEC, COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2016-87 COMP2016-48 |