カーネル法に基づく構造データのラベル付け学習アルゴリズム(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論、論理プログラム,プランニングetc.」及び一般)  [in Japanese] Kernel-based Discriminative Learning Algorithms for Labeling Structured Data  [in Japanese]

本稿において,我々はパーセプトロンアルゴリズムに基づく,配列や木,グラフなどの構造を持ったデータのラベル付け学習アルゴリズムを提案する.また,ラベル付けに用いることのできるいくつかのカーネル関数とその効率的な計算法を与える.提案手法は,完全にカーネル化されており,かつ,点ごとのラベル予測を行うため,任意の数の非観測変数を含む,サイズの大きい素性を用いることができる.この点において,提案手法は最大エントロピーマルコフモデルや条件付確率場など少数の非観測変数をもつ素性しか扱うことのできない既存の手法と大きく異なる.

We introduce a new perceptron-based discriminative learning algorithm for labeling structural data such as sequences, trees and graphs. Since it is fully kernelized and employs the pointwise label prediction, large features including arbitrary number of hidden variables can be incorporated with polynomial time complexity. This is contrasted with existing labelers that can handle only features of a small number of hidden variables such as Maximum Entropy Markov Models and Conditional Random Fields. We also introduce several kernel functions for labeling sequences, trees and graphs and the efficient algorithms for them.