jackee777のブログ

情報系学生のつぶやき

一部分に重みを加えたベクトルの cos 類似度の計算

※あくまで本記事が役に立つのはレアケースかと思います．

組み合わせの数，ベクトルの次元数および重みづけする次元数を考慮してから読んで欲しい記事です．

後輩のアルゴリズムがどうしても計算量がかかってしまうとのことで，cos 類似度の再計算を避ける方法として1つ出した案です．ipynb は github に公開しています． github.com

初期設定

import numpy as np
import copy
# 重みづけする値
weight = 20
# 重みづけする index 
indexes = [j for j in range(2, 4)]
indexes
[2, 3]

ベクトルの生成

x = np.random.randn(2, 100)
x[:, :5]
array([[ 1.30042348, -1.82751569,  0.84084007,  1.88565653, -0.24484313],
       [-1.26761704,  0.86831757, -0.44518288,  0.33844744, -0.40704083]])

一部分に重みを加えたベクトルの生成（チェックのため）

w = copy.copy(x)
w[:, indexes] *= weight
w[:, :5]
array([[ 1.30042348, -1.82751569, 16.81680149, 37.71313064, -0.24484313],
       [-1.26761704,  0.86831757, -8.90365757,  6.76894872, -0.40704083]])

cos 類似度の関数の定義

# linalg.norm でも出せますが，この方が後々楽なので
def cos_sim(x, y):
    return (x @ y.T)/(np.sqrt(x @ x.T)*np.sqrt(y @ y.T))

cos 類似度の関数の計算

cos_sim(x[0], x[1])
-0.12419248186849967

一部分に重みを加えたベクトルの cos 類似度を計算するための関数の定義

dot の場合であれば，重みによって変わった値だけ計算すればよいです．

  • 例えば，<1, 3, 4>というベクトルの dot 積は26です．
  • 3という値を重み2によって2倍したベクトル<1, 6, 4>の dot 積は53です．
  • この時の変化量は (2の2乗 - 1)* (3の2乗)=27すなわち((重みの2乗)-1) * (値の2乗)=変化量によって求めることができます．

要するに，元の26という値を持っていれば，変化した値のみを計算することで一部分に重みを加えたベクトルの dot 積が出せます．

こうすることで，ベクトルの全ての要素に対する計算を避けることができ，計算が繰り返される場合には計算量が削減できます．

同様に（大変なので，すいません） cos 類似度の分母も変更すると次の関数のようになります．

def weight_cos_sim(x, y, indexes, w):
    return (x @ y.T + (w**2-1) * np.sum(x[indexes] * y[indexes].T) )/\
            (np.sqrt(x @ x.T + (w**2-1) * np.sum(x[indexes] * x[indexes].T))*\
             np.sqrt(y @ y.T + (w**2-1) * np.sum(y[indexes] * y[indexes].T)))

（重みを再利用する場合）一部分に重みを加えたベクトルのcos 類似度を計算するための関数の定義

def reusedweight_cos_sim(x, y, values, indexes, w):
    return (values[0] + (w**2-1) * np.sum(x[indexes] * y[indexes].T) )/\
            (np.sqrt(values[1] + (w**2-1) * np.sum(x[indexes] * x[indexes].T))*\
             np.sqrt(values[2] + (w**2-1) * np.sum(y[indexes] * y[indexes].T)))

一部分に重みを加えたベクトルの cos 類似度の関数の計算

# チェック
cos_sim(w[0], w[1])
0.14208709983961829
# 本番
weight_cos_sim(x[0], x[1], indexes, weight)
0.14208709983961826

reused

# （重みを再利用する場合の）本番
reusedweight_cos_sim(x[0], x[1], [x[0] @ x[1].T, x[0] @ x[0].T, x[1] @ x[1].T], indexes, weight)
0.14208709983961826

まとめ

以上のような形で，同じ結果を得ることができました． 実際に，この関数を用いて効率が良くなるのは，組み合わせの数が多い場合です．

組み合わせが多い場合，計算済みの値を用いて計算を効率化できます． 雑ですが以上です

今年の目標

周りの方がやっているので備忘録として残しておきます．

短期目標

  • 納得のできる修論を書く このタイミングでいうのもなんですが，一番の目標です．
  • ACL, EMNLP, NAACL の本会議またはworkshopに通す 現時点では，非現実的かもですが，ここを目標にしないと筋の良い研究ができないなと思ってます．
  • 国際会議に long paper で通す minimum 一本！！頑張りましょう
  • AtCoder 水色 水色には簡単にはなれなそうなので，水色が目標です．
  • 強い研究室にする 周りの人の影響は大きいので，B4~M2まで育ってほしいと思っています． そして，教授だけでなく私にも還元してくれたら嬉しいなあ( ´∀｀ )

多分やる事

  • どこかの勉強会で話す
  • AtCoder 緑色

長期目標

  • 幸せな家庭を持つ 小学生からの夢なんですが，何を間違ってか博士後期課程に進むという真逆の事をする予定です．ちゃんと考えないと．．．
  • 自分がやりたい社会貢献をする 技術的にできることは凄い増えていて，貢献できそうな場もあるなと感じています．技術を持ってることはさほど重要ではなくて，人や社会に貢献して，フィードバック（意見やお金）を貰ってこそだろうと思うので，可能なことはしていきたいと思っています．

こんなところでしょうか？

インターンなり，どこかで雇ってもらいながら，博士後期課程を過ごすかは悩んでいるんですが，来年まではDC2のチャンスがあるので，それの期待値が最大になるように過ごしていきたいですね．

Stemming and Lemmatization

NLP 自然言語処理

英語の勉強として，翻訳記事を書いていきます．研究しろという話だけどもね．

 

はい，英語の形態素は" "(スペース)区切りで簡単だよって言いますね．
でも，日本語の形態素解析器 MeCab の辞書に「原形」というカラム名があるように
英語にも「原形」があり，原形に変換する手法があります．

MeCab: Yet Another Part-of-Speech and Morphological Analyzer

 

これらの技術に関して，まず stanford のページを日本語訳していきます．

Stemming and lemmatization

そして，英語の stemming および lemmatization には
nltk と stanfordnlp どちらが良いのか見ていきたいなと思います（主題）．

 

Stemming and lemmatization の日本語訳（TOEICは650しかないです）

文法的な理由によって，文章中の単語は organize, organizes, organizing のように様々な形（活用形）で用いられるはずです．
加えて，democracy, democratic, democratization のように類似した意味を持ち派生的に関連した単語の系統（派生語）があります．
多くの場合，これらの単語のうち1つ（検索語）を検索して，文章がその検索語と同じ系統の単語を持つかどうかを判定することは役に立つように思えます．

stemming と lemmatization の両方の目的は活用形や（時々ではあるが）派生語を減らし原形に戻すことです．
例えば， 

am, are, is $\Rightarrow$ be 
car, cars, car's, cars' $\Rightarrow$ car 

であり，文章に適用すると，

the boy's cars are different colors $\Rightarrow$ 
the boy car be differ color

となります（当たり前なんだけど，be なんだとは思いました．．．すいません．）．

 

しかしながら，この stemming と lemmatization にはちょっと違いがあります．

Stemming は通常，ほとんどの場面で正しくなることを期待して単語の終端を切り落とすという粗くヒューリスティックな処理を指す（基本的に，派生的な接辞の除去も含む）．

Lemmatization は通常，語彙や単語の形態素解析を利用して適切に操作することを指し，一般的に活用系の末尾のみの除去や基本形や辞書に存在する単語 lemma として返すことである．

例えば "saw" が与えれた場合は，stemming では "s" だけを返すかもしれないが，lemmatizeation では品詞に応じて see か saw が返されることが期待される．この2つの違いは stemming は派生語を崩壊させやすく，lemmatization は単語が持つ活用形を壊しやすいことだろう．これらに対する言語処理は索引処理（形態素解析器？構文解析器？）などの追加プラグインとして提供されることが多く，商用利用でもオープンソースでも見られる．

 

最も頻繁に見られる英語の stemming アルゴリズムとしては，経験的に早いPorter's アルゴリズム（Porter, 1980）がある．全体のアルゴリズムは長すぎて載せることができないが，一般的な例を示す．Porter's アルゴリズムは単語の削減を5段階に分け，それぞれを順に適用した結果を返す．それぞれの段階では，接辞が最も長くなるルールを適用するなどの方法が用いられる．

第一段階では，次のようである．

SSES   ⇒ 　SS　　Ex. caresses ⇒   caress
IES　　⇒ 　I　　  Ex. ponies    ⇒　poni
SS　　 ⇒ 　SS     Ex. caress     ⇒   caress
S　　　⇒        　  Ex. cats        ⇒   cat

残りのルールの多くは助数詞の概念を用いている．
助数詞は単語が十分に長いかを見るために音節の数を大まかに調べる．助数詞は，ルールに合致した語幹の一部を見つけることよりもルールに合致した接尾辞を見つけるのに向いている．

例えば， 次のルールは replacement を replac にするが，cement は c にはならない．

(m > 1)　EMENT　 ⇒ 　

Porter Stemmer の公式サイトは Porter Stemming Algorithm で
その他にも one-pass Lovins stemmer (http://www.cs.waikato.ac.nz/~eibe/stemmers/ ) や Paice/Husk stemmer (https://www.scientificpsychic.com/paice/paice.html) がある．

f:id:jackee777:20190509115747p:plain

各 stemmer の比較

上の図はこれらの手法の違いを示したものである．
(かなり違いますね，analysis can reveal features のところとかわかりやすい)
Stemming による処理は言語固有であるが，lemmatization と比べると必要とする情報は少なくて済む．Lemmatization では語彙の網羅や優れた形態素解析が必要とされるからだ．また，特定のドメインにおいては特定の stemming ルールが必要かもしれない．Stemming では厳密な 結果ではなく，等価なクラスを形成するかが問題である．

各単語の見出し語を正確に見つけるために full （全体？）に形態素解析を施す自然言語処理のツールとしては，stemmer よりも lemmatizer のほうが良いかもしれない．
全体に形態素解析を施すことは検索においてちょっとした利点がある．しかし，これ以上のことを述べることは難しい．なぜなら，正規化の形では英語の情報検索全体のパフォーマンスにほとんど影響がないからだ．クエリの面では有効だが，同じくらい他の点で問題がある．
うまくいかない例としては，次の単語全てに Porter stemmer を適用すると，すべて oper になる．

operate operating operates operation operative operatives operational

しかし，operate は一般的な動詞であり，operational and research のような価値のある情報が失われる．

 このような場合において，lemmatizer を使用しても特定の場合に登場する特定の活用形に対応できないため問題を完全に解決することはできないでしょう．
例えば，operate and system が登場する文章は operating and system というクエリと一致しません．
単語の正規化によって得られるより良い価値は言語形態論の正式な問題よりも単語使用時の実用的な問題に依存しています．

このことはスペイン語やドイツ語のような形態論がさらに多い言語によって異なります．European CLEF (おそらく学会名)では，stemmer を使用する方がメリットが大きいとしきりに言われている．

 

意外だったんですけど，言語処理のツールとしては lemmatization の方が良いかもくらいのことは触れているんですね．後半で勿論タスクにもよるけど，とも言っていますが．
Is it advisable to choose lemmatization over stemming in NLP? - Quora とかでも話されていて，まあそうなんだろうなあという感じです．

自分は stemming は欲しい情報がかなり削られているように感じるので，lemmatization を使用することが多いです．

 

## 本当はここから，nltk, stanfordnlp, spaCy の違いを書く予定でした
コードと結果見ながらやっていく予定でしたが，2019/09 現在であまり時間が割けてません．3ヶ月下書きのまま放置してしまっていたので，とりあえず公開しておきます．続き書きたいです。。。

学科の選び方

学科選び 学科選択 雑談

なんとなく，昔知りたかったことを昔の自分のために書いておきます．ふと思っただけなので，適当に短く終わらせます．

自分が選んだ学科が自分にとって一番いい学科（情報系の学科）だったと思います．しかし，自分は学科を超が付くほど適当に選びました．

さて，高校生の自分はどのように学科を選ぶべきだったんでしょうか？

 面接中，こんなやり取りがありました

面接官「この学科を選んだ理由はありますか？」

よくある？質問の一つです．素直な私はこう答えました．

私「この学科には運で入りました．機械系と情報系で2択で何となく選びました．」

ある意味，非常に残念な回答です．でも事実です．学科を深く学びたい理由は大学で得たもので，決して受験時の理由ではないからです．

私に適した質問はおそらくこうです．

面接官「あなたの学科の面白みは何ですか？」 or 「あなたの学科を選んでよかったことは何ですか？」

これは大学時代の質問となります．そうなると，私は話せることが沢山あるので，オタク特有の早口でこういうかもしれません

私「私の学科では～～中略～～中略～～～～～～～～～省略～～～～～～～～～なので，結果として機械ではなく人の考えを学べるという点が非常に面白く，入ってよかったと思います」

 これで良いのでしょうか？

私としては，これでもいいです．なぜなら運よく自分に合った学科を選べたので． でも世の中そうではないですね．神様が「運」でこの学科を選びました，というのは「なんとなく」と言っているのと同じです． 人と話す上で，人が理由を聞くうえで，「動機」というのは大事ですし，何より学科というのは自分の職種や人生に大きく影響します（というか，するものであるべきです）．※べきは言い過ぎです．

できることならば，高校の時に私は知るべきでした．どの学科に入るべきなのかを．

しかし，高校の時に入るべき学科を知る事なんてできるんでしょうか？

私個人の能力ですと，昔の自分にもワンチャンスはあったと思います．が，ほとんどノーチャンスだったなと思います．

何故でしょうか？理由はいくつかありますが大きいものを上げます．

  • 学部2年の時でも，まだ自分の学科がベストとは思っていなかった（機械系に転科できるかを数回検討した）
  • 学部4年生～修士2年まででオープンキャンパスを案内しているが，上辺以上のことは話せず，なんとなくの理解で終わってしまう．

どういうことかというと，修士になって初めて情報系の分類ができるようになりました．それまでは情報系とはなんなのかを私は知らず，上辺だけで考えていました．

「三角関数ってどこで使うの？何の役に立たないよね」状態だったんですね．あれ？学科と関係ないように思えますか？しかし，今の私には関係があるように思えます．

三角関数が関係あるわけではないです．「どこ」そして「何」が関係あります． 理数系の多くの学科で，数学というツールは共有ですが，「使い道」や「使い方」は多くの点で違います． （わからなくて良いですが，私にとっての cos の一番の利用価値はベクトル間の類似度です．ですが，テイラー展開であったり，力学の作用で使う方もいらっしゃるかなあと思います．情報系だと機械学習，シミュレーション，ロボット工学等で見られますね．） qiita.com

話が逸れました．なぜノーチャンスだったと思うのかですが，それは私が学んでいたのは三角関数のみで，何に使うかを考えたことがなかったからです．

では，何に使うかを考えるのが良いのでしょうか？

正直な話，何に使うかを知ってもあんま面白くないなあと自分は思います．何に使うかを知れば，その使い道として学科のイメージは湧きやすくなるかもしれませんが，もし「一生」学ぶかもしれないと思うなら，理由としてはちょっと弱いです．

cos がロボット工学で使えるって高校生の時に知ってもどうでも良いやん．そんなの．って当時の私が思ってしまいそうなので，何に使うかを知るだけでは意味がないという結論に勝手にしました．すいません(・_・)

じゃあ，何をすればよい学科を選べるのか

ですね．それはやっぱり上辺からの脱出しかないと思います．なんとなくで話す．なんとなくで理解するというのを辞めるということです．

先程の cos の話に戻ります．3. が高校生の自分がやったらよかったなと思うことです．

  1. cos が計算できるというのは，数学の理解です．
  2. 次に，cos がロボット工学に使えるというのが，使い道の理解です．
  3. なぜロボット工学に cos を用いるのかを知るというのが，過程の理解です．

つまり，ロボット工学で cos を使いたいと誰がなぜ思ったのかです．（なんとなくでも数式を見れば）cos を用いることはロボットの制御に欠かせず，なおかつ，非常にシンプルな形にする方法だと言えます．私は，それを誰がやったかは知りませんが，数式を見れば，何をしたかったかがわかります．そこに面白みを感じますし，学びたいと思えます．

www.mech.tohoku-gakuin.ac.jp （わざと大学の資料を選びました・・・）

こちらの方がずっと良さそうですね（対数の歴史は自分も好きです）． lemniscus.hatenablog.com

物語の初めと終わりだけを読んで知った気になるのではなく，物語をすべて読み解く．そうすれば，自ずと多くの理解が深まります．学科もその一つです．

そして，物事の過程を理解することができれば，次は自分が物語を書くことができます．

（そんなこんなで，私にとっては一つの関数をとっても素敵なものに思えてしまいます・・・）

最後に

最後に，私が普段大切にしていることを書いておきます．

疑問や思いを大切にする．ということです．「あれ？おかしい」，「うん？（なんか変）」というのは自分固有のものかもしれません．同様に，「面白い」，「楽しい」，「嫌い」というのも自分固有のものかもしれません．ただ，それを一時の感情とすれば，それは過ぎていくものかもしれませんが， 積み重なれば，それは「人」です．そして「自分」です．

自分というのは意外なところに落ちてます．少なくとも，僕は知りませんでした．今は知ってます．上記のものが私の研究動機だからです． （ちなみに，自分の使う一人称が「私」，「自分」，「俺」，「僕」，「ワイ」，「苗字」などがあるんですが，「僕」を使うのが内面に触れる時，「自分」を使うのは外から見る時などの傾向があります．）

最後まで読んでくれた方，ありがとうございました． （学んだ結果，どれもやりたい人は二刀流・三刀流をやればいいのかもしれないですね．学科も枠組みの一つでしかないので）

おまけ

最後に面白いことを言うと，私が中高の時に苦手としていたのは確率・ベクトル・積分でした． 今私が得意としているのは確率とベクトルです（積分よりは微分の方が使うので得意になりませんでした）． 私が確率とベクトルを苦手としてたのは，使い方を知らなかったからだなあと今は思います．

cython で numpy の dot を学ぶ - part 1

※こちらの記事は，暇があるたびに詳しくなっていきます（2019/06/27）

はじめに

どうも，cython の良い導入ってないよなあって感じてるものです．最近は cpp も使えるらしく，非常に便利だと思います． 当方，O'REILLY の Cython は昔読んだかもですが，読んだかを忘れました．

中身

cython の導入にはややこしいことがあるので，それを理解する．そのために，numpy.dot を実装する．全部のコードはこちら．

ファイル構成

まず，ファイル構成を以下のようにして，setup.py を書きます．

cython_lib
- __init__.py
- calculation.pxd
- calculation.pyx
setup.py

これだけで基本的には十分．python setup.py install を実行すると，cython_lib/calculation.c が出来ますが，自動生成なので読むものじゃないです．

setup.py を書く

参考はこちら．

from Cython.Distutils import build_ext
from Cython.Build import cythonize
import numpy as np
from setuptools import setup, Extension

ext_modules = [
    Extension('cython_lib.calculation', # module name
              sources=['cython_lib/calculation.pyx'], # necessary source code(.pyx and .c)
              include_dirs=[np.get_include()], # include files
              compiler_directives={'language_level' : "3"},
              ),
]

setup(
    name='cython_lib',
    packages=['cython_lib'],
    version='0.0.1',
    ext_modules=cythonize(ext_modules),
    cmdclass={'build_ext': build_ext}
)

cython_lib/calculation.pyx を書く

とりあえず，dot をテストするだけなら，ただの python です．

#!/usr/bin/env cython
# cython: boundscheck=False
# cython: wraparound=False
# cython: cdivision=True
# cython: embedsignature=True
# coding: utf-8

cimport cython
import numpy as np
cimport numpy as np

# 1×1 が答えの時
cpdef REAL_t cnum_dot_one(np.ndarray X0, np.ndarray X1):
    return np.dot(X0, X1)

# n×n が答えの時
cpdef np.ndarray cnum_dot(np.ndarray X0, np.ndarray X1):
    return np.dot(X0, X1)

 

cython_lib/calculation.pxd を書く

.pxd ファイルは c 言語で言う header ファイルと同じなので，1×1 が答えが答えとなる時の REAL_t の型だけ定めます．

import numpy as np
cimport numpy as np

ctypedef np.float32_t REAL_t

速度の計測

これはただの numpy なので，速度に違いはない．

本題

cython を適当に書くだけだと簡単なのはわかったと思うので，じゃあちゃんと c 言語で書こうと思う．としても，dot の比較をしても，numpy 相手では速度が上がらないという同じ結論になります． （次元数による比較によると，次元数が小さい時は jit が最速ですがそうでない時は numpy が速いそう.）

なんで numpy がこんな速いのかを理解していく過程で，cython を学びましょう．大体学べる．

とりあえず，ここまで

予定としては，openblas を使って numpy に追いつくところまでやります．

本当は wrapper を作る必要があるので，そこは勉強していきたいですね．また，openblas も scipy の linalg も元は fortran なので，fortran からの適用を学ぶ必要もあります（fortran は読めもしないけど）．

 

ABC129 E - Sum Equals Xor

python プログラミング

当初，書こうと思っていたわけではないので，文章の方は適当である．図が多分説明してる．．．

一番，難しいのは dp table の最初の値じゃない？と思った． とりあえず，一桁の時を考えると欲しい answer はこうなる．dp table の最初の値がわかれば解ける人は多そうなので，この情報で帰ってもいいと思う．

f:id:jackee777:20190616022006p:plain
ABC129 E. dp 最初

まずは，確定の時の初期値である 0(dp[0][0]) の事は考えず，未確定の時の初期値である 1(dp[1][0]) をどう使うかを考える．最上桁の値が 1 の時と 0 の時で確定するかしないか，次の候補の数が異なる．

f:id:jackee777:20190616022231p:plain
ABC129 E. dp 候補の抜き出し

これは，2桁以上を考えるとわかるが，確定した値をどう使うかを考える．候補は [0, 0], [0, 1], [1, 0] の3つあるので，それぞれを3倍する必要がある．

f:id:jackee777:20190616022313p:plain
ABC129 E. dp 確定した値の継続

2桁以上でも上手くいくかを考える．

f:id:jackee777:20190616022354p:plain
ABC129 E. 2桁以上の時

ここまでくれば反映させるだけなので，コードを書くと

L = input()
modulo = 10**9+7

dp = [[0] * (len(L)+1) for i in range(2)]
dp[1][0] = 1
  
for i in range(len(L)):
  if L[i] == "1":
    dp[0][i+1] = dp[1][i]
    dp[1][i+1] = dp[1][i] * 2
  else:
    dp[1][i+1] = dp[1][i]
  
  dp[0][i+1] += (3 * dp[0][i])
  dp[0][i+1] %= modulo
  dp[1][i+1] %= modulo


print((dp[0][-1]+dp[1][-1]) % modulo)

でした．print 時の modulo 忘れてて大変だった．．． 色んな人のコードを見たけど，普通は i の index と 0, 1 の index が逆らしい．

BabelNet 関係をメンテナンスした

雑談

ここ6ヶ月ほど，WordNet と BabelNet に触れることが多いので，パパパーっと BabelNet の方をメンテナンスしている．

残りは，Babelfy の offline version だけというとこまで来たので，とりあえずよかったなあと思う．

 

BabelNet 用 python package

https://github.com/jackee777/babelnetpy

BabelNet 用 offline server

https://github.com/jackee777/babelnet_offline

Babelfy Reimplementation 用の BabelNet server

https://github.com/jackee777/babelnet-lookup

感想とかあったら，書いてくれるか issue を投げてほしい所

 

ただし，BabelNet というのは便利なようで，WordNet の関係を非常に多くの箇所で壊してしまうので，そもそもここの改善がされないとなあという感じ．

加えて，BabelNet は研究目的でしか利用できないことが大きな弱点すぎる。。。

 

 

WSD は自分の sub task という感じ．