概要

Abstract より

MLNP は終点のノードが中間のノードより強い情報を持つ場合において有用性を発揮する階層的分類手法である
階層的多クラス分類を行う MLNP の手法は数多く存在するものの、MLNP を階層的多ラベル分類に利用することはなかなか難しいものがある
今回は、大域的な階層構造を考慮し、木および DAG の両方に適用できる新しい MLNP アルゴリズムを提案する
- 貪欲法が全ノードのラベルの事後確率を効率的に最大化することを示した
- さらに対称損失の期待値を最小化することも成し遂げた

Introduction より

階層的分類アルゴリズムはラベル間の階層関係を予測する上で非階層的なアプローチに比べて良さげなパフォーマンスを達成している
- MLNP は終点ノードまでのフルパスを利用した予測であるが、部分的なパスを利用した NMLNP ってのもある
今回は階層的多ラベル分類（ HMC ）に着目する
- 階層的他クラス分類との違いは、それぞれのパターンのラベルが階層内のパスの結合になること
  - 参考: J.Rousu, C.Saunders, S.Szedmak, and J.Shawe-Taylor. Kernel-based learning of hierarchical multilabel classification models. Journal of Machine Learning Research, 7:1601–1626, 2006.
- 日常的な例としては document, image, song, video あたりが複数のタグを持つ感じ
- 近年盛んに研究されている
階層的他クラス分類ではただ1つの部分木についての問題である一方、HMC においてはそれぞれのノードがいくつの部分木を持ちどの部分気についての問題かを決定する
- しかしながら、全ての部分木・サブグラフにおける最大事後確率を計算する上でのより良いアプローチとなるものの、終点ノード数が多いほどが候補数が多くなったり、既存研究においてはメタラベルの数が多くなったり DAG へ対応ができないなどの問題があった
これらの問題についての解決策を提案する
- 弱 nexted approximation 仮定を利用することで、最適化問題が貪欲法で効率的に解けることを証明した
章立ては以下の通り
- 2章で MLNP のためのフレームワークを提案
- 3章で DAG 構造への拡張を行う
- 4章で実験結果について述べる

利用技術・前提知識・用語

MLNP
- mandatory leaf node prediction
- ⇔ NMLNP
  - non-mandatory leaf node prediction
DAG
- directed acyclic graph
- 有向非循環グラフ
joint posteriror probability
- 同時事後確率
gene function
- 遺伝子機能
HMC
- hirarchical multi-label classification
- 階層的多ラベル分類？
greedy algorithm
- 貪欲法
symmetric loss function
- 対称損失関数？
Baysian network
- ベイジアンネットワーク
Second Pascal Challenge on Large-scale Hierarchical Text Classification
- テキスト分類のコンテスト？
nested approximation
- ネスト近似？
NAP assumption
MAS algorithm