修 士 学 位 論 文

修 士 学 位 論 文

題名

:

指導教員 福永 力 教授

   平成

31

1

10

首都大学東京大学院

理工学研究科 数理情報科学専攻 学修番号

17878318

氏名 田中 基之

目次

1

1

1.1

. . . . 1

1.2

. . . . 1

1.3

. . . . 2

2

2 2.1

. . . . 2

2.2 word2vec . . . . 3

2.3 fastText . . . . 5

3

5 3.1

SVD

. . . . 6

3.2

. . . . 7

3.3

. . . . 8

3.4

. . . . 9

4

13 4.1 SCDV . . . . 13

4.2 GMM

. . . . 13

4.3

. . . . 14

5

16 5.1

. . . . 16

5.2

. . . . 17

5.3

. . . . 17

5.4

. . . . 18

5.5

. . . . 19

6

22 6.1

. . . . 22

6.2

. . . . 23

7

23

補足資料

24

1

1.1

情報検索を行うためのアルゴリズムとして，ベクトル空間モデル

[12]

^*1

Web

文書分類もまた自然言語処理の問題の一つであるが，ベクトル空間モデルを適用するた めには，どのようにしてデータをベクトル化するかが重要となる．文書をベクトル化する 手法は様々であり，単語の出現分布を用いた

Bag of Words

doc2vec

SCDV

Sparse Composite Document Vectors

[5]

SCDV

word2vec [10]

tf-idf

SVM

Support Vector Machine

[15]

本論文は，この

SCDV

1.2

[5]

[5]

*1必ずしも必要ではないメール（ダイレクトメールなど）を自動分類するシステム．

1.3

2

3

2.1

4

5

2

単語を実数ベクトルで表現したものを単語の分散表現といい，以下，何らかの手法によ り取得した単語の分散表現を単語ベクトルと呼ぶことにする．本論文で扱う単語ベクトル の取得手法は，分布仮説を仮定する．分布仮説は「単語の意味はその周辺に出現する単語 によって決定される」というものである．単語

w _i

−→ wv _i

w _i

w j

sim(w i , w j )

sim(w i , w j ) = cos ( −→ wv i , −→ wv j ) =

−→ wv i · −→ wv j

|−→ wv _i ||−→ wv _j | (1)

単語のベクトル化手法は，単語の数え上げや行列の変形といった統計・数理的なもの と，ニューラルネットワークを用いた学習によるものに大別される．本章では前者として 単語文脈行列を，後者として

word2vec

fastText

2.1

文書を収集したデータをコーパスという．コーパス中に出現する各単語について，その 単語の前後

δ

c j

w i

w _i

c _j

δ = 1

“play”

“can”

“tennis”

“to”

“a”

:

I can play tennis. I want to play a tennis player.

コーパスに出現する単語の集合を

V _W

V _C

#V _W = I, #V _C = J

w i

c j

M ∈ R ^{I × J}

w _i

c _j

w _i

c _j

)

#(i, j)

M

(i, j)

m _ij

を共起する回数で定義する

:

m _ij ≡ #(i, j). (2)

他にも様々な共起の尺度が提案されているが，次の自己相互情報量を用いた尺度がよく用 いられる．

定義

2.1

pmi(w i , c j ) = log

#(i, j)

#( ∗ , ∗ )

#(i, ∗ )

#( ∗ , ∗ ) × #( ∗ , j )

#( ∗ , ∗ )

= log #(i, j) × #( ∗ , ∗ )

#(i, ∗ ) × #( ∗ , j ) (3)

Pointwise Mutual Information

#(i, ∗ ) =

∑ J j=1

#(i, j), #( ∗ , j ) =

∑ I i=1

#(i, j), #( ∗ , ∗ ) =

∑ I i=1

∑ J j=1

#(i, j) (4)

PMI

Positive PMI

”have”

や

”new”

[3]

m ^ppmi _ij ≡ ppmi(w _i , c _j ) = max { 0, pmi(w _i , c _j ) } . (5)

^*2 κ

Shifted PPMI

word2vec

2.2

[8][9]

m ^sppmi _ij ≡ sppmi(w i , c j ) = max { 0, pmi(w i , c j ) − log κ } . (6)

M ∈ R ^{I × J}

i

w i

−→ wv i ∈ R ^J

2.2 word2vec

word2vec [10]

るモデルであり，加法構成性が示唆されたことで注目を集めた

: arg max

−

→ w ∈ V

( − → w king − − → w man + − → w woman ) · − → w = − → w queen . (7)

*2機械学習のモデルの性能に影響を与える，調整可能なパラメータ．このパラメータを学習することは容易 ではなく，一般にはモデルを使用する側が予め決め打ちで設定する必要がある．

word2vec

skip-gram

[6]

w _{⟨ 1 ⟩} , w _{⟨ 2 ⟩} , . . . , w _{⟨ T ⟩}

t

w _{⟨ t ⟩}

δ

C _{⟨ t ⟩} = (w _{⟨ t − δ ⟩} , . . . , w _{⟨ t − 1 ⟩} , w _{⟨ t+1 ⟩} , . . . , w _{⟨ t+δ ⟩} ) (8)

skip-gram

w _{⟨ t ⟩}

C _{⟨ t ⟩}

p(C _{⟨ t ⟩} | w _{⟨ t ⟩} )

p(C _{⟨ t ⟩} | w _{⟨ t ⟩} ) = ∏

c ∈ C

p(c | w _{⟨ t ⟩} ) (9)

に自然対数をとり，すべての単語について足し合わせた対数尤度関数

L =

∑ T t=1

log



 ∏

c ∈ C

p(c | w _{⟨ t ⟩} )



 =

∑ T t=1

∑

c ∈ C

log p(c | w _{⟨ t ⟩} ) (10)

p(c | w _{⟨ t ⟩} )

:

p(c | w _{⟨ t ⟩} ) = exp s(c, w _{⟨ t ⟩} )

∑

c

∈ V

exp s(c ^′ , w _{⟨ t ⟩} ) . (11)

s(c, w) = − → u c · − → v w

− → u , − → v

(10)

L =

∑ T t=1

∑

c ∈ C

{

s(c, w _{⟨ t ⟩} ) − log

( ∑

c

∈ V

exp s(c ^′ , w _{⟨ t ⟩} ) )}

. (12)

現実的な問題として

c ^′ ∈ V W

w

c

p(D = 1 | w, c)

p(D = 0 | w, c)

p(D | w, c) = p(D = 1 | w, c) ^D p(D = 0 | w, c) ^{1 − D} (13)

w _⟨t⟩

c ∈ C _⟨t⟩

w _⟨t⟩

c ̸∈ C _⟨t⟩

(12)

L b =

∑ T t=1

∑

c ∈ C



log p(D _t = 1 | c, w _{⟨ t ⟩} ) ^D

+ ∑

c

̸∈ C

log p(D _t = 0 | c ^′ , w _{⟨ t ⟩} ) ^{1 − D}



 (14)

を最大化すればよい．確率

p(D = 1 | c, w)

σ(x) ≡ 1

1 + e ^{− x} (15)

を用いて

p(D = 1 | c, w) = σ(s(c, w)), (16)

p(D = 0 | c, w) = 1 − σ(s(c, w)) = σ( − s(c, w)) (17)

c ^′ ̸∈ C _{⟨ t ⟩}

w

U (w)

P (w) = U (w) ^α

∑ T

t=1 U (w _{⟨ t ⟩} ) ^α (18)

に従って

k

(14)

k = 10

α

0.75

2.3 fastText

fastText

word2vec

で，

“go”,“goes”,“going”

たモデルである

[2]

word2vec

fastText

subword

“where”

3

n

⟨ wh ⟩ , ⟨ whe ⟩ , ⟨ her ⟩ , ⟨ ere ⟩ , ⟨ re ⟩

は

“where”

fastText

学習を行い，それらのベクトルの和として最終的な単語のベクトルを与える．これによ り，接頭辞や接尾辞を考慮することができるほか，未知の単語に対するベクトルを考える ことも可能になる．部分語はデフォルトの設定で

n = 3, 4, 5, 6

n

3

2.1

I × J

J

J

“alcohol”

や

“liqueur”

低次元の密行列に変形して用いられることが多い．単語文脈行列に対する次元削減法とし ては特異値分解が一般的であるが，その他のいくつかの手法も試行した．ここでは予備実 験でとくに文書分類に効果的であったものを取り上げる．

3.1

SVD

定義

3.1

r ̸ = 0

M ∈ R ^{m × n}

3

M = U SV ^T (19)

に分解することを特異値分解（

Singular Value Decomposition

• U : r

m × r

⇐⇒ U ^T U = E r

• S : r × r

S = diag (σ 1 , . . . , σ r ), σ 1 ≥ · · · ≥ σ r > 0

• V : r

n × r

⇐⇒ V ^T V = E _r

であり，

S

U, V

i

σ i

定理

3.2

(19)

U, V

S

定理

3.3

Eckart & Young

r ̸ = 0

M ∈ R ^{m × n}

ρ (< r)

S ρ

を順に並べた行列

U ρ , V ρ

M ρ = U ρ S ρ V ρ T

(20)

ρ

M

M _ρ = arg min

X ∈R

rank X=ρ

∥ M − X ∥ F . (21)

ここで，フロベニウスノルム

∥ · ∥ F

M = [m _ij ] ∈ R ^{m × n}

∥ M ∥ F =



 ∑

i,j

| m ij | ²





1/2

(22)

M ρ

M

ρ

単語文脈行列

M

ρ

w i

ρ

M f = U ρ S _ρ ^γ ∈ R ^{I × ρ} (23)

の第

i

γ

0, 0.5, 1

γ = 1

M ρ M ρ T

= (U ρ S ρ V ρ T

)(U ρ S ρ V ρ T

) ^T = U ρ S ρ V ρ T

V ρ S ρ T

U ρ T

= (U _ρ S _ρ )(U _ρ S _ρ ) ^T = M f M f ^T (24)

(1)

w i

w j

3.2

ランダム・プロジェクションは

n

d

u ∈ R ^d

k

d

r ∈ R ^d

k

:

U ^′ = R ^T U. (25)

ここで，

R

r 1 , . . . , r k

d × k

U

u 1 , . . . , u n

d × n

U ^′

u 1 , . . . , u n

k

R

0

1

N (0, 1)

[1]

R ∈ R ^{d × k}

SR(s) =

 



 

− √

s/k with Prob. 1/2s 0 with Prob. 1 − 1/s

√ s/k with Prob. 1/2s

(26)

からサンプリングするスパース・ランダム・プロジェクションを採用した．ここで

s ∈ (0, 1]

Ping

[11]

s = √ 1

d (27)

を用いる．

3.3

カーネル主成分分析はカーネル法を用いたデータ解析の手法の一つで，正定値カーネル によって定まる非線形写像によって変換されたデータに対して主成分分析を行うことで，

変換前のデータがもつ非線形な特徴を考慮した分析を行う．正定値カーネルは以下で定義 される．なお，本節で紹介する定理の証明等は

[13]

定義

3.4 X

k : X × X −→ R

2

1)

x, y ∈ X

k(x, y) = k(y, x).

2)

n ∈ N

x 1 , x 2 , . . . , x n ∈ X, c 1 , c 2 , . . . , c n ∈ R

∑ n i,j=1

c i c j k(x i , x j ) ≧ 0. (28)

k

X

positive definite kernel

X

x ₁ , . . . , x _n

(i, j)

k(x _i , x _j )

n

定義

3.5 ( H , ⟨· , ·⟩ )

d(x, y) = ∥ x − y ∥ =

√ ⟨ x − y, x − y ⟩

H

定義

3.6 H

X

x ∈ X

k x ∈ H

⟨ f, k x ⟩ H = f(x) ( ∀ f ∈ H ) (29)

H

reproducing kernel Hilbert space

(29)

k(y, x) = k _x (y)

k

reproducing kernel

命題

3.7 H

X

k

H

1)

k

X

2)

k

3)

k

∥ k( · , x) ∥ H = √

k(x, x) ( ∀ f ∈ H )

定理

3.8

Moore-Aronszajn

X

k

X

H

3

1)

x ∈ X

k( · , x) ∈ H

2) Span { k( · , x) | x ∈ X }

H

3) k

H

系

3.9

X

k

H k

⟨ φ(x), φ(y) ⟩ = k(x, y) (30)

を満たす

φ : X −→ H k

これらの結果により，写像

φ

k(x, y) = exp (

− | x − y | ² 2σ ²

)

= exp (

− γ | x − y | ² )

(31)

カーネル主成分分析は，

I × J

M

{ x i } ^I i=1 ⊂ R ^J

k

K ∈ R ^{J × J}

K e ≡ K − J K − K J + J K J (32)

に対して特異値分解を行い，各成分の分散が最大となるような空間へデータを写す手法で ある．ここで，

J ≡

1/J

J

= 1

J ² 1 J 1 J T

(33)

3.4

3.4

3.3

Halko

[7]

Halko

験的に）改良したアルゴリズムである

redsvd ^*3

*3

https://code.google.com/archive/p/redsvd/

いると思われる計算方法を考案して用いている．本節ではその手法の説明と，簡単な実験 の結果から観察される近似の可能性について述べる．

3.4.1

単語文脈行列

M ∈ R ^I×J

r

p > q > 0

1.

M

(r + p)

A

2. G 1 ∈ R ^{m × (r+q)}

N (0, 1)

3.

A ^T G 1

Y

P = AY

4. G ₂ ∈ R (r+q)×(r+q)

N (0, 1)

5.

P G 2

Z

Q = Z ^T P

6.

Q

r

K r

M r = ZK r

を計算．

単語

w _i

−→ wv _i

6

i

m × n m × (r + p) m × (r + q)

(r + q) × (r + q) (r + q) × r

m × r

特異値分解

P = AY Q = Z

P kPCA M

= ZK

M A P Q K

M

à × à ×

(r + p) × (r + q) (r + p) × m m × (r + q) m × (r + q) m × (r + q)

(r + q) × (r + q)

Y A

G

Z P G

G

G

N (0, 1)

1

図

2 N (20, 10)

m × 1500

3.4.2

3.4.1

6

M

r

縮を近似している保証はないが，いくつかの実験により近似できている可能性が観察さ れた．

図

1

2

N (0, 1)

M

300

M

3

N (µ, σ)

U (a, b)

M

300

∥ A ∥ ∞ = max

i,j | a ij | (34)

を

300

6

γ = 20

p = 200, q = 10

m × n

n

m

m

m = 114260

91464

図

3 N (20, 10)

1000 × n

図

4

1000 × 1500

4

単語ベクトルを用いて文書をベクトル化する方法としてまず考えられるのは，文書に現 れる単語に対する単純な単語ベクトルの和（または平均）を文書のベクトルとみなす方法 であるが，本論文では

SCDV

SCDV

4.1 SCDV

SCDV

Sparse Composite Document Vectors

word2vec

r

Algorithm 1

rK

[5]

K

Algorithm 1

idf(w)

w

df(w)

idf(w)

w

[5]

−−→

scdv _D

4.2 GMM

ガウス分布の線形重ね合わせ

p(x) =

∑ K k=1

π k N (x | µ _k , Σ k ),

∑ K k=1

π k = 1, 0 ≦ π k ≦ 1 (35)

Gaussian Mixture Model

i = 1, 2, . . . , I

x _i ^T =

−→ wv _i

w _i

r

i

x _i ^T

I × r

r

X

x 1 , . . . , x I

p(X | π, µ, Σ)

L

L = log p(X | π, µ, Σ) =

∑ I i=1

log ( _K

∑

k=1

π k N (x i | µ _k , Σ k ) )

(36)

EM

（

Algorithm 2

[4]

単語

w i

c k

P (c k | w i )

P (c k | w i ) = γ i (k)

Algorithm 1 Sparse Composite Document Vector

Require:

V

−→ wv 1 , . . . , −→ wv I

Ensure:

−−→

scdv D

, . . . , −−→

scdv D

1: for w _i ∈ V do

2: idf(w i ) = log #

# { D ∈ | w i ∈ D }

3: end for

4:

w _i

c _k

P (c _k | w _i )

4.2

5: for w _i ∈ V do

6: for k = 1 to K do

7:

−−→ wcv ik = P (c k | w i ) −→ wv i

8: end for

9: end for

10: for w i ∈ V do

11: idf

−−→ wtv _i = idf(w _i ) ⊕ K

k=1 −−→ wcv _ik

12: /⋆ ⊕

: − → a ⊕ − →

b = [ − → a − → b ], ⊕

k − → a k = − → a 1 ⊕ − → a 2 ⊕ · · · ⋆/

13: end for

14: for D _n ∈ do

15:

: − →

dv D

= − → 0

16: for w i ∈ D n do

17: − →

dv _D

+ = −−→ wtv _i /⋆

D _n

⋆/

18: end for

19: end for

20: for D n ∈ do

21: −−→

scdv _D

= sparse( − →

dv _D

)

4.3

22: end for

4.3

疎率パラメータ

p > 0

− →

dv _D

i

a ⁽ⁱ⁾ n

a _max = avg

n

(max i (a ⁽ⁱ⁾ _n )) = 1 N

∑ N n=1

max i (a ⁽ⁱ⁾ _n ), (37)

a min = avg

n

(min i (a ⁽ⁱ⁾ _n )) = 1 N

∑ N n=1

min i (a ⁽ⁱ⁾ _n ), (38)

| a | + | a 14 |

Algorithm 2 GMM clustering with EM algorithm Require:

x 1 , . . . , x I

= −→ wv 1

T , . . . , −→ wv I T

Ensure: γ i (k), π k , µ _k , Σ k , L

1:

L

θ = { π k , µ _k , Σ k } ^K k=1

L =

∑ I i=1

log ( _K

∑

k=1

π k N (x i | µ _k , Σ k ) )

2: while L

do

3:

θ

γ _n (k)

: γ _i (k) = π k N (x i | µ _k , Σ k )

∑ K

j=1 π j N (x i | µ _j , Σ j )

4:

γ _i (k)

: I k =

∑ I i=1

γ i (k) π k = I _k

I µ _k = 1 I k

∑ I i=1

γ _i (k)x _i

Σ _k = 1 I k

∑ I i=1

γ _i (k) (x _i − µ _k ) (x _i − µ _k ) ^T

5:

L

6: end while

を計算し，すべての

− →

dv D

i

a ⁽ⁱ⁾ _n =

{ a ⁽ⁱ⁾ n if | a ⁽ⁱ⁾ n | ≧ p 100 t

0 otherwise (40)

を適用する．

[5]

p = 0.04

80%

5

本章では実験に用いたコーパスと環境，および実験の結果・考察を述べる．

5.1

それぞれのコーパスのより詳細な情報は本論文末尾の補足資料に載せる．

• 20Newsgroups

–

: 18846

: 7532

–

: 114260

–

:

–

: 20

• livedoor

–

: 7367

: 2221

–

: 91464

–

:

–

: 9

前処理として，英文コーパスはアルファベットをすべて小文字に変換し，アルファベッ トではない文字をすべて除去した．その後，前置詞や接続詞のように，文書の内容に関わ らずに出現する単語（ストップワード）及び

1

Python

“NLTK”

127

和文コーパスは記号や数字などを除去した後に単語を分割した（分かち書き）．単語の 分割に形態素解析エンジン

“MeCab”

“mecab-ipadic-NEologd”

^*4

Web

週に

2

slothlib ^*5

*4

https://github.com/neologd/mecab-ipadic-neologd

*5

http://svn.sourceforge.jp/svnroot/slothlib/CSharp/Version1/SlothLib/NLP/Filter/

StopWord/word/Japanese.txt.

5.2

•

– HP EliteDesk 800 G1 SFF

Windows 7 Professional

– CPU: Intel Core i7-6700

–

: 16GB

•

– Lenovo ThinkServer TS1-40

CentOS 6.7

– CPU: Intel Xeon Processor E3-1226 v3

–

: 16GB

•

–

: Spyder 3.3.2

–

: Python 3.6.7 :: anaconda 1.7.2

64bit

–

: MeCab 0.996

Linux

∗

: mecab-ipadic-NEologd

2018/12/21

5.3

[5]

word2vec

SCDV

5.3.1

SCDV

[5]

word2vec

たものと差し替えたものを考える．

word2vec

word2vec

r

[5]

r = 300

300

[5]

3

SVD + SCDV

RP + SCDV

kPCA + SCDV

5.3.2 fastText

SCDV

SCDV

−→ wv _i

fastText

fastText + SCDV

fastText

word2vec

5.3.3

文書

D n

−−−→ avgdv _n = 1

#D n

∑

w

∈ D

−→ wv i (41)

として取得したものを考える．ただし，ここでの

D _n

−→ wv _i

300

−−−→

avgdv _D

300

SCDV

SCDV

word2vec

fastText

5.4

5.4.1

分類器は線形

SVM

[4] § 7

[15] § 1

one-versus-the-rest

d

d − 1

5.4.2

評価基準は主に正解率，適合率，再現率，

F

•

accuracy

:

Accuracy = TP + TN TP + FP + FN + TN

•

precision

:

Precision = TP

TP + FP

真の結果 正 負 予測 正

TP FP

FN TN

表

1

T

True

F

False

P

Positive

N

Negative

•

recall

:

Recall = TP TP + FN

• F

F-measure, F1

:

F = 2

1

Precision + 1 Recall

= 2 · Precision · Recall Precision + Recall

文書分類の結果をどのような問題に応用するかによって重視すべき評価基準は異なる が，本論文では分類結果の具体的な使用目的を考慮していないため，適合率・再現率の双 方に均等に重みをおいた

F

5.5

SCDV

5.3

6

7

30%

70%

SVM

SVM

C

cross-validation)

(

)

5.5.1

グリッドサーチは与えた変数のすべての組み合わせをすべて試行し，最適スコアとそれ を与える変数の組み合わせを走査する手法である．この手法は結果が訓練データの選び方 に依存するため，汎化性能を保証するために交差検証を組み合わせている（

[15] § 8

1.

n

図

5

20NewsGroup

10

2.

3. n

n

実験では分割数を

n = 5

C

0.1, 0.3, 0.5, . . . , 6.7, 6.9

の

35

1

5 × 35 = 175

5.5.2

各手法のパラメータの値については，ニューラルネットワーク・単語文脈行列の双方に 共通するパラメータは

[5]

shift

κ

γ

fastText

fastText + SCDV

n-gram

1