Applying Tree Kernel to DOM Tree on Python

Definition:

We will use normalized one instead for the property of positive-definite kernel.

code:

from bs4 import BeautifulSoup
from pylab import *
import requests

def dom_tree_kernel(elems1,elems2):
    v1=[]
    v2=[]
    for target_elem in elems1+elems2:
        i=0
        for elem in elems1:
            if target_elem==elem:
                i+=1
        v1.append(i)
        i=0
        n=float(len(elems2))
        for elem in elems2:
            if target_elem==elem:
                i+=1
        v2.append(i)
    v1=array(v1)
    v2=array(v2)
    return v1.dot(v2)/(norm(v1)*norm(v2))

def get_dom_tree(url):
    return list(BeautifulSoup(requests.get(url).content).body.findAll())

if __name__ == "__main__":
    url1="http://www.webcreatorbox.com/tech/wordpress-tips/" # 2 columns
    url2="http://masalog.net/workflowy.html" # 2 columns
    url3="http://www.tuad.ac.jp/" # 3 columns
    dt1=get_dom_tree(url1)
    dt2=get_dom_tree(url2)
    dt3=get_dom_tree(url3)
    print "2-columns vs 2-columns:",dom_tree_kernel(dt1,dt2)
    print "2-columns vs 3-columns:",dom_tree_kernel(dt1,dt3)
    print "2-columns vs 3-columns:",dom_tree_kernel(dt2,dt3)

Result:

2-columns vs 2-columns: 0.206278804472
2-columns vs 3-columns: 0.0855306751119
2-columns vs 3-columns: 0.670058498405

In third result, although one is 2-columns and the other is 3-columns, the result is high. This is quite interesting. It could capture the internal structure. This DOM tree kernel can be regarded as a similarity between webpages 🙂

広告

列空間(像)と零空間(核)と正射影行列

今読んでいる論文で重要な概念なので勉強し直しました. 理解に半日かかりました. 途中まで理解できたと思うので忘れないうちに.

行列A = [a_1|\cdots|a_n]\in \mathbb{R}^{m \times n}を考えます.
Aの列空間C(A)は文字通り列ベクトルで張られる空間です. 正確にはピポット列たちで張られる空間ですがここではAはフルランクだとします.

C(A) := span\{a_1,\ldots,a_n\}

便宜上A^Tの零空間N(A^T)を考えます.

N(A^T) := \{x|A^T x= 0 \}

さて,今回議論したいのは,元の空間\mathbb{R}^nからAの列空間およびA^Tの零空間への正射影行列はどんな形をしているのか,ということです. ここからは図がないと議論しにくいのですが…

まずはモチベーション.以下の線形方程式を考えます.

Ax=b

これは解をもたないことがあります.どんな時でしょうか? それはbC(A)に入っていない時です. そこで,bbに最も近いC(A)内の点pで置き換えてから,これを解くことを考えます. さて,pC(A)内の点なので,p=A\hat{x}と書けます. 元の方程式の解xの代わりに,p=A\hat{x}の解\hat{x}を求めようということです.

ここで,「最も近い点」とはなんなのかという議論になります. それをここで定義しなければなりません.ここは定義なので納得できなければ,または問題によっては変えても問題はないというわけです.

—ここから例に入ります—

20141016_1.png

今,A \in \mathbb{R}^{2\times 2}とし,ランクは1とします. つまりこの線形変換により\mathbb{R}^2内の点は,ある直線上につぶされます. イメージを上に示します.図での直線がC(A)です. さてAには列が2つありますがそれらは線形従属の関係になっています. 上の図のように,bC(A)に垂直に下ろした点をpと定義し,そのような射影,(これを正射影と呼ぶ)をPとします. 厳密に,e:=b-p=b-A\hat{x}とおくと,eC(A)が直交するようにpを定めます.

—ここまで例です—

eC(A)が直交するという条件はつまり,eC(A)の基底が直交するということです. C(A)の基底はAがフルランクならばその列からなる集合です. よって,eC(A)が直交するという条件は以下のように書けます.

A^T (b-A\hat{x}) = 0

これより,

\hat{x} = (A^T A)^{-1}A^T b

これで代わりの線形方程式が解けました. さらに,

p=A\hat{x}=A(A^T A)^{-1}A^T b

ここから

P = A(A^T A)^{-1}A^T

\mathbb{R}^nの任意の要素bC(A)に正射影する行列(正射影行列)だということが読み取れます.

さて,では\mathbb{R}^nからN(A^T)への正射影行列Qはどうやって求めるのでしょうか. 実は,C(A)N(A^T)は直交しています. これは結構簡単に証明できます.

x \in C(A), y \in N(A^T)とします.このとき,

x^T y = (Ax')^T y = x'^T Ay = 0

よって,C(A)N(A^T)は直交しています. さらに次元定理より

n = dim C(A) + dim N(A^T)

なので,C(A)の基底がk個からなり,N(A^T)の基底が\ell個あるとすると,k+\ell=nとなります. つまり,任意のb \in \mathbb{R}^n は,p \in C(A), q \in N(A^T) を用いて,

b = p + q

と表せる.これを変形すると,

q = b - p = b - A(A^T A)^{-1}A^T b = (I - A(A^T A)^{-1}A^T) b

よって,\mathbb{R}^nからN(A^T)への正射影行列Qは,

Q = (I - A(A^T A)^{-1}A^T)

と表せる.

以下の講義でここに書いてあるようなことが学べます.というよりそっちを見ていただいた方がよいと思います. 自分整理のためのメモでしたー.