ie_test

2018年12月1日土曜日

2018年8月5日日曜日

RSAについて

# 概要
RSA の復号がうまくいくことを述べておく。(よく忘れるので。)

以下とほぼ同様(なので個人メモのようなもの)

https://ww1.fukuoka-edu.ac.jp/~sakamott/RSAtop.html

## 補題 1
p, q を相異なる素数とし，x, a, b を整数とする。

このとき、 a ≡ b (mod p) かつ a ≡ b (mod q) ならば　 a ≡ b (mod pq)　が成り立つ。

### (証明)

(a - b)　は p の倍数かつ q の倍数。 p,q は素数なので (a - b ) は pq の倍数。

## 補題 2( フェルマーの小定理 )

p を素数とし、a を p と互いに素な整数とするとき、

$a^p$ ≡ a ( mod p )

が成り立つ。

### (証明)

a = 0 の時は自明

#### $ a \neq 0 $ の時

$ a^p - a = (1+m)^p - (1+m) = m^p -m + pC_1m^{(p-1)} +  pC_2m^{(p-2)} + ... $

となっており、

$ pC_im^{(p-i)} $ は p が素数なので p の倍数となる。

よって $ a^p - a = m^p - m $ mod p となる。

よって帰納法により ok 。

## RSA暗号のための命題

相異なる素数 p, q に対して L　を p-1 と q-1 の最小公倍数とする。
k ≡ 1 ( mod L )
をみたす整数 k が与えられたとき，

任意の整数 x に対して

$x^k$ ≡ x ( mod  pq )
が成り立つ。

## 証明

まず最初に $x^k$ ≡ x ( mod  p ) を示す。

### x が p と素な場合

L は (p-1) の倍数なので
$ x^k $ = $ x^{t(p-1)+1} $ と書ける。

フェルマーの小定理より

$ x^{(p-1)}  $ = 1 mod p より
  
$ x^k $ = $ x^{t(p-1)+1} $ = x mod p .

### x が p と素でない場合
$ x^p  $ = 0 mod p  より自明

同様に q に対しても
$x^k$ ≡ x ( mod  q )　が成り立つ。

よって補題1 より

$x^k$ ≡ x ( mod  pq ) が成り立つ。

2018年8月1日水曜日

tensorflow の RNN 実装について

# 目的
RNN は入力が結構複雑なので意図通りのネットワークになっているかを確認したい.

## RNN コード

以下のコードをみる。わかりやすくするために $$ W \in R^{3 \times 5}$$ の要素を全て 1,$$b \in R^5$$ を全て 0 にして実行する。
```
#coding:utf-8

import tensorflow as tf
import numpy as np

n_inputs = 3
n_neurons = 5

X0 = tf.placeholder( tf.float32, [None, n_inputs] )
X1 = tf.placeholder( tf.float32, [None, n_inputs] )

basic_cell = tf.contrib.rnn.BasicRNNCell( num_units=n_neurons )

output_seq, states = \
    tf.contrib.rnn.static_rnn( basic_cell, [X0, X1], dtype=tf.float32 )

Y0, Y1 = output_seq
init = tf.global_variables_initializer()

X0_batch = np.array( [ [0, 0.1, 0.2] ] )
X1_batch = np.array( [ [0, 0.1, 0.2] ] )

assign_ops = []
for v in tf.global_variables():
    #rnn/basic_rnn_cell/kernel:0 (8, 5)
    print(v.name,v.shape)    
    if v.name == "rnn/basic_rnn_cell/bias:0":
        assign_ops.append ( tf.assign( v, tf.zeros( v.shape, dtype=tf.float32 ) ) )
    else:
        assign_ops.append ( tf.assign( v, tf.ones( v.shape, dtype=tf.float32 ) ) )
assign_ops_exec = tf.group(*assign_ops)

with tf.Session() as sess:
    init.run()
    sess.run( assign_ops_exec )
    Y0_val, Y1_val = sess.run( [Y0,Y1], feed_dict={ X0: X0_batch, X1:X1_batch } )
    print(Y0_val) # math.tanh( 0.3 )
    print(Y1_val) # math.tanh( 5*math.tanh(0.3) + 0.3 )

```

実は以下のコードと同様のネットワークになっている。

```
#coding:utf-8

import tensorflow as tf

n_inputs = 3
n_neurons = 5

X0 = tf.placeholder( tf.float32, [None, n_inputs] )
X1 = tf.placeholder( tf.float32, [None, n_inputs] )

Wx = tf.Variable( tf.random_normal( shape=(n_inputs, n_neurons), dtype=tf.float32 ) )
Wy = tf.Variable( tf.random_normal( shape=(n_inputs, n_neurons), dtype=tf.float32 ) )
b  = tf.Variable( tf.zeros( [1, n_neurons], dtype=tf.float32 ) )

Y0 = tf.tanh( tf.matmul( X0, Wx) + b )
Y1 = tf.tanh( tf.matmul( Y0, Wy) + tf.matmul( X1, Wx ) + b )
print("ok")
```

## 確認
rnn.py を実行すると以下の出力になる。
```
[[0.2913126 0.2913126 0.2913126 0.2913126 0.2913126]]
[[0.94211787 0.94211787 0.94211787 0.94211787 0.94211787]]
```
W が Wx と Wy を合わせた形となり shape = (8,5) となっていることが確認できる。
また、 
math.tanh(0.3) = 0.2913126124515909
math.tanh( 5*math.tanh(0.3) + 0.3 ) = 0.9421178971878335
となることが確認できる。

## LSTM コード
以下は MNIST に対して無理やり LSTM やってみたコードの一部。
https://blog.scimpr.com/2018/01/26/tensorflow%E3%81%AE%E3%83%A2%E3%83%87%E3%83%AA%E3%83%B3%E3%82%B0%EF%BC%92%E3%80%9Crnn/
```
#coding:utf-8
import tensorflow as tf

x = tf.placeholder( tf.float32, [None, 784] )
x2 = tf.reshape( x, [-1, 28, 28] )
x3 = tf.transpose( x2, [1, 0, 2] )  #[28, 50, 28]のtensor
x4 = tf.reshape( x3, [-1, 28] ) #[28*50, 28]のtensor
x5_list = tf.split( x4, 28 ) # shape=(*,28) となる tensor を 28 個もつリスト.
# print( "x4: ", x4.shape )
# print( "type(x5): ", type(x5) )
# print( "type(x5[0]): ", type(x5[0]) )
# print( "x5[0]: ", x5[0].shape )

lstm_cell = tf.contrib.rnn.BasicLSTMCell( 13, forget_bias=1.0)
outputs, states = tf.contrib.rnn.static_rnn( lstm_cell, x5_list, dtype=tf.float32 )
print( "len(outputs): ", len(outputs) )
print( "outputs[0].shape: ", outputs[0].shape )
print( "len(states): ", len(states) )
print(  type(states[0]), type(states[1]) )
print(  states[0].shape, states[1].shape )
print("variable print")
for v in tf.global_variables():
    print( v.name, v.shape )

```

## LSTM 確認
以下のように shape=(input*output, 4* output ) の変数が内部で確保されている事が確認できる。
```
len(outputs):  28
outputs[0].shape:  (?, 13)
len(states):  2
<class 'tensorflow.python.framework.ops.Tensor'> <class 'tensorflow.python.framework.ops.Tensor'>
(?, 13) (?, 13)
variable print
rnn/basic_lstm_cell/kernel:0 (41, 52)
rnn/basic_lstm_cell/bias:0 (52,)
ok

```
さらにあの LSTM のめんどい式が計算されていることを確認した方が良いが、
そのためには、もう少し小さいサンプルでデータを作成した方がよい。。
(力尽きた。)

luigi の機能色々

luigi で色々行う際にちょっとハマったことなどを書いてます。

luigi の基本的な取り扱いに関しては下記を参照
https://ietoa.blogspot.com/2018/07/luigi.html

# luigi で google cloud strage(以下 gcs) を依存先に設定する方法
gcs 上のファイルを依存先として設定する方法を調査した。

## 課題設定
gcs 上の a-test バケット上の test_dir フォルダの中の tmp_test.txt ファイルを
a-test2 バケット上に tmp_test2.txt ファイルとしてコピーする。

## コード
```
import os
import luigi
import luigi.contrib.gcs

class Orig(luigi.Task):
    def output(self):
        return luigi.contrib.gcs.GCSTarget("gs://a-test/test_dir/tmp_test.txt")

class Testup(luigi.Task):
    def requires(self):
        return Orig()
        
    def run(self):
        input_path = self.input().path
        output_path = self.output().path
        os.system( "gsutil cp %s %s"%(input_path, output_path ) )
        
    def output(self):
        return luigi.contrib.gcs.GCSTarget("gs://a-test2/tmp_test2.txt")

```

実際の実行には gsutil コマンドを使っている。
(gsutil コマンドの設定に関しては以下を参照,gcloud コマンドの設定ができれば使える。
 https://ietoa.blogspot.com/2018/07/gcp-google-cloud-platform.html )
依存の設定に luigi.contrib.gcs.GCSTarget を使っているが
その前に import luigi.contrib.gcs という記述がないとエラーが生じるので注意。

# luigi で Bigquery のテーブルを依存先に設定する方法
Bigquery 上のテーブルを依存先として設定する方法を調査した。
## コード
以下は Bigquery において, プロジェクトコードが watashi_no_project,
dataset が "temp_results"で、
"my_table" -> "my_table_filter" -> "my_table_count"
のように中間テーブルの作成が依存している場合のコードとなっている.
BigqueryTarget は table.dataset_id, table.table_id によって dataset と table を表す文字列を取得できる。
(https://github.com/spotify/luigi/blob/master/luigi/contrib/bigquery.py)

```
import luigi
from luigi.contrib.bigquery import BigqueryTarget

PROJECT_ID = 'watashi_no_project'

...

class SelectQuery( luigi.Task ):
    dest_dataset_id = "temp_results"
    dest_table_id = "my_table"
    def run():
        print("this is given!")
        exit(1)

def output(self):
        return BigqueryTarget( PROJECT_ID,
                               self.dest_dataset_id, self.dest_table_id )
    
class FilterQuery( luigi.Task ):
    dest_dataset_id = "temp_results"
    dest_table_id = "my_table_filter"
    start_date = "2018-04-01"    
    def requires(self):    
        return SelectQuery()
    
    def run(self):
        exec_filter_query_by_date( self.start_date,
                                   self.input().table.dataset_id,
                                   self.input().table.table_id,
                                   self.output().table.dataset_id,
                                   self.output().table.table_id )
    def output(self):
        return BigqueryTarget( PROJECT_ID,
                               self.dest_dataset_id, self.dest_table_id )

class KaimonoCountQuery( luigi.Task ):
    dest_dataset_id = "temp_results"
    dest_table_id  = "my_table_count"
    def requires(self):
        return FilterQuery()

def run(self):
        exec_count_query( self.input().table.dataset_id, self.input().table.table_id,
                          self.output().table.dataset_id, self.output().table.table_id )
    
    def output(self):
        return BigqueryTarget( PROJECT_ID,
                               self.dest_dataset_id, self.dest_table_id )

```

# luigi で同じ task を並列に実行したい場合
下記のコードのように各タスクにパラメータを設定してやって、
あるタスクの requires に違うパラメータでインスタンスを設定する。
さらに設定ファイル、実行コマンドにおいて指定する要素がある。

## コード

```
#coding:utf-8
import os
import luigi

class TestTask(luigi.Task):
    n = luigi.IntParameter() # インスタンス毎に異なるパラメータ.
    def run(self):
        os.system( "echo hello %d >%s"%( self.n, self.output().path) )
    def output(self):
        return luigi.LocalTarget( "test_task_%d.txt"%self.n )
    
class TestTaskTotal(luigi.Task):
    def requires(self):
        ret_list = []
        for i in range(4):
            ret_list.append( TestTask(n=i) )
        return ret_list
    
    def run(self):
        print("ok")

```
## 設定ファイルと実行コマンド
並列実行する場合、さらに以下のように「設定ファイル」と「実行コマンド」における設定が必要
### 設定ファイル
4 並列したい場合は以下のように設定する必要がある。(デフォルトは実行するマシンのコア数になっている。)
luigi.cfg
```
[core]
parallel-scheduling-processes=4
```
### 実行コマンド
4 並列したい場合、以下のように実行する必要がある。(設定がないと実行はされるが並列実行にはならないので計算時間の改善にならない)。
gcloud コマンドで複数マシンに並列実行させる場合などで有効。
```
PYTHONPATH="." luigi --local-scheduler --module mytmp TestTaskTotal --workers=4
```

# 並列実行に関する話題
以下の記事のよると windows 上での並列実行では問題が生じる可能性がある。（未確認）
https://qiita.com/soyiharu/items/e54bd963f9faf22c6cae

また並列実行ジョブの個数と速度感については以下を参照。
https://qiita.com/yanagi3150/items/15b2928b5018b197ab45

思想としてもある程度の粗い粒度でのジョブ実行を想定していることがわかる。
https://luigi.readthedocs.io/en/stable/design_and_limitations.html

## 注意
joblib と併用すると問題になる可能性がある。(未検証)

# オンメモリでの取り扱いについて
luigi はオンメモリでの依存処理は推奨していないようだ。(以下の記事参照)
https://qiita.com/yanagi3150/items/6dd88af31ad55d98bb33

# 依存設定のカスタマイズ
luigi はデフォルトだと依存解決にターゲットファイルがあるかないかしか見ない。make がファイルの更新時間を見るのと比べるとだいぶてきとう。多分、ネットワーク越しの依存などを見るため、時間の同期などを保証できないだろうと想定しているからと思われる。
その代わり依存解決のカスタマイズができる。
https://qiita.com/ngr_t/items/b928bc13457571e25519
と
https://gist.github.com/demoray/b503c887518941d264b0
を見る限りでは task クラスの complete メソッドを定義してやれば良い。

## 依存関係の実装
上記のリンク先の記事を参考に書いてみた。
以下は test_task.txt が test_task2.txt より新しければ TestTask2 が実行される.
```
#coding:utf-8
import os
import datetime

import luigi

class TestTask(luigi.Task):
    def run(self):
        os.system( "echo hello 111 >%s"%( self.output().path) )
    def output(self):
        return luigi.LocalTarget( "test_task.txt" )
    
class TestTask2(luigi.Task):
    def requires(self):
        return TestTask()
    def run(self):
        os.system( "cat %s >%s"%( self.input().path,
                                  self.output().path) )
    def output(self):
        return luigi.LocalTarget( "test_task_2.txt" )
    
    def complete(self):
        output_fpath = self.output().path
        if os.path.exists( output_fpath ) == False:
            return False
        input_fpath = self.input().path
        if os.path.exists( input_fpath ) == False:
            return False

input_datetime = datetime.datetime.fromtimestamp(  \
                                    os.path.getmtime( input_fpath ) )
        output_datetime = datetime.datetime.fromtimestamp(  \
                                    os.path.getmtime( output_fpath ) )
        if input_datetime > output_datetime:
            return False
        return True
```
なんとなくだけれども全てのタスクにここまで書かせるのはきついだろうと思うんで、何か良いライブラリやクラスがあるんではないかとも思う。
とりあえずここでは実装できて、実際に機能するということだけ確かめておいた。

# 全てのターゲットを消去して実行したいときなど
以下のページで方法についてだいぶ議論している。まだ追えてない。。時間のあるときに再調査！
https://github.com/spotify/luigi/issues/595

tensorflow の batch normalize に関して

# 目的
実際の処理についてデバッグしてみた。

# コード
以下のコードは
バッチの大きさ = 3 で
変数一個の層が2 つ重なったネットワークで
 $$f = x^3 + 1 $$
という関数を回帰するだけのトレーニング。

```
#coding: utf-8

import random

import tensorflow as tf
import numpy as np

random.seed(0)

training = tf.placeholder_with_default( False, shape=(), name="training" )

x = tf.placeholder( tf.float32, shape=(None,1) )

#w = tf.Variable( tf.zeros([1,1]) )
w = tf.Variable( tf.ones([1,1]) )
#b = tf.Variable( tf.zeros([1]) )
b = tf.Variable( tf.ones([1]) )
hidden_tmp = tf.matmul( x, w ) + b # 行列の掛け算
#hidden = tf.sigmoid( hidden_tmp )
bn1 = tf.layers.batch_normalization( hidden_tmp, training=training, momentum=0.9 )
hidden = tf.sigmoid( bn1 )
#print( dir(bn1) )
#exit(1)

w2 = tf.Variable( tf.ones([1,1]) )
#b2 = tf.Variable( tf.zeros([1]) )
b2 = tf.Variable( tf.ones([1]) )
f = tf.sigmoid( tf.matmul( hidden, w2 ) + b2 ) # 行列の掛け算

f_ = tf.placeholder( tf.float32, shape=(None,1) )
loss = tf.reduce_mean( tf.abs( f_ - f) )
learn_rate = 0.5
trainer = tf.train.GradientDescentOptimizer( learn_rate )
extra_update_ops = tf.get_collection( tf.GraphKeys.UPDATE_OPS )
with tf.control_dependencies(extra_update_ops):
    trainer_op = trainer.minimize(loss)
#trainer_op = trainer.minimize( loss )

batch_size = 3
epochs = 10
with tf.Session() as sess:
    init = tf.global_variables_initializer()
    init.run()
    for i in range( epochs ):
        batch_xs, batch_fs = [], []
        #print( w.eval() )
        for j in range( batch_size ):
            x1 = random.random()
            f1 = x1*x1*x1 + 1 # この関数を訓練させる！
            batch_xs.append( [ x1 ] )
            batch_fs.append( [ f1 ] )

print( batch_xs )
        for v in tf.global_variables():
            print(v.name, v.eval() )
        print( hidden_tmp.eval( feed_dict={x: batch_xs } ) )
        print( bn1.eval( feed_dict={x: batch_xs } ) )

sess.run( [trainer_op, extra_update_ops],
                  feed_dict={x: batch_xs, f_: batch_fs, training:True } )

result_loss = loss.eval( feed_dict={x: batch_xs, f_: batch_fs } )
        print( "result_loss:", result_loss )
 
```

# 出力
以下のような出力がなされる。
```
[[0.6108869734438016], [0.9130110532378982], [0.9666063677707588]]
Variable:0 [[0.9991983]]
Variable_1:0 [1.]
batch_normalization/gamma:0 [0.9833956]
batch_normalization/beta:0 [0.12067804]
batch_normalization/moving_mean:0 [0.9730693]
batch_normalization/moving_variance:0 [0.41279468]
Variable_2:0 [[1.2562904]]
Variable_3:0 [1.5393883]
[[1.6103973]
 [1.9122791]
 [1.9658315]]
[[1.0949917]
 [1.5564928]
 [1.638361 ]]
....
```
# 考察

```
hidden_tmp = tf.matmul( x, w ) + b # 行列の掛け算
bn1 = tf.layers.batch_normalization( hidden_tmp, training=training, momentum=0.9 )
```
上記の hidden_tmp と bn1 の出力値を比べると
m_m : moving_mean
m_v : moving_variance
bn1 = gamma*( (hidden_tmp - m_m) /math.sqrt( m_v+0.00001) ) + beta
の関係にあることが確認できる。

# 課題
hidden_tmp のバッチの平均値に対して移動平均が取られて, moving_meabnとなっていることを確認した方が良い。

ランク付けに関する相関

# 目的
レコメンドにおいて機械学習により各ユーザーに対して各アイテムのランク付けを行う。
条件を変えるとランクが変わるが、そのランクの相関を測ることでどれだけランクが変動したかを表す指標があると良い。
「A New Rank Correlation Coefficient for Information Retrieval」にそのようなランクの指標が示されているのでこれを元に記載する。

#  Kendall’s tau
Kendall の tau はそういった指標の古典的なものである。(1938年ごろ)
https://ja.wikipedia.org/wiki/%E3%82%B1%E3%83%B3%E3%83%89%E3%83%BC%E3%83%AB%E3%81%AE%E9%A0%86%E4%BD%8D%E7%9B%B8%E9%96%A2%E4%BF%82%E6%95%B0
N 個のアイテムに対する二つのランク付けに対して、順位が入れ替わっていないペアの個数を K, 入れ替わっている個数を J とした時
$$tau = \frac{K-J}{N*(N-1)/2}$$
と表される。
tau は - 1 から 1 の間で 1 に近い方がより相関が高く、 -1 に近いと逆相関になっている。0だと無相関といった形。

例:
5 つのアイテム(A~E)に対して二つのランク付け X, Y が以下のようであったとする。
       1, 2, 3, 4, 5
X: C, E, A, B, D
Y: D, A, B, E, C

この時、アイテムの組み合わせは
(A,B) ,(A,C),  (A,D) , (A,E) 
(B,C) , (B,D) , (B,E) ,
(C,D) , (C,E) 
(D,E) 
の 10 通りで、そのうち X, Y で順位が入れ替わっていないものは (A,B) の1組なので K=1
そのほかは入れ替わっているので J = -9
よって
tau = -0.8 となる。

# AP correlation( average precision correlation)

$$tau_{ap} = \frac{2}{N-1} \sum_{i=2}^N(\frac{C(i)}{i-1}) -1$$

ここで $C(i) $ は X のランクが i のアイテム1 と X のランクが i より上(つまり番号としては小さい) アイテム2 に対して、Y のランクにおける順位の大小が同じもののペア数

登録: 投稿 (Atom)