2019-01-01

ハフマン符号化と交差エントロピー

ハフマン符号化が交差エントロピーとつながってて面白かった

ハフマン符号化とは

例えば文字列「ABAACBDA」をエンコードするとする。工夫せずにエンコードしようとすると以下の通り。

文字	対応ビット
A	00
B	01
C	10
D	11

するとエンコードされた文字列は「00 01 00 00 10 01 11 00」の16ビットとなる。ハフマン符号化では出現頻度の多い文字に少ないビット数を割り当てることでデータの圧縮を可能にしている。例えば今回の文字列を以下のように割り当てると

文字	対応ビット
A	0
B	10
C	110
D	111

エンコードされた文字列は「0 10 0 0 110 10 111 0」の14ビットとなり少し圧縮された。今回は例があまり適切ではなかったがものによっては70%以上圧縮されたりする。実際は適当に割り当てるのではなくハフマン木というものを作って効率の良い割り当てを行う。

交差エントロピー

1文字に割り当てられるビット数の平均を平均符号数といい以下の式で表す。

$$\sum p(x_i)bit(x_i)$$

$p(x_i)$ は文字 $x_i$ が出現する確率で $bit(x_i)$ は文字 $x_i$ に割り当てるビット数。 $bit(x_i)=\log{\frac{1}{p(x_i)}}$ の時に平均符号長が最小となることが証明されているので書き直すと

$$H=\sum p(x_i)\log{\frac{1}{p(x_i)}}$$

Hをエントロピーと呼んだりするらしい。
ここで、確率分布 $P$ に従う文字列を、確率分布 $Q$ で最適化された方式でエンコードした時のエントロピーを考えると

$$H=\sum P(x_i)\log{\frac{1}{Q(x_i)}}$$

となる。このような式を交差エントロピーと呼んだりするらしい。PとQの分布が異なるとHの値は大きくなる。逆に言えば交差エントロピーが小さい時はPとQの確率分布は同じようなものだと推定できる。この性質を利用して機械学習で損失関数として使われたりする。例えばtensorflowでは次のように記述。

cross_entropy = -tf.reduce_sum(y_*tf.log(y))

もっとも、最近では交差エントロピーを計算する関数がすでに用意されているのでいちいち書く必要はないが。

まとめ

ハフマン符号化で効率よく圧縮できる
交差エントロピーの大きさで確率分布の重なり具合を推定

2018-10-04

遺伝的アルゴリズムで作った画像集

遺伝的アルゴリズムで画像を学習したかった - 日々の記録

上の記事で作った生成器での作品集

f:id:busongames:20181004223531j:image
f:id:busongames:20181004223522j:image
f:id:busongames:20181004223533j:image
f:id:busongames:20181004223518j:image
f:id:busongames:20181004223527j:image
f:id:busongames:20181004223524j:image

お気に入りはキトゥンちゃん

2018-09-15

遺伝的アルゴリズムでsnakegameを学習したかった

方針

入力を

頭の1マス左に壁があるか
頭の1マス正面に壁があるか
頭の1マス右に壁があるか
頭の1マス左に自分の体があるか
頭の1マス正面に自分の体があるか
頭の1マス右に自分の体があるか
頭の左側に餌があるか
頭の前側に餌があるか
頭の右側に餌があるか

の9つ、出力を

左に進む
前に進む
右に進む

の3つからなるニューラルネットワークを考える。入力は0か1で右とか左とかは絶対的なものではなく蛇の進行方向から見てである。
今回はそのニューラルネットワークの重みを遺伝的アルゴリズムで進化させていく。

適応度の設定

最初は餌を食べたら10ポイント、1ターン生きたら1ポイント増やす方向で考えていたが、どうやらそれだと蛇が同じところをぐるぐる回るように進化してしまうので、餌に近づいたら1ポイント、餌から離れたら-2ポイントというようにした。調べてみると、もっと複雑にしている人もいるようだが今回は簡単のためこれにした。
また、適用度計算のときはたまたま運良く点数が高かった物が選ばれる状況を避けるため、50回ほどループを回し平均を最終的な値とした。

その他いろいろあるが割愛。

結果

f:id:busongames:20180915170212g:plain — 1世代目

f:id:busongames:20180915170222g:plain — 2世代目

(GIFの大きさが違うのは目をつぶってください)
2世代目で既にうまくいっている。逆に自分のコードではここから世代を重ねてもあまり変わらなかった。餌と頭を繋いだ直線上に体があった時餌を優先してしまい体にあたりゲームオーバーということがなんど世代を重ねても直らなかった。悔しい。でもそれなりにうまくいったと思う。

↓参考にした動画。

AI learns to play snake using Genetic Algorithm and Deep learning

GTC japanも行ってモチベーション上げた。

2018-09-07

遺伝的アルゴリズムで画像を学習したかった

きっかけ

rogerjohansson.blog
上の記事を読んでpythonで作ってみたくなった。記事内では世代の中の個体数は1体だけだったので10体に増やし交叉を取り入れてみたらどうなるだろうと思った。

方針

それぞれの個体はポリゴンの集合を持ちそれぞれのポリゴンは頂点座標、rgb値、透明度を持っている。ウィンドウ表示はtkinterが楽だったがtkinter.canvasでは透明度を変更できなかったのでpillowでnew imageにポリゴンを描画して最後にcanvasにその画像を貼る形にした。この方が処理も早くなる。

交叉では二点交叉を使いポリゴンの集合を入れ替える。コードはDEAPのcxTwoPoint()を参考にした。

def cxTwoPoint(ind1, ind2):
    size = min(len(ind1), len(ind2))
    cxpoint1 = random.randint(1, size)
    cxpoint2 = random.randint(1, size - 1)
    if cxpoint2 >= cxpoint1:
        cxpoint2 += 1
    else: # Swap the two cx points
        cxpoint1, cxpoint2 = cxpoint2, cxpoint1
   
    ind1[cxpoint1:cxpoint2], ind2[cxpoint1:cxpoint2] \
        = ind2[cxpoint1:cxpoint2], ind1[cxpoint1:cxpoint2]
        
    return ind1, ind2

しかしこのままではshallow copyになってしまうのでcopy.deepcopyでコピーした値を返す。

突然変異はそれぞれの個体に対して一定確率でポリゴンを追加したり削除したり並び順を変えたりポリゴンの頂点座標を変えたり画素を変えたりした。これはリンクをたどった先のソースコードをpythonで真似しただけ。

最初は選択方法としてimagehashを使おうと思ったが、より細かくしたかったので画像をnp.arrayとしてピクセルごとの画素の差の2乗の和を比べて小さいものをエリート選択で決めていくことにした。

その他いろいろあるが割愛。

結果

f:id:busongames:20180907231138j:plain — モナリザ

f:id:busongames:20180907230423p:plain — モナリザ

f:id:busongames:20180907231135p:plain — appleロゴ

f:id:busongames:20180907230429p:plain — appleロゴ

f:id:busongames:20180907231141j:plain — emoji

f:id:busongames:20180907230436p:plain — emoji

すべて60万世代後の結果である。モナリザのオリジナル画像はどっかにいってしまったので近い構図の画像を貼った。

これ交叉いらなくね

一つの世代に10個体にしたが、最終的にどれも全く変わらないものが10個できてしまった。他のポリゴンとの重ねあいで色合いができていくので交叉したら適応度が下がることはよくよく考えてみれば当たり前だった。最初の方に同じような個体が選択されてそれ同士が交叉してもあまり変わらないので10個が同じ画像になったと考えられる。
最終的に個体数を1体に減らしそれを突然変異させた息子と比べるようにした。こっちの方が早く計算もできるしポリゴンの数も100をこえ複雑な形に対応できるようになった!

2018-08-18

tkinterをやってみよう

pythonにいくつかあるGUIライブラリの中で一番手軽に扱えそうなtkinterをいじってみた。本当はkivyとかやりたかったがうまくインストールできなかった、、、

雛形

root = tkinter.Tk()
root.mainloop()

ボタンやラベルなど一通りのものは貼れる。
イベントを登録するにはbind()を使う。例えばボタンに登録するには

button.bind("<1>",method)

methodが実行されてほしい関数。<1>は左クリックが押された時にという意味で、他にも<2>だと右クリックで実行されたりとバリエーションがある。注意点としてmethodの引数にeventを指定する。buttonの定義時にcommandで指定するやり方もあるらしいがbindの方が拡張性が高い？

canvasを登録すれば図形描画もできる。

canvas = tkinter.Canvas(self,bg="white", height=750, width=500)
canvas.create_line(100, 100, 200, 200, fill='blue') #線
canvas.create_polygon(150, 150, 500, 20, 200, 40, fill="red") #多角形
canvas.pack()

f:id:busongames:20180818172216p:plain

模索して作ったサンプルファイル

import tkinter
from tkinter import filedialog as tkFileDialog
from PIL import Image, ImageTk

class Application(tkinter.Frame):

    def __init__(self, master=None):
        super().__init__(master)
        self.pack()
        self.create_widgets()

    def create_widgets(self):
        self.button1 = tkinter.Button(self,text="select")
        self.button1.pack()
        self.button1.bind("<1>",self.photoselect)
        self.leftC = tkinter.Canvas(self,bg="white", height=750, width=500)
        self.leftC.pack(side="left")
        self.rightC = tkinter.Canvas(self,bg="white", height=750, width=500)
        self.rightC.create_line(100, 100, 200, 200, fill='blue')
        self.rightC.create_polygon(150, 150, 500, 20, 200, 40, fill="red")
        self.rightC.pack(side="right")

    def photoselect(self,event):
        filename=tkFileDialog.askopenfilename()
        self.img = Image.open(filename)  
        self.image = self.photoresize(self.img)
        self.img = ImageTk.PhotoImage(self.image)
        self.leftC.create_image( 0, 0, image = self.img, anchor = tkinter.NW )

     #画像の縦横比で縮尺のサイズを変える
    def photoresize(self,img):
        w,h=img.size
        if w/h>=500/750:
            return img.resize((500,int(h*500/w)))
        else:
            return img.resize((int(h*750/h),750))


if __name__ == "__main__":
    root = tkinter.Tk()
    root.geometry("1000x800")
    app = Application(master=root)
    app.mainloop()

間違いございましたらお願いします。

2018-07-18

illustrator 暇つぶし

f:id:busongames:20180718162019j:plain

なんかかっこよくなった「*ぶ」

2018-07-17

コマンドシェルを自作のメモ

なんとなくやってみたくなったのでメモ

シェルコマンドはパスを探って実行される

echo $PATH

で確認。
コマンドを記述してそのファイルをパスのどれかにいれる、またはファイルのあるディレクトリをパスに追加する。

ファイルを作成。ファイル名がコマンド名になる。今回はhelloで保存。

#!/bin/sh
echo" HelloWorld"

一行目はおまじないのようなものでこれでインタプリタを指定するらしい。

なんか権限をいじって誰でも使えるようにするらしい。以下のコマンドを入力。

$chmod a+x hello

あとはhelloファイルを$PATHのどこかのディレクトリに追加。helloのあるディレクトリをパスに追加してもよい。

$hello
HelloWorld

$nでn番目の引数を参照してくれるらしいので、weather 地名　で天気を表示するコマンドを作った。元のファイルは昔作ったpythonのファイルを使用。

$weather tokyo
http://weather.livedoor.com/area/forecast/130010
東京都 東京 の天気
今日:晴のち曇
明日:晴時々曇
min:27
max:35
明後日:晴時々曇

満足