2018-03-22

kaggleのメルカリ価格予測コンペの反省とword2vec、Embeddingについて

機械学習

そういえば年末年始あたりにメルカリのコンペに冬休みの自由研究として参加してました

他のことに追われていたらいつの間にかコンペが終了したので反省という名の手法の振り返りをする

コンペ自体の詳細は以下のリンクから

Mercari Price Suggestion Challenge | Kaggle

何をするコンペだったかというと主催側で商品名、商品の品質(5段階)、商品のカテゴリ名や説明文などが100万件以上あるデータを提供するのでそこから与えられた商品の価格を予測してねっていう感じのコンペ

価格の予測というわけで二値分類とかではないから半教師分類が使えなくて困った(値段予測を10ドル区切りのnクラス分類と置けばゴリ押しできたかも)

まずは自分が行ったデータ分析をば。コードはここ

与えられた訓練用のデータtrain.tsvの欠損値の確認を最初に行う~~tsvファイルで与えられたので読み込みで最初こけた~~

# 欠損値の確認
train_df.isnull().sum()

---
train_id                  0
name                      0
item_condition_id         0
category_name          6327
brand_name           632682
price                     0
shipping                  0
item_description          4
dtype: int64

訓練データは140万件ほどある中、brand_nameは63万件も欠損値があることがわかる。
学歴の偏差値でもそうだが、シャネルやルイヴィトンといったブランド名が付与されているだけである程度の価格は検討つきそうという直感があったので、brand_nameが付与されているか否かの二値の値を新たに与えることにした

# brand_nameが存在するなら1を返し、無いなら0を返す
def isBrandname(x,name):
    brand_name = str(x['brand_name'])
    if(brand_name==name):
        return 0
    return 1

fill_nan_brand_name = "Unknown"
train_df['brand_name']=train_df[['brand_name']].fillna(fill_nan_brand_name)
train_df['is_brand_name'] =  train_df.apply(lambda x: isBrandname(x,fill_nan_brand_name), axis=1)

次にcategory_nameの中身を確認した。value_countで中身を見てみると一部でこんな感じ
f:id:Owatank:20180322111441p:plain

カテゴリ数が１って140万もデータあるのになんか嫌だな・・・one-hot絶対したくねえ・・・と思い悩む。
カテゴリの書式はどれも/でsplitできそうだと考えて左から１つsplitしたものを取ってそれをfirst_category_nameという新たなデータとして加えることにする

def get_first_category_name(x):
    category_name = str(x['category_name'])
    return category_name.split('/')[0]

# category_nameの第一カテゴリを抜き取る
# 欠損値は Unknown で埋めておく
fill_nan_category_name = "Unknown"
train_df['category_name']=train_df[['category_name']].fillna(fill_nan_category_name)

train_df['first_category_name'] =  train_df.apply(lambda x: get_first_category_name(x), axis=1)

first_category_nameのvalue_countは次のようになった

f:id:Owatank:20180322112005p:plain

カテゴリを一つ抜き取ったので全体として意味があるものというのは失われてしまった
カテゴリは３つくらいsplitできそうだったので同様にsecond_category_nameとthird_category_nameも加えた

ここでグのサマーインターンのときに~~盗み聞きした~~懇親会での言葉を思い出す。
日付という文字列のデータから日付を得るように、nameから何かしら得ることはできないだろうか

ということでbrand_nameが無いものに対してnameからブランド名を抜き取ってそれをbrand_nameとして与えてあげることにする

brand_dict = dict(train_df['brand_name'].value_counts())

def extract_brandname_from_name(x,b_dict):
    name = str(x['name'])
    name_split_list = name.split(' ')
    if(x['is_brand_name'] != 1):
        for item in name_split_list:
            if(item in b_dict):
                return item
    return str(x['brand_name'])

train_df['new_brand_name'] =  train_df.apply(lambda x: extract_brandname_from_name(x,brand_dict), axis=1)

new_brand_nameという名前で新たに作ったので、これに対しても最初に行ったブランド名があるか無いかの処理を同様に行った
結果としては10万件ほどブランド名があるものが増えた。

だいたいこんな感じでデータの分析を終えた。自分ではこれがまだ精一杯(´･ω･)

分析して新たに作ったデータで予測を行う学習モデルを構築する

# 入力層
input_dim = 8
X = tf.placeholder(tf.float32, shape=[None, input_dim], name="input")
t = tf.placeholder(tf.float32, shape=[None, 1])
# パラメータ1
stddev = np.sqrt(2.0 / input_dim)
input_node_num = 128
W1 = tf.Variable(tf.truncated_normal([input_dim,input_node_num], stddev=stddev))
b1 = tf.Variable(tf.constant(0.1, shape=[input_node_num]))

# パラメータ2
stddev = np.sqrt(2.0 / input_node_num)
hidden1_node_num = 256
W2 = tf.Variable(tf.truncated_normal([input_node_num,hidden1_node_num], stddev=stddev))
b2 = tf.Variable(tf.constant(0.1, shape=[hidden1_node_num]))

# パラメータ3
stddev = np.sqrt(2.0 / hidden1_node_num)
hidden2_node_num = 512
W3 = tf.Variable(tf.truncated_normal([hidden1_node_num,hidden2_node_num], stddev=stddev))
b3 = tf.Variable(tf.constant(0.1, shape=[hidden2_node_num]))

# パラメータ3
stddev = np.sqrt(2.0 / hidden2_node_num)
output_W = tf.Variable(tf.truncated_normal([hidden2_node_num,1], stddev=stddev))
output_b = tf.Variable(tf.constant(0.1, shape=[1]))
keep_prob1 = tf.placeholder(tf.float32) # ドロップアウトする割合
keep_prob2 = tf.placeholder(tf.float32) # ドロップアウトする割合

layer1 = tf.nn.relu(tf.matmul(X,W1) + b1)

layer2 = tf.nn.relu(tf.matmul(layer1,W2) + b2)
layer2_drop = tf.nn.dropout(layer2, keep_prob1)
layer3 = tf.nn.relu(tf.matmul(layer2_drop,W3) + b3)
layer3_drop = tf.nn.dropout(layer3, keep_prob2)

output_layer = tf.matmul(layer3_drop,output_W)+output_b

p = tf.nn.relu(output_layer,name="output")
# 荷重減衰
norm_term = tf.nn.l2_loss(layer1) + tf.nn.l2_loss(layer2) +tf.nn.l2_loss(layer3)
# 正則項
lambda_ = 0.0001
# 損失関数(MSE)
loss = tf.reduce_mean(tf.square(p - t))+ lambda_*norm_term
#loss = tf.reduce_mean(tf.square(p - t))
# 学習アルゴリズム
optimizer = tf.train.AdamOptimizer()
train_step = optimizer.minimize(loss)

いつも通りのMLPで構築してみた。

しかし結果のスコアは0.713ほどだった。(値が小さい方がいいからクッソ悪い)
何故だと悩んで、そういえばitem_description使ってないな・・・と思った。
他の参加者はitem_descriptionを使用しているのだろうか？と思い、カーネルを漁ることに

するとこんな感じのコードを見つけた

tok_raw = Tokenizer()
tok_raw.fit_on_texts(raw_text)

train_df["seq_item_description"] = tok_raw.texts_to_sequences(train_df.item_description.str.lower())
test_df["seq_item_description"] = tok_raw.texts_to_sequences(test_df.item_description.str.lower())
train_df["seq_name"] = tok_raw.texts_to_sequences(train_df.name.str.lower())
test_df["seq_name"] = tok_raw.texts_to_sequences(test_df.name.str.lower())

!?
え、何これは・・・

層の定義においてはこんなだった

emb_name = Embedding(MAX_TEXT, 50)(name)
emb_item_desc = Embedding(MAX_TEXT, 50)(item_desc)

!!?!?

Embeddingって何だ・・・と当時の自分は思ったが、試しにこれらを使ってnameとitem_descriptionを特徴として使いつつ、自分で得た新たなデータも加えて学習させてみるかと試して見たところ、スコアが0.4656とハチャメチャ上がった

当時は全くもって謎だったが、最近自然言語処理について調べたりしていたのでここで定義していたEmbeddingはまずEmbed自体の意味が埋め込みという意味で、埋め込みというのは文字を実数のベクトルに変換して特徴として扱えるようにするって感じなのかなと自分で考えた。

だから最初にtok_raw.texts_to_sequencesでitem_descriptionの文章を単語に分割したり、ストップワードの排除やステミングといった前処理をかけてあげたりしていたのだ・・・

埋め込みによるベクトルの変換においてはappleなら[1,0,0,0,0,...]といったone-hotのような変換ではなく、apple = 果物+赤+...といった単語の足し算で表現するようにして[1,0,0,1,0,...]としたり、あえて単語に重みをつけて表現することもできるそうだ

最近読んだポアンカレ埋め込みという論文では、word2vecではユークリッド空間による埋め込みを行っているが、双曲線空間の中に埋め込むことで、ユークリッド空間の埋め込みより単語同士の類似性、つまり距離や潜在的な階層表現などにおいてより優れる結果を出せると書いてあった。しかもベクトルによる表現も倹約に表現できるらしい。

双曲線空間すげえ！！！！！！！！！！！

無敵じゃんこんなの・・・概要だけでめちゃくちゃワクワクしたし銀河を感じてしまった・・・
しかしこの論文で出てきた最適化方法あたりでリーマン最適化、測地線、などなど聞いたこともない単語がたくさん出てきて全然わからなかった
どうやら噂の多様体というものを知る必要があるらしい。

今まで機械学習って確率統計とか最適化数学あたりが重要なんかなーと思っていたが、自然言語処理において幾何学ってこんなロマンがあるし、こういった問題に対して登場してくるのかと思える良い発見ができるコンペだった。結果はボロクソだったが

2018-02-24

ベクトルの射影と内積について

線形代数

確率統計の本を読んでいて、共分散行列あたりで射影の話が出てきた。
そういえば射影についてのイメージがあやふやだったなと思ったのでメモ
かなり前に読んだフーリエの冒険を参考にした。

f:id:Owatank:20180224140956p:plain

上の画像において $\vec{B}$ を $\vec{A_1}$ と $\vec{A_2}$ に射影するというのは $\vec{B}$ を射影したい方向のベクトルと直交するように下ろして交わった時のベクトル $\vec{P_1}$ と $\vec{P_2}$ が射影ベクトルとなる。

何をしているかといえば $\vec{B}$ は $\vec{A_1}$ や $\vec{A_2}$ ではどういったもので表されるかみたいなものを $\vec{P_1}$ 、 $\vec{P_2}$ が示している。 $\vec{B}$ が卵を表すベクトルで $\vec{A_1}$ がサンドイッチを表すベクトルなら $\vec{P_1}$ はタマゴサンドを表す(卵を使ったサンドイッチのネタならなんでもいいけど)。

なんで直交していないといけないんだろって思ったけど $\vec{P_1} + \vec{P_2} = \vec{B}$ という関係が成り立つから何となく察した。

実際に $\vec{B}$ を $\vec{A_1}$ に向かって垂直に下ろしたとして、交わる $\vec{P_1}$ を求めてみる。

f:id:Owatank:20180224142903p:plain

$\vec{B}$ を $\vec{A_1}$ に向かって垂直に下ろしたときのベクトルは $\vec{P_1} - \vec{B}$ で表せる。
$(\vec{P_1} - \vec{B})$ は $\vec{A_1}$ と垂直だから内積は０になるのはわかる。
そして $\vec{P_1}$ は $\vec{A_1}$ の長さが違うだけのものなので(スカラー倍)以下の関係になっている。

$\vec{P_1} = x\vec{A_1}$ (xは定数)

つまり $\vec{P_1}$ は定数x を求められれば実質求められる。~~いくつか悪さできそうな関係式~~ $\vec{A_1} \cdot (\vec{P_1} - \vec{B}) = 0$ と $\vec{P_1} = x\vec{A_1}$ から

$\vec{A_1} \cdot (\vec{P_1} - \vec{B}) = 0$ は $\vec{P_1} = x\vec{A_1}$ を代入して
$\vec{A_1} \cdot (x\vec{A_1} - \vec{B}) = 0$ になる。これを展開して
$x\vec{A_1} \cdot \vec{A_1} - \vec{A_1} \cdot \vec{B} = 0$ つまり $x\vec{A_1} \cdot \vec{A_1} = \vec{A_1} \cdot \vec{B}$ が得られる。
x だけの式に変形して

$x = \frac{ \vec{A_1} \cdot \vec{B}}{\vec{A_1} \cdot \vec{A_1}}$ 　 $x\vec{A_1} = \frac{ \vec{A_1} \cdot \vec{B}}{\vec{A_1} \cdot \vec{A_1}}\vec{A_1}$

最後両辺に $\vec{A_1}$ をかけたのは $\vec{P_1} = x\vec{A_1}$ の右辺に上記を代入したいため。結果として

$\vec{P_1} = \frac{ \vec{A_1} \cdot \vec{B}}{\vec{A_1} \cdot \vec{A_1}}\vec{A_1}$ が得られる。

ただの定数xは分子も分母も内積な形で表されていたのだ・・・
$\vec{A_1}$ と $\vec{B}$ 自体が直交していたらxの分子の内積は０になるので射影した値も０になるのがわかる。

中学か高校生の頃にこんな感じの式を見たことはないだろうか？

$\vec{X}\cdot \vec{Y} = |\vec{X}| |\vec{Y}|cos\theta$ 、 $\vec{X}\cdot \vec{X} = |\vec{X}|^2$

内積ってやつだ。これでさっき得られた式を書き換えてみる。

$\vec{P_1} = \frac{ \vec{A_1} \cdot \vec{B}}{\vec{A_1} \cdot \vec{A_1}}\vec{A_1} = \frac{ |\vec{A_1}| |\vec{B}| cos\theta}{|\vec{A_1}|^2}\vec{A_1} = |\vec{B}|cos\theta \frac{\vec{A_1}}{|\vec{A_1}|}$

うーん。分子と分母の内積な形のときより得体の知れない形になってしまった。cosを何とかしたい
f:id:Owatank:20180224160416p:plain
三角関数でよくみたやつだ。ん・・・？待てよ・・・？
cosをベクトルの長さから表すことができるんじゃないか！？
f:id:Owatank:20180224161439p:plain

$cos\theta = \frac{|\vec{P_1}|}{|\vec{B}|}$ より $|\vec{P_1}| = |\vec{B}|cos\theta$ 、ベクトル $\vec{P_1}$ の長さが得られた。おほ＾〜

これらのことから
求めたい射影ベクトル $\vec{P_1} = \frac{ \vec{A_1} \cdot \vec{B}}{\vec{A_1} \cdot \vec{A_1}}\vec{A_1}$ の分母や分子の関係式は $\vec{P_1} = |\vec{B}|cos\theta \frac{\vec{A_1}}{|\vec{A_1}|}$ という得体の知れない関係式に直すことができ、それは f:id:Owatank:20180224163131p:plain
$\vec{P_1}$ は $\vec{A_1}$ の方向(単位ベクトル)に $|\vec{P_1}| = |\vec{B}|cos\theta$ の長さだけ進んだベクトルという見方をすることできた。

そもそも射影って何が便利なんだろと考えたけど $\vec{B}$ をりんご、オレンジ、桃の３つの果物を合わせたミックスジュースだとしたらそれを各成分ごとに分解したいといった時に便利なんかなと考えた。いや逆に射影ベクトルからミックスジュースのベクトルを作ることも可能なのか・・・？

今更だけど内積って二つのベクトルが同じ向きではないときに、どっちかのベクトルの方向に合わせて( $|\vec{B}|cos\theta$ のような処理)をして二つの長さを掛け合わせるといったイメージでいいのかな

内積もそうだけど距離というか位相というか連続や隣の概念のようなものについても勉強すべきだなと思った。

参考アンド宣伝
フーリエの冒険
 フーリエの冒険
 フーリエの冒険

2018-02-11

機械学習の勉強を始めて1年ほど経ったので振り返る

機械学習

あまりこういうことするのは好きではないが、これからも勉強を続けていってどれくらい成長できたか確認したいと思ったので、タイトル通り機械学習の勉強を始めて1年ほど経ったので振り返ることにした。

始めた発端

学部2年の10月頃、大学の授業にあまり追われなくなり暇になってたところ先輩から「はじめてのパターン認識」という本を貸してくれたので読むことにした。
わからないところも多かったけど、パターン認識って(プロトタイプとかからの)距離から分類したり、勾配とか使うんだなーくらいのイメージが付いた。
授業もあったしノートに写しながら読んでいたので、読み終わるのに2ヶ月くらいかかった記憶がある。

その後1〜2月頃(うろ覚え)にTensorflowを使ったディープラーニングのアルバイトもどきをやってみないかと声をかけられたのでやることにした。
このアルバイトではライブラリの使い方や導入方法、簡単な回帰や分類の記事を書いたり(バージョンの変化による)修正したりするものだった。
始めた頃はコードで定義されている損失関数やソフトマックスってなんだ？みたいな雰囲気でディープラーニングをやっている状態で今覚えばかなりひどかった。

3月

Tensorflowで構築したモデルをAndroidアプリとして動かしたいと言われリファレンスを読みまくる日々に追われた。
この記事を参考にしてアヤメの分類をアプリとして動かしたり
f:id:Owatank:20180211114241p:plain
この方法だとc++でなぜかコードを書かないといけなくて辛かった。
その後モルガンさんの素晴らしい記事を見つけて、おかげでモデルのファイルを読み込んで入力値を渡してあげるだけで済むようになって咽び泣いた。

春休みに入って時間もできたので真面目にディープラーニングの仕組みみたいなものについて勉強しようかなと思い始める。
何から始めればいいか悩んでいたところ何故か会社に「ゼロから作るDeep Learning」という本が転がっていたのでこっそり借りて読んだ。
はじパタを事前に読んでいたおかげかサクサク読めたしTensorflowを使ってネットワークの構築で定義していたtf.layers.conv2dのパラメータの意味や、tf.nn.dropoutとかの意味がわかっていってめっちゃ楽しかった。伏線回収しているような気分だった。

4月~8月

魚の本のおかげで、もっとディープラーニングについてしっかり勉強したいなと思うようになって次に研究室に置いてあった青くてイルカの絵が載っている岡谷さんの「深層学習」という本を読んだ。自己符号化器の内容が読んでいて一番ワクワクした。
かなり授業を取ったので勉強に充てる時間が全くなくて半分以上読む頃には夏休みに入っていた。

それとは別で物体検出というものに興味を持って、SSDという手法を知る。自分で実装してみたいと思いまず仕組みを知ろうと思った。SSDの行なっていることを知るにはRCNNやSPP-netなどの論文から読まなくてはいけないらしく初めて論文を読んだ。英語力がスカスカで一つ読むのに2週間以上かかった。

論文を読んで思ったのは、論文内で定義されている損失関数などの数式の意味があまり理解できなかったということ。
ディープラーニングの仕組みではなく数学の基礎的なものをやり直そうかなと思い始めた。

9月

初めての機械学習のインターンに参加した。割とボロボロな結果だったけど、機械学習にしてもディープラーニングにしても、必要なデータは自分で整形したり特徴量の絞り込みをしたりしなくてはいけないということを痛感する。

今までMNISTやアヤメのデータセットなど用意されたデータでやっていたのでこれはかなり自分の中では大きかった。

10月~11月

9月のインターンのこともあり、「戦略的データサイエンス」という本を借りて読んでいった。この本のおかげで、エントロピーなるものや混同行列に決定木など色々なことを知ることができた。
またデータセットの整形、前処理ということにも慣れようと思い、kagglのフリーのデータセットとpandasというライブラリを使ってデータの操作の練習をした。「Pythonによるデータ分析入門」という本が図書館にあったのでちまちま借りた。

11月の最後に某リクのデータサイエンティストイベントなるものがあり何故か参加できた。学部生が自分だけで辛かった。
所属している研究室は卒業単位が取れないと研究させてくれない(研究スペースすら割り当てられてなかったけど)らしいので、面接のときに研究内容を話すことが全くできなかったし、面接に来てくれた各企業の人からは「いや絶対院に行ったほうがいいよ」と言われて進路相談を受けている気分だった。優秀な人を取りに来ているのにすごく申し訳なかった。

他の参加者からエントリーシートがスカスカじゃんとか、googleに就職したいとか書いておこうよwとか今の時期から機械学習の勉強してるみたいだけどブームすぎたらどうするの？とか~~イキられて~~言われて懇親会のピザがしょっぱかった。
旧帝大の修士や博士というだけで学歴ビーム喰らっているのにさらにオーバーキルされた気分だった。

それでも企業の人やイキリ修士、博士の意見から、機械学習の勉強をするのはいいとして、一体どういったことをしたいのか(研究としても仕事としても)ということを考えようと思った。今まではわかると楽しいからやっていたという感じで何がしたいかは全くなかった。

12月

4月からの研究テーマや将来何しようかなと考えつつ、数学的な基礎を固めようと思い「プログラミングのための線形代数」という本を読んだ。
1年生の頃は単位のためと適当にやっていた線形代数だったけど基底や固有値・固有ベクトルの存在などのありがたさがわかってくると興奮した。
kagglのメルカリコンペにこっそり参加した。

1月

「スパース性に基づく機械学習」という本を帰省している間に読もうと思ったが見事に数式の部分で躓いたので「プログラミングのための確率統計」を読むことにした。読んでいくと「深層学習」の本で載っていた白色化の式の意味とかがわかってやっぱ基礎がガバガバと再認識した。

自然言語処理について触ろうと思ってWORD2VECなどの論文を読んだいたら、ユークリッド空間やリーマン勾配、測地線とか謎の単語が出て来て！？となった。なんで言語処理なのにこんなものが出てくるんだ・・・多様体って何だ・・・・
論文でボコボコにされたが単語の類似性などを保ったまま実数値のベクトルに変換？するには幾何学の考えが必要なんだなと思った。
それまで機械学習の勉強って線形代数や確率統計、最適化数学とかをやっとけばいいのかな〜とかのんきに考えていたが、他の数学の分野を知っておくと考えをこういった手法のアプローチが提案できるのかと感動した。というか幾何学にものすごい興味を持った。

幾何学の勉強は位相空間論、多様体論、双曲幾何とたくさんあるし一つ学ぶのにすごい時間がかかるそうだ。
そのおかげか世界が広くなったように感じてまだまだ薄っぺらいままで全然成長できてないんだと実感した。
学ぶべきこと、やりたいことは沢山あるし自由な時間は4月から少なくなっていくけど、自分がどうなりたいかを考えてやっていきたい

2018-02-06

自然言語処理に触れてみる(メルカリのデータセットでカテゴリ分類)

機械学習

よく聞く自然言語処理をやっとこさ触ってみることにした。

自然言語処理自体については図書館で借りた戦略的データサイエンスという本がちょっとだけ触れていてくれたのでこれを元に触ってみることにする
www.oreilly.co.jp

今までSVMでも決定木でも学習に必要な特徴量は大体離散値か実数値で、文字列を特徴量として渡したことがない。画像も数値の集まりで表現したし、正解ラベルも分類ならdogは1、catは2とか離散値かone-hot表現に直した

よくあるニュースの説明文からカテゴリ分類をするといったものも、説明文を数値、特徴ベクトルに変換して学習している。

その変換アプローチとして簡単かつ低コストなのがbag-of-word(BoW)と呼ばれるもの。これは全てのドキュメントを独立した単語の集まりと見なす(文法、単語の順序、文構造、句読点とかは無視する)
このアプローチではドキュメントに含まれる単語は全てドキュメントにとって重要なキーワード(特徴)になり得るとみる

あるドキュメントにおける特徴値はどんなものになるかというと全ての単語をトークンとして扱って、あるドキュメントにそのトークンが含まれているかどうかをベクトルで表現する。

用語の出現するか否かの区別に加えて、用語が使用された回数でさらに区別をしようということで用語の出現頻度を数える。ドキュメント内に存在する用語の重要性が出現回数に応じて高くなるときとかの重み付けに有効らしい。用語出現頻度(Term Frequency,TF)と呼ばれる

長いドキュメントの方が多くの単語を持っているから用語出現頻度の値は長いドキュメントの方が大きいはず。でも長いドキュメントだからといって短いドキュメントよりある用語が重要な意味を持つとは限らない。

そのため、用語出現頻度がドキュメントの長さに依存しないようにドキュメント内の総単語数で用語の出現回数を割るといった正規化を施すこともあるらしい。

自前で雑に実装したもの

import collections
import re

def TF(desc,terms,norm=False):
    tf_dict = {}
    d = desc.lower()
    for term in terms:
        i = 0
        for m in re.finditer(term,d):
            i += 1
        if i > 0 and norm==False:
            tf_dict[term] = i
        elif i > 0 and norm==True:
            tf_dict[term] = i/len(set(d.split(' ')))
    return tf_dict

正規化の方はsetでドキュメントの長さを取ってしまったけど重複ありならいらなかったかもしれない・・・

頻度のリストを作る際に、まず用語に以下のような処理を施してあげるのが基本

大文字と小文字の正規化 単語は全て小文字に変換する。これはJsonとJSONといった単語を同じ用語と見なすため
ステミング
英単語において動詞announceはannounces、announced、announcingと変化する。これらはannouc + 接頭辞に分解できるため、接頭辞を削除してannoucという用語として扱うといったことをする。名詞も複数形は単数形に直してあげる
ストップワードの除去
ストップワードとは英語において出現回数の多い一般的な単語のことを指す。これらは自然言語処理の対象外になる単語だそうだ。theとかamとかandとかそこらへん。最近でたItとかいうホラー映画のタイトルみたいにストップワードが重要な意味を持つこともあるから対象によって除去は変わってきそうだ

この前処理はgensimという便利なライブラリのgensim.parsing.preprocess_stringというメソッドを使うことで上記の処理を一気にすることができる

pre_itemname = []
# gensim.parsing.preprocess_string(文字列)は以下の関数を実行した結果を返してくれる
# strip_tags() : <a>hoge</hoge>といったhtmlのタグを消してくれる
# strip_punctuation() : ,や!といった記号を消してくれる
# strip_multiple_whitespaces() : \rや\nといった空白文字を消してくれる
# strip_numeric() : 文字列の中にある数字を消してくれる
# remove_stopwords() : am や but　といったストップワードと呼ばれる単語を削除してくれる
# strip_short() : 一定の長さを持たない単語を削除する(デフォルトでは３)
# stem_text() : ステミング(useやuseful,usingなら -> us)を行ってくれる
for i in itemname:
    pre_itemname.append(gensim.parsing.preprocess_string(i))

データとしてkaggleのコンペにメルカリの価格予測のデータを使うことにする。規約見た限り大丈夫なはず。
f:id:Owatank:20180204161831p:plain

処理の結果としては以下のようになった
f:id:Owatank:20180206112721p:plain
どことなく重要な単語が消えてるようなそうでないような・・・まあいいや

自分で実装したTFを適用してみる。結果はこうなった
f:id:Owatank:20180206113305p:plain
商品のタイトルだから単一ドキュメントに重複する単語が登場するのは滅多にないかな

単一のドキュメント内での用語の出現頻度を測定することとは別に解析対象のコーパス(ドキュメントの集まり)において、ある用語がどれだけ一般的かといったものも測定する必要がある。

例えば、ある用語が出現するドキュメントの数が少ないほど、その用語は重要かもしれない。ある用語tに関する希少性は逆文書頻度(IDF)と呼ばれる式で計算できる

$IDF(t) = 1+log_{2}\frac{総ドキュメント数}{用語tを含むドキュメント数}$

logの中身から、分母(用語tを含むドキュメント数)が小さいほど、IDFの値は大きくなることがわかる

まずこれを計算するにはコーパスからある用語がいくつ出現しているかを調べなくてはいけない

def get_terms_dict(doc):    
    d = collections.defaultdict(int)
    for i in doc:
        # 重複はカウントしない
        terms = set(i)
        for term in terms:
            d[term] += 1
    return d

コーパスでの用語出現頻度のリストを作ってIDFを計算する

def IDF(terms_dict,term,doc_num):
    return (1+np.log2(doc_num/terms_dict[term]))

f:id:Owatank:20180206114931p:plain

TFとIDFを組み合わせたTFIDFと呼ばれるテキストの表現方法(重み付けとも)が有名らしい

$TFIDF(t,d) = TF(t,d)\ast IDF(t)$

tは用語、dは単一ドキュメントを指す。数式から、TFIDFは単一ドキュメントに対する値であることがわかる。
自分で実装したもの

def TFIDF(tf,idf):
    tfidf_dict = {}
    tf_list = list(tf.items())
    for t in tf_list:
        tmp_dict = {}
        for k,v in t[1].items():
            tmp_dict[k] = v*idf[k]
        tfidf_dict[t[0]] = tmp_dict
    return tfidf_dict

f:id:Owatank:20180206120226p:plain
TFの値を正規化していないからか、基本的に1や2とかの値が多いため、IDF値のまんまな物が多い・・・

こうすることで用語が登場しているかどうかの0と1の特徴ベクトルではなく重み付けを行ったもので学習データとして使うことができる
　　　　-＝　∧＿∧
　　-＝≡　（　´∀｀）
　　　　-＝（　つ┯つ
　　 -＝≡/　 / //
　 -＝≡（_＿）/ ）
　　 -＝ (◎)￣））

gensimのライブラリを使ってさっきのTFIDFの値が合っているか、その後学習データでカテゴリの分類をしてみる

まずコーパス内での用語出現回数リストは次のように作成する

itemname_corpora_dict = gensim.corpora.Dictionary(pre_itemname)

TFIDF値を計算するには先にドキュメント(前処理済み)をBoWに変換してから行う

bow_dict = {}
for i in range(0,len(pre_itemname)):
    bow_dict[i] = itemname_corpora_dict.doc2bow(pre_itemname[i])

tfidf_model = gensim.models.TfidfModel(bow_dict.values(),normalize=False)
tfidf_corpus = tfidf_model[bow_dict.values()]

自分で作ったTFIDFのものと結果を比較する。適当に2個持ってきた結果
f:id:Owatank:20180206122854p:plain

なんかgensimの方はIDFの計算において１が加算されていないっぽい？そんなことしたらlogの中身が１のとき0の値になるけどいいんだろうか
多分計算式としてはそれ以外は合ってるかな

この重み付けされたBoWのベクトル(商品の名前)で、カテゴリ分類をしてみる。

コーパス内にある用語の数(次元数)が19797と多いので次の考え方を考慮して絞り込みをする

用語はレアすぎてはいけないということ
解析対象のコーパスのどっかのドキュメント内に滅多に使われない単語が登場しているとする。この用語が重要かどうかは利用次第で重要度は変わってくる。クラスタリングのためならあまり使われない単語は分類の基準にはなれず重要度は低くなる。なので、ある用語が出現するドキュメントの数に下限を設定して、その加減を超えたものを用語として扱うといった制限を付ける。
用語は一般的すぎてもいけないということ
ストップワードのようにコーパスにある全てのドキュメントに出現するような用語は分類、クラスタリングといった点では区別に使えない。上とは反対にある用語が出現するドキュメントの数(または割合)に任意の上限を設けて、過度に出現する用語を取り除く

# レアすぎる単語、一般的すぎる単語の除去
item_corpora_dict.filter_extremes(no_below=3,no_above=0.5)

実行した結果、コーパス内にある用語の数は7174となった。~~それでもまだ多い気がする~~
これは一種の次元削減として見てもいいのかな

次にTFIDFを正規化ありで実行し、重み付けされた特徴ベクトルを得る

tfidf_model = gensim.models.TfidfModel(bow_dict.values(),normalize=True)
tfidf_corpus = tfidf_model[bow_dict.values()]

feature_vec = gensim.matutils.corpus2dense(list(tfidf_corpus), num_terms=len(itemname_corpora_dict))
feature_vec = feature_vec.T

分類のための学習を行う

# TFIDFで重み付けしたもので分類
from sklearn.grid_search import GridSearchCV
from sklearn.cross_validation import StratifiedKFold
from sklearn.linear_model import SGDClassifier
clf = GridSearchCV(SGDClassifier(penalty="l2"), param_grid={'alpha':[0.01,0.05,0.001,0.0001]})

# StratifiedKFold(y, n_folds, shuffle=True) 交差検証用にデータを分割してくれる
for i, (itr, ite) in enumerate(StratifiedKFold(y_test,n_folds=5, shuffle=True)):
    clf.fit(X_train[itr], y_train[itr])
    train_pred = clf.predict(X_train[ite])
    train_acc = metrics.accuracy_score(train_pred,y_train[ite])
    print("{0} finished. test accuracy : {1}".format(i+1,train_acc))

今回はGridSearchCVとStratifiedKFoldというメソッドを使ってみた。前者は最適なパラメータを探してくれて、後者は交差検証のためのメソッドらしい

f:id:Owatank:20180206143448p:plain

最終的なテストデータでのAccuracyは0.78095だった。

同様のことを重み付けしていないただのBoWでのベクトルで行なったが、こっちでのテストデータのAccuracyは0.7827だった。
重み付けしていない方が誤差レベルだけど値が大きいことからここでの問題に対して用語の重み付けはそんなに意味を成さなかったのかな(((((;｀Д´)≡⊃)｀Д）､;'.･

今回やったもののコードはここ

github.com

2018-01-28

PythonとGo言語でSlackからTogglとスプレッドシートを操作するbotを作った

機械学習に全然関係ないです

togglという時間を計測したり分析してくれるサービスがありますね
最近勉強時間を測って振り返ってみようと思い使っているが、スマホやブラウザから操作すると大抵タイマーをストップするのを忘れて作業時間が43時間になったりすることがよくある

正直タイマーのスタートやストップのために一々スマホアプリやwebブラウザを開くのは面倒で困る。
という訳でいつもよく見るslackやtwitterから操作すれば面倒に感じないのでは？と思い勉強の息抜きも兼ねてtogglのタイマーを操作してくれるslackbotを作ることにした。すでにそういうものがある？まあ・・・うん・・・・

最初はpythonで作ったけど後からgo言語でも作った
以下を参考にした

Real Time Messaging APIで秘書botを作ってみる - adish intelligence
golang で始める Slack bot 開発 - at kaneshin
GitHub - toggl/toggl_api_docs: Documentation for the Toggl API

やっていることは、特定のキーワードに反応して対応する操作を行い、メッセージを返すといったもの
例えばstartと入力すればtogglのタイマーをスタートする、add desc hogeと打てばそのtogglのタイムエントリーにhogeという説明文を追加するとか
個人のtogglのAPI トークンを使って操作するので同チャンネル内の他の人からは操作できないように、メッセージの送信者のメールアドレスを確認して特定のユーザーなら操作を行うといったものにしておいた

f:id:Owatank:20180128143706p:plain f:id:Owatank:20180128143316p:plain

それとは別に計測した時間をgoogle スプレッドシートに書き込んでくれる機能も盛り込んだ
用意しておいたスプレッドシートから対応する日付の行を持ってきていい感じに出力してシートを更新したりする

f:id:Owatank:20180128144313p:plain

コードはここ(追記: Goの方パターン諸々綺麗に直しといた)
Go言語のほう
 Pythonのほう

開発は全然したことないから関数名、パターンだったり例外処理だったりと雑なのだ
Pythonをここ最近触っていたせいか初めてgoを触ったせいなのか色々とギャップがひどかった。Pythonのが色々とゴリ押しで書けるところがあるからか...

2018-01-23

期待値と分散(離散値の場合)について

確率統計

青いイルカの深層学習の本やスパース性に基づく機械学習の本でも、損失関数の説明あたりで平均期待二乗誤差といった誤差の期待値を最小化する式が出てくる

なんとなく雰囲気で読んでいて、いつも期待値が得体の知れないもののように感じて詰まってしまっていた。
適当に調べると期待値はある関数f(x)の確率分布p(x)の下での平均値をf(x)の期待値と呼ぶとか書かれていた。
参考(12-3. 確率変数の期待値 | 統計学の時間 | 統計WEB)

悩むのは確率分布p(x)の下での平均値というところ。確率ってP(X=a)というのは何%でX=aが起きるかを示しているものだからそれ自体が平均っぽいものじゃないのか？と考えていた。

スパース性に基づく機械学習でも期待値で詰まっているところがあるし、悩みっぱなしは良くないと思い、「プログラミングのための確率統計」という本を読むことにした

読み進めて期待値について自分なりにイメージを掴んだのでメモメモ

機械学習において nクラス分類というのは、データの特徴という入力を渡し結果として分類の結果(nクラスのうちの一つ)を受けとるといったものを考える。ソフトマックス関数でいえば最も確率が高いもののクラスを選ぶ

これは $X$ を入力、 $Y$ を結果としたら $Y = f(X)$ みたいに数式で表せるはず

でも現実にはノイズの混入を避けることができずXの測定値が同じでも、得られるYの測定値は異なるということが起こってしまう。 $Y = f(X) + b$ な感じかな？

$Y = f(X)$ 、つまりX=aなら必ずY=bが出るよみたいに確定して言えないならせめてX=aのときは何%くらいでY=bが出るとは言えないだろうか？

こういった表現は条件付き確率 $P(Y=b|X=a)$ で表すことができる

ところで新年明けましたね。くじ引きをしたのではないでしょうか。ということで次のようなくじ引きをする

100円、500円、1000円のいずれかを払うと1回引けるくじがある。それぞれのくじの内容は

100円くじ : 80%で50円、15%で100円、5%で300円もらえる
500円くじ : 60%で250円、25%で500円、15%で1500円もらえる
1000円くじ : 35%で500円、45%で1000円、20%で3000円もらえる

500円くじに挑戦したときいくらぐらいもらえるだろうか
これは条件付き確率 $P(Y=もらえる金額|X=500円くじを引く)$ となる

確率ではもちろん「60%で250円、25%で500円、15%で1500円もらえる」と言うことができるがそうじゃない。そういった揺らぐ値ではなく揺らがない具体的な値としての答えが欲しい。例えばこのくじ引けば大体5000兆円儲かるよみたいな
そんな役割を果たす具体的な値のことを期待値と呼ぶそうだ

確率分布p(x)は揺らぐからこそ平均としてこんな値が出る、といった一目でわかる値が欲しいんだな
ちなみに期待値は平均みたいにn個の値を合計してnで割るということはしていないので平均値と期待値は違うもの、でいいのかな

次に期待値と呼ぶのはいいけどどうやってその値を求めるか
確率は起こりうる事象を全て足した結果は１にならないといけない

例えば全ての出る目の確率が等しい6面サイコロだったら
(１がでる確率)+(２が出る確率)+...+(６がでる確率) = 1

ここで
$P(Y=250|X=500) + P(Y=500,X=500) + P(Y=1500,X=500) = 1$
としよう

どのくじを引くかは任意で、くじの種類によってもらえる金額は変わってくるけどくじの内容の確率が変化するということはないので独立とする

図で表すとこう
f:id:Owatank:20180123105522p:plain

面積１の正方形の中に確率の値を面積とした領域がある感じ

同時確率は
$P(Y,X) = P(Y|X)P(X)$

独立なときは $P(Y,X) = P(Y)P(X)$ としていいので $P(X)=1$ とすると、結局は $Y$ がいくらでるかの確率(周辺確率)で考えることになる

次に上の画像の各領域において、いくらもらえるかの値段を高さで表現する
f:id:Owatank:20180123105959p:plain

デコボコしている。このデコボコを均一にして綺麗な直方体のようにしたとき、面積はYがとりうる全ての確率P(Y)になるから、その時の高さが $Y$ がいくらでるかの平均にならないだろうか。

f:id:Owatank:20180123112414p:plain

その高さはどう計算するかというとこの体積を雪だと思えば雪が少ないとこに分けてあげて均一にするだけ、それはそれぞれの体積を足した結果と変わらないはず
体積自体を増やしたり減らしたりすることはしてない

つまり

$E [Y ] = 250\ast P(Y=250,X=500) + 500\ast P(Y=500,X=500) + 1500\ast P(Y=1500,X=500)$

こうすれば期待値(体積)を求められる。ちなみにYの期待値を $E [Y ]$ で表した。結果は
$E [Y ] = 250\ast 0.6 + 500\ast 0.25 + 1500\ast 0.15 = 500$

平均として500円もらえるっぽい
「0.6%で250円、0.25%で500円,0.15%で1500円もらえるよ」よりも「期待値として500円貰えるから損はしないよ」と言われる方が参加する人は増えるかな

「期待値として500円貰えるから損はしないよ」と言われてやってみよっかな〜〜〜、って思ったときあくまで期待値だし、期待値が出たら損をしないだけ。
$Y$ がいくらでるかは揺らぐ値だから期待値が必ずでるとは限らない。そこで期待値ではない値 $y$ が出た時、それが期待値からどれくらい離れているか計算して、外れた時のリスクはどれくらいかといったものを調べてから挑戦したい気持ちもある

かなり離れていたら損をしたときのショックはでかいし、離れていなければダメージはそこそこ少ないし・・・まあいいか・・とか対策を練ってから挑みたい

この距離は期待値を $\mu$ 、くじを引いた時の実際の金額を $y$ とすれば距離は $| \ y - \mu \ |$ でいいはずなんだけど、絶対値をだと場合分けしないといけなかったり微分できない点があったり不便らしい。そのため $( \ y - \mu \ )^{2}$ といった2乗の形、自乗誤差と呼ばれるものを使う

二乗しているため期待値 $\mu$ から離れるほど値は大きくなるのが特徴
$y$ は必ずこういった値が出る、というものではなく揺らぐ値なので $( \ y - \mu \ )^{2}$ も揺らぐ値になってしまう。ダメじゃん

この期待値からの外れ具合を表す値の揺らがない値、つまり外れ具合を表す値の期待値が欲しいので

$V[Y] = E [( \ y - \mu \ )^{2}]$

を計算すれば外れ具合を表す値の期待値が得られる。
そしてこの $V[Y]$ のことを分散と呼ぶ。分布の散り具合・・かっこいい・・・
分散は値が大きければ散らばっている、値が小さければ散らばり具合が少ないといったことを示してくれる

さっそく計算して求める
$V[Y] = (250-500)\ast (250-500)+(500-500)\ast (500-500)+(1500-500)\ast (1500-500) = 1062500$

うーん・・・値が大きいってことは散らばっているということだけど、どれくらい散らばっているのかわからない・・・

距離がそもそも $( \ y - \mu \ )$ 、単位として $m$ だとしたら、二乗しているということは分散は $m^{2}$ 、長さの二乗を表していることになる。単位が違うから比較が難しい。
なら平方根を取れば $m$ に直せるじゃん。取ってみよう

$\sqrt{V [ Y ] } = \sqrt{1062500} = 1030.7764064$

分散の平方根を取ったものを標準偏差と呼ぶ。期待値は $\mu = 500$ だから悪くはないのかな?

最後に500円くじを500回試行したときの１回ごとの累積和をプロットしてみた
ソースはここ
github.com

横軸は試行回数、縦軸はその時の所持金額とする。
まず500回試行して250円、500円、1500円がどれくらい出たかというと

f:id:Owatank:20180123120519p:plain

だいたい事前に設定した「60%で250円、25%で500円、15%で1500円もらえる」に従っているので良しとする。

３人がくじに挑戦したとしてそれぞれの累積の結果は

f:id:Owatank:20180123120651p:plain

f:id:Owatank:20180123120711p:plain

f:id:Owatank:20180123120726p:plain

赤の線が期待値を表し、赤の点線が期待値±標準偏差を表す。この点線内に点が集中していないことから分布がひどく散らばっているのがわかる。
最初の人はかなり勝っているのに対し、三番目の人はかなりボロ負けしている。
二番目の結果を見る限り、最初は負け続けていても途中から利益が出ているのを見ると、負け続けても諦めなければ勝てるといった気持ちも大切なのかなとか思う。ギャンブル試行だ・・・

大事なことは期待値、分散、標準偏差は揺らがない値で確率分布における目安のような役割を果たす値ということ。

参考文献(Kindle版もあるよ)

プログラミングのための確率統計
 プログラミングのための確率統計
 プログラミングのための確率統計

2017-12-28

スパース性に基づく機械学習のわからないとこのメモ

機械学習助けて

タイトル通りL1ノルムとか正則化あたりを理解しようと思ったので「スパース性に基づく機械学習」という本を読んでる
わからない~~というより日本語が理解できない~~ところがいくつかあったのでメモとして残して、理解できた部分はここでまとめることにする。
わからないとこは箇条書きする

未解決のとこでわかる人いれば助けてほしい・・・・・・・

第1章

スパース性というのは「まばら」を意味する単語
この本だとn次元のベクトル $\vec{x}$ が非ゼロの成分がごく一部しかなくて、それ以外の成分が０なものとかを指す
$\vec{x} = (1,1,1,0,0,...,0)^{T}$
こんな感じ

スパース性の考えが機械学習にどう役立つか？というのを「ひよこのオスとメスの分類」で考える
ひよこのオスとメスを仕分けするバイトがあるとして、どう仕分けするか。クチバシとか足とか全身をくまなく調べて仕分けする方法を取った時、全身を見るのでかなり時間がかからないだろうか。
実際に仕事としてやっている人たちはどうやら肛門や羽といった一部分のみを調べて仕分けしているそう。
これは全身、「すべての特徴」を見るのではなく「ある一部分の特徴」にのみに注目するだけで仕分けができるということを意味している。スパース性の考えとしては一部分(非ゼロ)ということになる。

また「すべての特徴」がひよこのオスとメスの分類に関係あるとしたら沢山のひよこの「すべての特徴」をくまなく調べないといけないが、「ある一部分の特徴」のみが関係あるとしたら、少数のひよこからその関係を調べるだけで済む。

こんな感じでスパース性は「計算量」の節約の他に「統計に必要なサンプル数」といった統計的な問題を良い方向に持っていってくれることができる。

ここで「ある一部分の特徴」のみが関係しているはずと仮定を立てたとして、「ある一部分の特徴」がどこなのかはわかっていない状況なのでその特徴は自分たちで探さないといけないというのも重要

ページ2の「スパース性の拡張のもう一つの例として行列の低ランク性が~」の部分 --- 解決
d行T列の行列を推定する問題で行列のランクが $r$ であるということは、T個の学習課題に共通する $r$ 個の要因が存在することを意味する

省略したけど大体ここら辺が理解できなかった

まず特異値というのは、これは行列Aを相似変換して対角行列の形にしたとき、その対角成分が非ゼロな値のものを特異値と呼ぶっぽい
そして相似変換された元の行列Aのランクはこの特異値の数と一致する性質があるとのこと。

$$ A = \begin{pmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \\ a_7 & a_8 & a_9 \end{pmatrix} $$

行列Aが(3,3)行列だったとして、第３列目が第１列目の3倍、つまり $a_7 = 3a_1, a_8 = 3a_2, a_9 = 3a_3$ といった関係だったとしたら、3次元のうち一つの次元は残りの次元で表現できるということを意味する。
基底でいえば線型独立ではないって言えるということかな
スパース性でいえば、3次元の「すべての特徴」を見る必要はなくなったといえる

~~ここミスってる気がするから修正する~~

第2章

ページ4の「例示することが容易でも、ルールとして言い表すことが難しい事柄が多数存在する」 --- 疑問

MNISTみたいな手書き数字の分類で言えば、例示で「手書き数字の０と９の区別」を説明するのは簡単だけど、ルールで説明するには「基準としての手書き数字０と９」を定義しなければ説明できないが、基準を定義するにはほぼ無限にあるサンプルが必要であり困難ということであってる?

ページ5,6の相対エントロピーやロジスティック損失の導出 --- 未解決

イルカの方の深層学習で導出したような気がするのでそっちを復習してまとめるはず

この本では予測や分類を「入力ベクトル $\boldsymbol{x}$ が与えられたもとで、どの程度よくラベル $y$ を予測(分類)できるか」という観点で評価する。データから学習して、分類などを行いたいデータの背後にある未知の確率分布 $P(\boldsymbol{x},y)$ に関する期待値を求める

でもこの期待値は未知の確率分布 $P(\boldsymbol{x},y)$ に関する期待値だから直接評価はできないため、訓練データから $P(\boldsymbol{x},y)$ をある程度近似するということ。

統計学の授業で「日本人の20歳の平均身長」を求めたいとき全ての20歳の日本人のデータを集めるのはほぼ無理というか難しいから、例えばいくつかの大学に協力してもらったりして有限の人数、いくつかの20歳の日本人のデータを集めて「日本人の20歳の平均身長」を近似するという話に似ている気がする

そのため訓練データから期待誤差を近似したもの、最小化をすることを経験誤差と経験誤差最小化と呼ぶ
深層学習でよく定義する訓練誤差とかはこっちを指してるんだな

深層学習の本で入力と重み $\boldsymbol{w}$ とバイアス $b$ を用いた $f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w} + b$ といった曲線の式をよく見る。この曲線に従ってラベル $y$ を予測したりヌンヌン...
誤差を最小にするというのは訓練データでいえば $f(\boldsymbol{x}) = \boldsymbol{x}^{T} \boldsymbol{w} + b$ という曲線による予測が訓練データがもつ答え $y$ と大体一致して欲しいということ

f:id:Owatank:20171228125452j:plain

曲線の形をグニャグニャ変えていけばいつかは大体一致する曲線になっていくはず。 $\boldsymbol{w}$ と $b$ の値を変えていくと形は変わるので、最小化するとは最適な $\hat{ \boldsymbol{w}}$ と $\hat{b}$ を見つけること。

f:id:Owatank:20171228132907p:plain

最小化を達成するための $(\hat{ \boldsymbol{w}},\hat{b})$ を推定量と呼び、ハットをつけて区別するらしい

ページ7のこの最適化問題は~... --- 疑問

ある行列
$\boldsymbol{X} = ( \boldsymbol{x_1}, ... , \boldsymbol{x_n} )$
のランクが $d+1$ 以上であれば、一意に解 $(\hat{ \boldsymbol{w}},\hat{b})$ が定まる

ここが「？」となった。伝えたいことはランクが $d+1$ 以上ということは解決したいことがらは $d+1$ 次元で表現できるということ。3次元なら2次元で表現することは難しいから論外(というか自己符号化器の話になる？)として、 $d+1$ 以上なら次元が多くても、求めたい $(\hat{ \boldsymbol{w}},\hat{b})$ は定まるということかな。

訓練誤差が小さい値になったからといって近似したい期待誤差が小さいとは限らないことがある。こういう状況は取ってきた一部、訓練データにかなり適合してしまっているとかが考えられる。適合しすぎて期待誤差が大きくなってしまう現象を過剰適合、オーバーフィッティングと呼ぶ。過適合ってやつだ
訓練誤差が小さくなって、期待誤差もそこそこ小さくなることを汎化するという。よく汎化性能って単語見ますね

過適合を防ぎ、汎化性能を上げるにはモデルを制約し、誤差への当てはまりを抑えることが大事になってくる。モデルを制約する方法としては

多項式などの独立な基底関数の和として関数 $f$ を表現し、その基底関数の数を小さく抑える
関数 $f$ の何らかのノルムを抑える

む、難しい単語で書かれてる・・・・。今までの知識を振り絞って考えると１つ目は要するに「次元数を抑えろ」ということだと思う。基底関数でエッッと混乱したけど、曲線を表す多項式は行列で表すとき、極端な話単位ベクトルで構成される基底で分解して表現できるはず。基底関数の数を小さく抑えるというのはこの基底の要素である基底ベクトルの本数を減らすということ。基底ベクトルの本数が減るんだから次元数も当然減る。

近似したい曲線が３次式のする。この曲線を3次式以上で表現しようと考えると、できないことはないが近似したい曲線と形は離れていくかもしれない。それは汎化性能が落ちてしまうことになる。

２つ目は次元数を固定したときの係数(推定量) $\boldsymbol{w}$ のとり方の制限かな。実数範囲から係数の値を選べるとしてある次数の係数はめっちゃ大きくとって別の係数は小さくとって・・・とバラ付きすぎるのは問題。実数のある値より大きい値は取らないみたいな制約を決めて $\hat{ \boldsymbol{w}}$ を選ぶ方法をとるということ。

ページ12~14の平均期待二乗誤差 --- 未解決

ここ完全に頭追いつかなかった。
まず推定量 $\boldsymbol{w}$ の期待二乗誤差の訓練データに関する期待値を
$\bar{L}(\boldsymbol{w}) = E_T E_{\boldsymbol{x},y} (y-\hat{\boldsymbol{w}}^{T}\boldsymbol{\phi}(x))^{2})$ と定義する

また次数pのとき $\boldsymbol{\phi} = (1,x^{1}, ... , x^{p})^{T} , \boldsymbol{w} = (w_0,w_1, ... ,w_p)^{T}$

このとき平均期待二乗誤差は
f:id:Owatank:20180101161043p:plain

(二乗が抜けていたので赤で修正)この導出が全然わからん・・・。第一行目でおそらく二乗の中身を \[ (( \hat{\boldsymbol{w}}^{T} + \bar{\boldsymbol{w}}^{T} - \bar{\boldsymbol{w}}^{T} + {\boldsymbol{w}^{\ast}}^{T} - {\boldsymbol{w}^{\ast}}^{T} )\boldsymbol{\phi}(x) - y )^{2} \]
こんな感じにして変換しているとは思うけど第二行目の変換で悩んでしまった。

※追記( 12/29 )

$E_{T_r}$ は推定量 $\hat{\boldsymbol{w}}$ を見つけるために使った訓練データ(標本)からの期待値

$\bar{\boldsymbol{w}}$ は推定量 $\hat{\boldsymbol{w}}$ の訓練データに関する期待値らしく $\bar{\boldsymbol{w}} = E_{T_r}\hat{\boldsymbol{w}}$ と定義している

最適性条件というのは
\[ E [ \boldsymbol{\phi}(x)(\boldsymbol{w}^{\ast} \boldsymbol{\phi}(x) - y) ] = 0 \]

$\boldsymbol{w}^{\ast}$ は全てに当てはまる理想のパラメータだから、 $(\boldsymbol{w}^{\ast} \boldsymbol{\phi}(x) - y)$ のところが０にならないといけないということなはず

平均二乗誤差に存在する ${\sum}_x$ は計量行列と呼び以下のように定義される

\[ {\sum}_x = E [ \boldsymbol{\phi}(x) \boldsymbol{\phi}^{T}(x)] \]

この計量に基づく距離を

\[ || \boldsymbol{w} - \boldsymbol{w}^{\prime}||_{\sum{x}} = \sqrt{ (\boldsymbol{w} - \boldsymbol{w}^{\prime})^{T} {\sum{x}} (\boldsymbol{w} - \boldsymbol{w}^{\prime})} \]

と定義しているそうだ

ちなみに最後の行の第一項は期待値 $\bar{\boldsymbol{w}}$ のまわりでの推定量 $\hat{\boldsymbol{w}}$ の揺らぎを定量化する項、ばらけ具合ということで分散になって、第二項は期待二乗誤差 $L(\boldsymbol{w})$ を最小化するパラメータ $\boldsymbol{w}^{\ast}$ と推定量の期待値 $\bar{\boldsymbol{w}}$ の距離の２乗でありバイアス(近似誤差)を定量化する項になる
近似して求めたいのは期待二乗誤差を最小化する理想のパラメータ $\boldsymbol{w}^{\ast}$ であり $\bar{\boldsymbol{w}}=\boldsymbol{w}^{\ast}$ になれば推定量 $\hat{\boldsymbol{w}}$ は不偏推定量(訓練データ(標本)から求めた期待値が母集団の期待値と一致)になるのはわかる。

最適性条件などを使って平均期待二乗誤差を導出しているらしい。まとめておく

ページ18の制約付き最小化問題と罰則項付き最小化問題の等価性 --- 未解決

ヤバイ

文がわからなかっただけなので後回しかも

※追記(1/1)
ラグランジュの未定乗数法のことという神の声を頂いた

第3章

$\boldsymbol{y}= \boldsymbol{x}^{T} \boldsymbol{w}$ を満たすようなパラメータ(ベクトル) $\boldsymbol{w}$ を決めるとき、ベクトルの非ゼロ要素は少ない方がいい。

例として電車を考える。目的地まで電車で移動したいとき、同じ料金、同じ時間で到着するなら乗り換え( $\boldsymbol{w}$ の非ゼロ要素として見る)は少ない方が嬉しくないだろうか。自分は乗り換えが苦手なので少ない方が助かる。

なので推定量 $\hat{\boldsymbol{w}}$ を見つけるときの条件として新たに非ゼロ要素は k個以下という制約を加えてあげればより良い $\hat{\boldsymbol{w}}$ を見つけることができると書いてあった。すごい。

しかし残念ながらこのような制約を加えた最適化問題の計算は現実的に困難であるそうだ。ええ・・・。
理由としては $\boldsymbol{y}= \boldsymbol{x}^{T} \boldsymbol{w}$ を満たすような $\boldsymbol{w}$ の組をしらみ潰しというかブルートフォース？とも言えるのだろうか、調べなくてはいけないから。次元数が増えれば増えるほど調べないといけない組の数は多くなってしまう。

困ってしまった。そこでL1ノルム正則化と呼ばれる手法が役に立つ。
ベクトル $\boldsymbol{w}$ のL1ノルムはベクトルの要素ごとの絶対値の線形和として

${\| \boldsymbol{w} \|} (l_1) = \sum_{j=0}^d | w_i |$

で表される。
ベクトル $\boldsymbol{w}$ の非ゼロ要素の数が多いほど、L1ノルムの値も大きくなる。非ゼロの数が１、２、と増えていくのとは別でL1ノルムの値は要素の値によって比例して大きくなることに注意。

このL1ノルムと呼ばれるものを使って非ゼロ要素が少なくて、求めたい要件を満たすような $\boldsymbol{w}$ を見つける。最適化問題としては

$minimize(\boldsymbol{w}) \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, ( \,\, {\| \boldsymbol{w} \|} (l_1) \leq C \,\,)$

あるいは

$minimize(\boldsymbol{w}) \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, + \lambda \| \boldsymbol{w} \| (l_1)$

と表される。また条件として $C > 0 , \lambda > 0$

L1ノルムは $y = x^{2}$ みたいな形をしているから任意の d次元ベクトル $\boldsymbol{w}$ のL1ノルムは凸関数になる

f:id:Owatank:20180102143841p:plain

なので最適化問題

$minimize(\boldsymbol{w}) \,\, \,\, \hat{L}(\boldsymbol{w}) \,\, + \lambda \| \boldsymbol{w} \| (l_1)$

$\hat{L}(\boldsymbol{w})$ が凸関数なら、凸最適化問題になると書いてあった。凸関数同士を合わせたものが凸関数になるという証明がなかったけど自明なのかな？

1次元ベクトル $\boldsymbol{w}$ のL1ノルムは

n = 100
x = np.linspace(-1, 1, n)

f = np.abs(x)
plt.plot(x,f,"r-")
plt.show()

f:id:Owatank:20180102153358p:plain

こんな感じの直線で引けるけど、本に書いてあるL1ノルムの図形はひし形みたいなグラフになっている。ﾅﾝﾃﾞﾀﾞﾖヾ(｀Д´)ﾉ
よく読んだらひし形はL1ノルムの等高線を表していると書いてあった。
等高線は小学校のときに地形の等高線しか引いた記憶しかないけど、ここでは d次元ベクトル $\boldsymbol{w}$ のL1ノルムの値を高さとしたグラフが等高線となる。書いてみる

等高線を書くには方眼、meshgridが必要なので用意する

n = 30
x = np.linspace(-1, 1, n)
y = np.linspace(-1, 1, n)

xx,yy = np.meshgrid(x, y)

変数xxとyyが方眼、グリッド線になってくれる。

次に描写したいL1ノルムの方程式を用意する。2次元のグラフとして表示したいので2次元ベクトル $\boldsymbol{w} = (w1,w2)^{T}$ として
$f(w1,w2) = |w1| + |w2|$ のようなL1ノルムの値を高さとして持つ $f(w1,w2)$ を作る。
ここでは x軸をw1、y軸をw2として作ることにする。

meshgridで作ったxxとyyは変数を見る限りこんな感じになってるはず
f:id:Owatank:20180102161104p:plain f:id:Owatank:20180102161001p:plain f:id:Owatank:20180102160844p:plain

上の水色と緑の線は5本だけど、プログラムとしてはn = 30とn本で指定される
$f(w1,w2)$ はこの [-1,1]区間の全ての点、組の結果を計算して作る

f = np.abs(xx)+np.abs(yy)

plt.contour(xx,yy,f)
plt.xlim(-1,1)
plt.ylim(-1,1)
plt.gca()
plt.show()

f:id:Owatank:20180102164853p:plain

ひし形になってくれた。 n の値を変えるとよりひし形っぽくなるのも確認できた。
等高線っぽさを見たいので別のメソッドで出力してみると

from mpl_toolkits.mplot3d import Axes3D
fig = plt.figure(figsize=(10,6))
ax = Axes3D(fig)
ax.contourf3D(xx,yy,f)

f:id:Owatank:20180102165031p:plain

いい感じに等高線っぽくなった

このことからL2ノルムでよく見る楕円の形はあるベクトルの要素からできるL2ノルムの等高線、楕円を図示していたということかな。