Learning Relational Patterns (ALT 2011)

original paper: http://www2.cs.uregina.ca/~zilles/geilkeZ11.pdf

ALT パターン形式言語

パターンは実際の適用のためには、表現力が十分ではない (どっちの意味だろう)
1つパターン中の変数同士の関係を定める
- Relational Pattern (RP)
- RP Languages (RPLs)
RPLs は正提示から学習可能
それとは別に新しい学習モデルを提案する

Introduction

Angluin のパターン
正提示からの学習
- 正データのストリーム: 逐次的に推測
言語の表現力と学習可能性はトレードオフ
- 言語が複雑になると厳密に学習するアルゴリズムが存在しない (正規言語; 文脈自由文法)
- しばしばそれは、membership 判定の計算複雑性に起因する
  - 例えばある文字列 $s$ があるパターン言語 $L (p)$ に属するかの判定は NP-hard

Relational Patterns

$n$ 個の変数 $y_{1} . . y_{n}$ に関する $n$ 項関係 $R_{y_{1} . . y_{n}}$
- 沢山予め定めておく
変数を $n$ 個 ( $y_{1} . . y_{n}$ ) 含むパターン $p$ について
- $y_{i} \mapsto s_{i}$ とする代入は
- $R_{y_{1} . . y_{n}} (s_{1}, . ., s_{n})$ を満たさなければならない

例

$R_{x_{1}} = {a^{i} : i \geq 1}$
$R_{x_{2}} = {b^{i} : i \geq 1}$
$R_{x_{1}, x_{2}} = {(w_{1}, w_{2}) : | w_{1} | = | w_{2} |}$

L (x_{1} x_{2}) = {a^{i} b^{i} : i \geq 1}