#6 Seeing stars when there aren’t many stars: Graph-based semi-supervised learning for sentiment categorization

tutorialの資料があった。Amazonのカスタマーレビューのところにある☆がいくつかを当てるような問題にSSLを適用した、というもの。グラフベースの手法。この論文のmain contributionは3つあって

  • 教師ありでやられていたことを半教師あり学習に拡張
  • グラフを使った問題に定式化、その問題の最適化について考えた(closed form solutionがある)
  • 実験によりSSLの効用がどんなもんかを検証した

というところ。

要点としては、「損失関数の構成の仕方」「ラベルありデータが多すぎると悪化することがある」くらいかしら。

ごにょごにょ書いてあるが、損失関数をまず定義。ラベルありのデータについて二乗和誤差とラベルなしデータについての二乗和誤差(事前にラベルありデータを使って作った学習器を使って出したものを使う)が入っている。ラベルありのほうは重要な情報でこっちのほうは間違って欲しくないので、重みに相当するようなMというスカラーを二乗和のところにかけてあるのがポイント。この辺のときにもラベルなしデータのところの損失は1以下の重みをかけて、というのがあったな。

損失関数にはもう一つ大きなパートがある。あと同じラベルを持ってるデータの近く(ここではkNNを使ってある)にあるデータは同じラベルを持っているはず、という仮定(これはグラフベースのSSLには大体出てくる)も損失関数に入れてあげる。これもラベルありとラベルなしについて重みを変える。さて、このままでは最適化が大変なので、重み行列とかを少しばっかり考えて定式化してあげるとただの二次関数となり、大変happyな結果((7)式)となる。

グラフの枝の重み(ようするに距離)をどうするかっていうのは非常に重要な問題で、ここではPSPというのと相互情報量を使ったものがある。が、その辺を置いておくと、ラベル付きデータの数が少ないときはSSLはうまくいくが、ラベル付きデータの数が増えてくると逆に悪化するという減少が見られた。

その他

あんまりこの論文とは関係ないけど、グラフが巨大になってくるとkNNを探してくるところが結構大変になるのかなーとか思った。だからkNNの近似(名前忘れた => LSHでした...)とかの研究も結構されているのかなーとか思った。

A. Goldberg and J. Zhu. 2006.
In HLT-NAACL Workshop on Graph-based Algorithms for Natural Language Processing.

In this paper, Goldberg and Zhu directly apply harmonic functions to sentiment categorization. They define a graph where each instance node is connected to a label node with a particular strength. For labeled data, the connection is given strength 1. For unlabeled data, the connection is given some strength proportional to an external classifier. In addition to this, they connect neighboring instances based on a variety of heuristics. As in Zhu, Gharhamani, and Lafferty (2003), their energy function is quadratic, allowing them to compute the minimum-energy labeling of the graph in closed form. For small amounts of labeled data, they are able to significantly improve over a supervised baseline.

Graph-based SSL - SSL Tutorial: ACL 2008