14 Vector space classification (pp.266-292)

IIR

タイトルから章の意味がわからなかったけれど，kNNのようなinstance based learningの話だった．納得．

ざっくりとポイントをまとめるとこんな感じ．

  • Rocchio classification
  • kNN
    • time complexitiy and optimality
  • any-of classifier, one-of classifier
  • bias-variance trade off
  • linear vs non-linear classifier

Rocchio classificationという名前を知らなかった．多クラスの場合は，cluster-based classificationとかcentroid-based classificationと呼ばれることもあるらしい．

oddsとってlogとればNaive Bayesもlinear classifierです．という解説は，意外に新鮮．論文では読んだことあるけれど，教科書で（少なくともNBの章では）見たことがない．これもNBの章ではないのだけれど．

kNNの解説は1NNのボロノイ図から．kNNはnon-linearなんすよ．というのが図を含めてわかりやすく解説されている．

本章後半は，linear classifierとnon-linear classifierという軸をもって，bias-variance tradeoffの観点で解説．説明が丁寧．

varianceをmodel complexity(memory capacity)と見なすこともできる，という記述を見て，符号のイメージが増強された気がする．

感想．解説の粒度が的確．説明も秀逸．さすが．機械学習やる人にはもの足りないのだろうけれど，使う人にとってはぴったりだと思いました．

メモ

  • 14.3.1 Time complexity and optimality of k nearest neighborがきちんと理解できていないので，あとで復習しておこう
  • kNNのfast algorithm気になる
  • inverted indexを使ってlinear classifierの高速計算，なにそれ気になる？？
  • kNNのサーベイ論文を読んだことないので，チェックチェック