著者

田中 英輝

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告自然言語処理(NL)

巻号頁・発行日

vol.1995, no.69, pp.89-94, 1995-07-20

被引用文献数

4

---

自然言語処理に利用するための規則をコーパスから学習する研究が最近盛んになっている.これらの研究では,得られた規則の適用範囲をいかに一般化するかが大きな課題となる.なぜなら,コーパスから直接学習される規則はそのままでは適用範囲が極端に狭いからである.現在はこの問題を解決するためにシソーラスを利用した手法が試みられている.このとき,シソーラス上のどの概念で規則を一般化するかが問題となる.しかしシソーラス上のノードの選び方は,組合せ的に爆発を起こすためその決定は容易ではない.本稿では,この問題を線形時間で解く基本的なアルゴリズムを提案する.本稿の問題は一般的に言うと帰納学習の分野で問題とされていた「構造化属性」の問題に属する.さらに,決定木の最適部分木を求める問題とも等しい.The proper treatment of structured attributes in inductive learning is getting much attention as this learning technique is now frequently applied to the knowledge extraction in natural language processing, In this context, the problem is finding a set of thesaurus nodes that maximally generalizes words in the learning source, but causes minimum errors. The number of candidate node sets, however, explodes as the thesaurus size increases, and no efficient algorithm has been discovered so far. In this paper, we propose the algorithm T^* which can find the optimal node sets in linear-time. This algorithm first converts the thesaurus into a directed acyclic graph changing this difficult problem into a shortest path problem with a graph where we can use an efficient algorithm. We then show that T^* can also be used to find the optimally pruned decision tree.