ABSTRACT

Real-world problems may contain latent dependencies (i.e., hidden sub-structures) that are difficult to capture with conventional structured classifiers, such as conditional random fields. In such cases, models that exploit latent variables are advantageous in learning, and conditional latent variable models have been applied successfully into real-world tasks in natural language processing and vision processing communities, including syntactic parsing and vision recognition. In the first part of this thesis, I perform experiments in a variety of tasks to confirm the advantages of conditional latent variable models, and investigate what kind of latent dependencies are learned by the model.

While the experiments confirmed the advantages of conditional latent variable models, the same experiments revealed two problems in applying such models for practical usages. First, establishing an efficient inference method on latent conditional models remains an open question. Second, because of the incorporation of latent variables, training a latent conditional model brings a heavy computational cost. To deal with those critical problems, I propose efficient methods for inference and training on latent conditional models.

In the inference stage, I propose the ``latent-dynamic inference", which is able to produce the exact optimal label sequence on latent conditional models by systematically combining efficient search strategy (the A* search) and dynamic programming (the Forward-Backward method). I also describe a straightforward solution on approximating the exact method, and show that the approximated version performs as well as the exact one, while the speed is much faster.

In the training stage, I propose a perceptron-style algorithm for fast online training of conditional latent variable models. Our method extends the perceptron algorithm for the learning task with latent dependencies. It relies on Viterbi decoding over latent variables, combined with simple additive updates. Compared to existing probabilistic training methods on conditional latent variable models, our training algorithm lowers the training cost significantly yet with comparable or even superior classification accuracy. I also analyze the convergence properties of the proposed training method, and show it is guaranteed to converge with a bound.

To evaluate the efficiency and accuracy of our proposals, I performed experiments on a variety of natural language processing tasks as well as an artificial data. Our experiments demonstrate that the proposed inference and training methods achieve good experimental results, and their computational costs are much lower than the traditional methods.

論文要旨

実世界の問題には、条件付確率場など従来の機械学習モデルでは表現しきれない隠れた依存関係が含まれることがある。 このような問題に対しては、隠れ変数を用いたモデルが有効である。自然言語処理および画像処理の分野では、統語解析、画像認識など現実的な問題に条件付隠れ変数モデルが応用され、その有効性が確かめられている。本論文の最初の部分では,条件付き隠れ変数モデルをさらに様々な問題に応用し、その有効性を示すとともに、隠れた依存関係としてどのようなものが学習され,精度向上に寄与しているのかを検討する。

上記の実験は、条件付き隠れ変数モデルの有用性を示す一方で、このモデルを実用化するにあたって、2つの問題が存在すること明らかにした。ひとつは,条件付き隠れ変数モデルの下での推論の際の計算コストが非常に大きいという問題、もうひとつは、モデルの学習に必要な時間が非常に長いという問題である。本論文の後半では、これらの問題を解決するため、条件付隠れ変数モデルのための効率的な学習および推論の手法を提案する。

まず、条件付隠れ変数モデルを用いた系列ラベリングのための高速な推論手法を提案する。この手法では、効率的な探索と動的計画法を組み合わせることにより、 最適な出力ラベル列(厳密解)を求める。また、この手法を一部変更し、高品質な近似解を厳密解法に比べはるかに高速に求める手法を提案する。

次に、パーセプトロンと類似したオンライン学習アルゴリズムを、条件付隠れ変数モデルに適用することを提案する。この手法では、隠れ変数列に対するビタビア ルゴリズムと加算形の重み更新ルールを組み合わせることにより、効率的な学習を実現する。最尤推定に基づく従来の手法と比べた場合、提案手法は学習コスト を大幅に削減し、かつ、同等以上の分類精度を実現する。また、提案手法による重みパラメータの収束に関して理論的な解析を行い、パラメータ更新の回数に関する上限値が存在することを示す。

評価実験として、提案した学習および推論手法を種々の自然言語処理タスクおよび人工データに適用し、精度の高い結果が従来法よりもはるかに効率的に得られることを示す.

本論文は 自然言語処理における統語解析の問題や画像処理における画像認識等の問題において用いられる条件付隠れ変数モデル下の推論の計算コストを大幅に改善する推論手法を提案するとともに、効率的なオンライン学習アルゴリズムを提案し、実際にもそれらの手法が種々の自然言語処理の問題において高い精度と高速性を両立していることを示したものである。

本論文は六章からなり、第一章では、条件付隠れ変数モデルとその関連問題の背景を解説している。

第二章では、本論文で扱う自然言語処理上の問題に対する従来手法について解説を行っている。

第三章では、条件付隠れ変数モデルが自然言語処理上の種々の問題において有用であることを、実験を通して示している。

第四章は二節よりなり、まず第一節において、条件付隠れ変数モデルを用いた系列ラベリングの計算コストを改善する、効率的な探索法と動的計画法を組み合わせた新しい高速かつ厳密な手法を提案している。さらにそれを拡張したさらに高速な高精度近似解法も提案している。さらに第二節では、パーセプトロンと類似したオンライン学習アルゴリズムを条件付隠れ変数モデルに適用した新しい学習手法を提案し、その上でこの学習手法の収束性を理論的に証明している。

第五章では、第四章で提案した手法が、自然言語処理上の種々の問題において、従来手法と比べきわめて効率的であることを計算機実験を通して実際に示している。

第六章では、本論文で提案された手法とその有効性を総括している。

なお、本論文の第三章の研究は、Louis-Philippe Morency氏、辻井潤一氏との、第四章、第五章の研究は張耀中氏、鶴岡慶雅氏、辻井潤一氏との共同研究であるが、論文提出者が主体となって立案、分析、検証を行ったもので、論文提出者の寄与が十分であると判断する。本論文の結果は、最近の機械学習の研究の大きな流れのひとつであるオンライン学習に関する従来の結果を大きく改善する独自かつ先進的なものであり、実際にもそれらの成果は、自然言語処理の分野における最もレベルの高い国際会議において多数採択され国際的に極めて高い評価を受けている。よって審査委員会は、本論文の独創性、有効性が標準修業年限3年間で達し得る平均水準を超えたものであり、博士号に十分値するものと判断した。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。