研究紹介「メタ関係発見」

ドワンゴ人工知能研究所 技術資料 [2017年8月9日版]

「メタ関係発見」とは「関係の関係性を見付ける」手法です。
ここで系列を区別するための属性があたえられてない、多次元系列における関係を「系列の組」とした場合、「系列の組」間のメタな関係を発見することです。なお、組は順序付けられた集合(リストに似たもの)です。その中で私たちが着目し取り組みを進めているのが、等価なメタ関係の発見を行う「等価性構造(Equivalence Structure:ES)抽出」です。

メタ関係発見

図:等価性構造抽出の例。#1〜#8の系列(系列)から〈#1, #2, #3〉と〈#8, #7, #5〉という二つの組を取り出し、この二つの組にメタ関係があるかどうかを検証する。この例では、青、赤、黒の3つの部分列が酷似しているため、等価なメタ関係と見なす。

等価性構造抽出では、二つ以上の組を比較して、必ずしも同時でない時刻(非同期)において「似た部分列が含まれている」ときに、「等価」というメタ関係を持つ構造が発見されたと考えます。この抽出は「属性が未知である」といった場合でも利用できる特徴を持ちます。「非同期」かつ「属性が未知である」データの例として、ヒトとチンパンジーの脳波の中にある等価な関係を見つけるタスクが考えられます。このようなデータでは一般的に同期していないため、時刻の違いを吸収する必要があります.またここで言う属性が未知であるとは,ヒトとチンパンジーでは各脳波の持つ属性(働きや意味)がどう対応しているのか分からないということです。このようなデータ間で等価性構造を見つけると,脳波の何れの系列同士が対応しているかを見つけることに役立ちます。ここで二つの組が等価であるかどうかの判定は、部分列を比較し、十分に類似しているかを基に行います。これにより、非同期で属性が未知な関係でも関係性を発見できます。

ES抽出の大きな問題点は、その計算量の多さです。すべての系列の数をNとし、組の大きさをKとしたとき、探索する組の数はN個の中からK個を並べる順列になり、その中で部分列の比較も行う必要もあります。我々は直接K順列を計算するのではなく,Kを逐次的に増やす探索手法(ESIS)を提案し、これにより計算時間を削減しました。実用性を高めるために今後一層の計算時間の削減に取り組んでいます。