ラプラス正則化 (Laplacian Regularization) を使った半教師付き分類

教師ありデータ\{(x_i,y_i)\}_{i=1}^{n_l}と教師なしデータ\{x_j\}_{j=n_l+1}^{n}を 用いて学習する枠組みを半教師付き学習と呼ぶ. 少量の教師ありデータと大量の教師なしデータを持っているという設定は非常に現実的で, 半教師付き学習は実用的な枠組みだと思う.

ラプラス正則化の基本的なアイデアは,「似ているものは同じラベルを持つ」というもの. 具体的には,類似度行列Wを受け取り, 類似度が高いものは予測値も近くなるような正則化を行う. 今回はラプラス正則化のリッジ回帰への適用例を考えてみる. 目的関数は以下で与えられる.

\min_{\theta} \ \sum_{i=1}^{n_l} (y_i-f_{\theta}(x_i))^2 + \alpha \|\theta\|^2 + \beta \sum_{j=n_l+1}^{n} \sum_{k=n_l+1}^n W_{jk} (f_\theta(x_j)-f_\theta(x_k))^2

最後の項がラプラス正則化項. この項は結局ラプラス行列というもので表されるのでラプラス正則化と呼ばれている.

ここで,非線形な決定境界を表現するために,f_\thetaには以下で定義するRBFカーネルモデルを用いることにする.

f_{\theta}(x) = \sum_{\ell=1}^n \theta_\ell k(x,x_\ell), \ k(x,x_\ell)=\exp\left(-\gamma\|x-x_\ell\|^2\right)

コードは以下のようになった.

実行結果はこんな感じ. 左が訓練データで赤と青がラベル付きデータで白い点がラベルなしデータ. このように,たった2つの教師ありデータから正しく分類ができている.

laplacian_regularization_2moons.png

laplacian_regularization_2circles.png

ラプラス正則化は目的関数に一つ項を加えるだけで, 教師なしデータも活用できるのでお手軽で性能も素晴らしいので是非使ってみてください. 課題としてはパラメータチューニングがある. 教師ありデータが十分にあれば,交差検定ができるが,この例では2つしかないので最適なパラメータを得るのは難しい. それと,RBFカーネルモデルにすべてのデータ点を使っているものポイント.

広告

dragnetでHTMLから本文を抽出

HTMLから本文あるいはコンテンツを抽出したいという需要はかなりあると思う. この問題に対して,機械学習的なアプローチをしているdragnetというものがある(ソースは以下).

dragnetはHTMLをまずblockと呼ばれる単位に分割する. その後,そのブロックが本文であるかないかのラベルをつける. このようなラベル付きデータを用いて,分類器をトレーニングしている. データも以下で公開されていて,自由に追加してコミットすることができる.

分類器にはロジスティック回帰が使われているようだ. ロジスティック回帰は,ブロックが本文かどうかという確率を返すので,この閾値を自分なりにいじることでカスタマイズすることもできる. しかし,オリジナルのソースではこの部分がおかしなことになっている. というのも,dragnet.cotent_extractor.set_thresholdで閾値を設定できるのだが, 閾値で区切るところでdragnet.cotent_extractor._block_model.predictに対して閾値で区切っている. これはすごくおかしなことでpredictは0か1を吐くので閾値で切るというのが実際は機能していない.

というわけでフォークしてそこを書き換えてみた. 以下にそのリポジトリがある(なぜかプルリクが投げれなかった).

オリジナルを使う場合は以下の関数を使用すると良い.

このようなcontent extractor共通の悩みだと思うが, ニュースサイトとかではうまくいくけど,動画サイトや,特殊なサイトでは動かないというケースがある. そのようなケースでも閾値で対応できるかもしれないけど,試していない. とりあえず.dragnetは素晴らしいので是非使ってみてください.

追記(2015/07/30):pull requestを投げました.マージされればきちんとthresholdを設定できます.

word2vecでニュース記事分類

word2vecの応用として文書分類,ここではニュース分類をやってみました. データはlivedoorニュースコーパスを使いました. あと,wikipediaのデータで学習させたモデルを使いました.

bag-of-wordsを用いた場合は以下で議論されています.

さて,今回はword2vecを使って文書分類に挑戦してみます. word2vecにより,単語空間は有限次元ベクトル空間で表現されています. 単語xのベクトル表現をv(x)とし長さ1に正規化されているとします (正規化すると内積がcos類似度になる.特に正規化しなくてもよいと思うが念のため). さらに,文書dのベクトル表現をv(d)とします. ここで,文書dは単語を元に持つ集合(順序は考慮しない)とします.

さて,最もシンプルな文書ベクトルは以下のようになるだろう.

v(d) = \frac{1}{|d|} \sum_{x \in d} v(x)

これをモデル1とする.

次に,以下のような重み付きバージョンを考える.

v(d) = \frac{1}{|d|} \sum_{x \in d} \ w(x) \ v(x) \\ \\ \sum_{w \in d} \ w(x)=1

この重みw(x)には,例えばTFIDFやPMIなんかが使えると思う. ちなみに重みは足して1になるようにしておく.これをモデル2とする. 今回は,モデル1とモデル2を比較してみる.

モデル1はすぐに構築できるが,モデル2の重みを何にしようか迷う. 今回のタスクは文書分類なのだから,クラス分類において重要な単語には大きな重みをつけるべきだろう. そう考えると,以下の重み関数はどうだろうか.

w(x,d) = \frac{c(x,d)}{\sum_{x' \in d} c(x',d)}\log\frac{\#\mathcal{Y}}{\#\{y| x \in y\}}

ここでc(x,d)は,単語xの文書dにおける出現回数, \mathcal{Y}=\{1,\ldots,c\}はクラスで,\#は集合の要素数をさす. logの項はidfのクラス版で,その単語がいろんなクラスに出現するなら分母が大きくなり全体が小さくなる. 逆に,その単語があるクラスにしか出てこないならその単語の重みは大きくなる. これはあまりにもハードな重みな気がするが,とりあえずこれ(以下tficfと呼ぶ)を使ってみる.

さて,まずは文書を形態素解析するのだが(形態素解析を使わないバージョンは次に書こうと思う), 辞書には最近流行りのneologdを使う.

ライブドアニュースコーパスのディレクトリ構成は以下のようになっていることを想定.

livedoor_corpus/
  dokujo-tsushin/
  it-life-hack/
  kaden-channel/
  livedoor-homme/
  movie-enter/
  peachy/
  smax/
  sports-watch/
  topic-news/

なお,カテゴリ数は9で総文書数は7376であった. 分類器にはロジスティック回帰を用いた.

以下に実験結果を示す.

uniform tficf
0.85 (0.01) 0.52 (0.03)

tficfが重み付けを行った結果だ.ものすごく悪い. 一方重み付けを行わないモデル (uniform) はかなりいい性能を発揮している. 重み付けによりここまで性能が落ちるとは思わなかった. 何かバグがないか追求してみるが,今のところword2vecで学習した単語空間をそのまま使っても特に問題はなさそうだ. それにしても上のqiitaの記事ではBOW+kNNというシンプルな組み合わせながら精度が89%と報告されている. これはおそらく文書分類というタスクでは,文書が多数の単語を含むのでBOWでも十分にそれを表現できているため,と解釈できる. 逆に,一つの文書が短かったり,単語そのものを分類しなければならないようなタスクでは,word2vecの真価が発揮されるのではないかと思う.

単語分類については以下に簡単な例がある.

実は,短い文書においては,TFICFの有効性を確認した.よって長い文書でも動くはずなのだが,今回は動かなかった. というわけでバグを探すのと,word2vecの他の応用も考えてみる.

実験に使ったコードはGistに置いておくので,気が向いたら試してみてください:

Pythonでscikit-multilearnを使ったマルチラベル分類 (multi-label classification)

通常の分類問題は,各点がたった1つのクラスにしか属さないという仮定のもとで解かれる. しかし,現実には各点が複数のクラスに属するという場合がある. このような問題はマルチラベル分類問題 (multi-label classification) と呼ばれ,盛んに研究されている. マルチラベル分類問題を解くためのモジュールはいくつか存在するが,Pythonにはscikit-multilearnというモジュールがある.

今回はこれを使ってマルチラベル分類問題を解いてみる. データには公式と同じくsceneを使う.

まずはscikit-multilearnをダウンロードして移動する.

git clone https://github.com/scikit-multilearn/scikit-multilearn
cd scikit-multilearn

今回はここに以下のコードを置いて使ってみる.

実行結果:

0.113573021182

やっていることはとてもシンプル. まだソースを見ていないのでなんとも言えないが, 基本的な分類器を用意してそれをskmultilearn.meta_br.BinaryRelevanceがmulti-label用にラップしてくれると解釈している. 今回はlinear SVMを使ってみた. multi-label classificationの評価指標にはhamming lossが使われるようだ. これは[0-1]で,低ければ低いほど良い. 今回は0.11だったのでまぁまぁなのではないか.

以上scikit-multilearnの簡単な使い方を紹介してみた. 「multi-label classificationしないといけないけど詳しくない」 という方はとりあえずこれを使ってみるというのはどうでしょうか.

平均値の差の検定の威力たるや…

Source and explanation

# coding: utf-8
"""
検定の威力を検証する.
今回は累積分布関数が人の目で見て非常に似ているケースを想定したい.
なぜなら,累積分布関数が明らかに違うなら,検定を行う必要もないと思うからだ.
二つの分布から生成された標本x1, x2がある.
それぞれの平均値mmu1, mmu2を使って,x1,x2は別々の分布から生成されたことを検定で確かめる.
帰無仮説:x1,x2は同じ分布から生成された.
この仮説を棄却できるかどうかを調べる.
なお,分布には正規分布を使い,真のパラメータはそれぞれ(mu1, sigma1), (mu2, sigma2)である.
"""
import numpy as np
import random

class Cdf(object):
    def __init__(self, t):
        self.t = t
        self.N = float(len(t))

    def prob(self, x):
        return len([tt for tt in self.t if tt <= x]) / self.N

# 設定
# 大きさは1000ずつ
n, m = 1000, 1000 
# 真のパラメータ
mu1, mu2 = 0, 1
sigma1, sigma2 = 1, 1
# 標本の生成
x1 = np.random.normal(mu1, sigma1, n)
x2 = np.random.normal(mu2, sigma2, m)

# 帰無仮説用
x = x1 + x2
#random.shuffle(x)
# 標本平均
mmu1, mmu2 = x1.mean(), x2.mean()
# 平均差
# この平均差が偶然なのかどうか調べる.
delta = abs(mmu1 - mmu2)

print
print "n:", n
print "m:", m
print "mu1:", mmu1
print "mu2:", mmu2
print "delta:", delta

# 1000回リサンプリングして1000個の平均差を得る.
# 帰無仮説に基づくものなので,x1とx2を混ぜ合わせたものを使う.
iters = 1000
deltas = np.array([np.mean([random.choice(x) for i in range(n)]) - np.mean([random.choice(x) for i in range(m)]) for i in range(iters)])
print '(Mean, Var) :', (deltas.mean(), deltas.var())

# 標本の平均差以上の平均差が生成される確率(p値)を計算.
# 累積分布関数を使っているが,別に使わなくても良い.
cdf = Cdf(deltas)
left = cdf.prob(-delta)
right = 1.0 - cdf.prob(delta)
pvalue = left + right
print 'Tails (left, right, total):', left, right, left+right
# p値を見て判断

# plot用データ作成
cdf1 = Cdf(x1)
cdf2 = Cdf(x2)
minimum = np.min([x1.min(), x2.min()])
maximum = np.max([x1.max(), x2.max()])
px = np.linspace(minimum, maximum, 200)
py1 = np.array([cdf1.prob(xx) for xx in px], dtype=float)
py2 = np.array([cdf2.prob(xx) for xx in px], dtype=float)

import matplotlib.pyplot as plt
plt.plot(px, py1, "b-")
plt.plot(px, py2, "b-")
plt.show()

Results

Case 1: 全く同じ分布(パラメータ)

平均0分散1の正規分布と平均0分散1の正規分布から生成されたデータ. 累積分布関数はこんな感じ.見た目はほとんど同じ. こいつのp値は0.468で帰無仮説は棄却できない. つまり,同じ分布から生成されたということ.理にかなう. wpid-same_dist.png

Case 2: ほぼ同じ分布(パラメータ)

平均0分散1の正規分布と平均0.15分散1の正規分布から生成されたデータ. 累積分布関数はこんな感じ.さきほどまではいかないが見た目はほとんど同じ. p値は0.049で,有意水準5%でなら棄却できる.(使い方あってるのか…) wpid-5_dist.png

Case 3: 異なる分布(パラメータ)

平均0分散1の正規分布と平均1分散1の正規分布から生成されたデータ. 累積分布関数はこんな感じ.見た目から同じ分布(同じパラメータ)から生成されていないことがわかる. 是非棄却されてほしい. wpid-notsame.png p値は0で期待通り棄却できる.

Summary

平均値の検定は,2つのデータがあり,それぞれ異なる分布(あるいはパラメータ)から生成されたかどうかを確かめることができる. 今回は同一分布(正規分布)で,パラメータだけを変えて実験をしてみた. 検定結果は理にかなっており,パラメータが全く同じなら,帰無仮説は棄却できず, パラメータを大きく変化(1程度)させると帰無仮説は棄却され,異なる分布と判断した. 問題は人間の目でみて,ほとんど同じだけどどうだろう?というケース(Case2). このケースを実験することで,「判断は,有意水準に委ねる」という統計学の非常にスマートな態度を実感することができた. これからの研究活動に役立ちそうだ.

どうやらHTML本文抽出はDIFFBOTに任せた方が良さそうだ(Python)

wpid-diffbot_logo-white.png DIFFBOTはWEBページから必要な情報を抽出するためのAPIを提供している. 無料でもある程度の機能を使うことができる.

登録

まずは会員登録をする.

の一番下のView Plansをクリック. FreeプランのSign Upから登録. 送られて来るメールにtrial developer tokenが記入してある. これを使います.

Pythonから使う

以下のコマンドでインストールできる.

sudo pip install diffbot

例のごとくライフハッカーをパースしてみる.

>>> import diffbot
>>> token = "your developer token"
>>> url = "http://www.lifehacker.jp/2014/02/140224cochlearimplant.html"
>>> json_result = diffbot.article(url, token=token)

これでタイトル,画像,本文などが簡単に抽出できる. 前述のPocket APIではArticle View APIはまだ提供されていないので, もし,HTMLからデータを抽出したければ,DIFFBOTを使うのが最も簡単な方法かもしれない.

HTML本文抽出には最も効果的なのはh5タグ?(Python)

どうも. HTML本文抽出はもうかなりいろんなライブラリがあるみたいなので,助かっています. ただ,自分でも少し興味があるので調べてみました. 僕もやはりコンテンツ要素の抽出的やり方が良いのではないかと思います. コンテンツ要素とは,本文を含むタグ,という意味です. この記事では6つのニュース系サイトを調査して,どのタグがHTML本文抽出に効果的なのか調べることにします. 6つでは統計的にうんぬん言えるレベルではないと思いますが.

さて,コンテンツ要素の候補はdiv, pタグとします. 全ての候補を,それが含んでいる各タグの個数でもってベクトル化します. そして,あらかじめ調べておいたコンテンツ要素に該当するものに1,そうでないもの0のラベルを貼ります. 1のラベルが貼られたものの平均ベクトルを計算(mu1). 同様に0のラベルが貼られたものの平均ベクトルを計算(mu0). でもって,タグiがどれくらい有効か調べてみたいと思います. ここでいう有効なタグというのは,コンテンツ要素には含まれていて,それ以外にはあまり含まれないタグを指します.

Result

h5 40.3729750224
li 9.48468366897
body 5.29023736076
head 1.18257207967
strong 0.635549559566
html 0.607884938778
dd 0.235510380623
p 0.166378116343
ul 0.156020923659
label 0.0742267250716
fieldset 0.0717178349261
meta 0.0322441507155
div 0.0252577050591
table 0.0200621351686
br 0.011026083618
dl 0.00673111023781
center 0.00575343384869
h3 0.00563661589778
cite 0.00563661589778
h4 0.00463917031698
img 0.00456914610937
script 0.00310556029484
form 0.0026095333033
em 0.00181217590507
button 0.00138024901993
tr 0.00121310949017
noscript 0.00105675315588
h6 0.000345062254982
h1 0.000316906133482
tbody 0.000194097518427
hr 0.000194097518427
td 0.000153361002214
a 0.000153361002214
iframe 0.000153361002214
title 0.000153361002214
dt 8.62655637455e-05
b 5.99066414899e-05
small 4.85243796068e-05
input 3.83402505535e-05
g:plusone 2.93542543301e-05
style 2.15663909364e-05
link 1.49766603725e-05
textarea 5.99066414899e-07
h2 0.0
span 0.0
address 0.0
i 0.0

あえて割合([0-1])で出さないようにしました. 予想通りliタグが上位に来ています,メニューなんかによく使用され,かつコンテンツにはあまり使用されないので,これは妥当かと思われます. 興味深いのはh5タグです.考えてみれば当然なのかもしれませんが,1位とは驚きました. body, head, htmlがランクインしているのは私のミスでしょうか. さらに,strong, brなんかもランクインしていますね. まだまだ件数が少なくて,頼りない情報ですが,おもしろい結果が得られて満足です.