2019-08-26

pytorchでレイヤーをフリーズさせる

画像分野で深層学習を用いる際はImageNetのような大規模データセットで学習した学習済みモデルを使用して転移学習、ファインチューニングを行うことが一般的です。
このファインチューニングを行う際に、最初の数エポックはモデルの最終層以外の重みを固定し最終層だけ学習、その後に全レイヤーの重みを学習するといったテクニックがあります。

blog.floydhub.com

www.analyticsindiamag.com

一般的にニューラルネットワークの入力層に近いほど学習データの抽象的な特徴を学習していると言われていますが、
このテクニックを使うことにより、学習初期にいきなり入力層に近いレイヤーの重みが更新されることで抽象的な特徴抽出機能が崩壊することを防ぐ効果があります。

pytorchでは以下のようにパラメータをrequires_grad=Falseすることによってbackward()の際に重みが更新されないようにする（freeze）ことができます。

from torchvision.models import resnet34
model = resnet34(pretrained=True)

# freeze all layers
for param in model.parameters():
    param.requires_grad = False

上記の例だと最終層も含めてすべてのレイヤーがfreezeされてしまうので最終層はrequires_grad=Trueのままにしておきます。

from torchvision.models import resnet34
model = resnet34(pretrained=True)

# freeze layers except last layer
for param in model.parameters():
    param.requires_grad = False

last_layer = list(model.children())[-1]
print(f'except last layer: {last_layer}')
for param in last_layer.parameters():
    param.requires_grad = True

このようにしてやることで最終層だけ除いてレイヤーの重みを固定することができます。

この状態で数エポック学習を回して最終的に全レイヤーを学習する際はrequires_grad=Trueに戻してあげればOKです。

from torchvision.models import resnet34
model = resnet34(pretrained=True)

# unfreeze all layers
for param in model.parameters():
    param.requires_grad = True

2019-02-22

jenkinsとgithubを連携して自動テストをする

web上にいろいろ情報が錯綜していていろいろハマったので成功したやりかたをメモしておく

やりたいこと

githubに新しいcommitがpushされるごとにそのソースコードをビルドしてテストする
テスト結果をgithub上から確認できるようにする
github側の設定
ビルドしたいレポジトリにwebhookを設定する
- settings -> webook
  - pyload url
    - http://****/github-webhook/
  - content type
    - application json
  - Which events would you like to trigger this webhook?
    - "Just the push event." or "Send me everything."
access tokenの設定
- 個人アカウントのsettings -> developer settings -> personal access token
  - generate new token
  - repoとadmin:repo_hookをチェック

jenkins側の設定

jenkinsの管理 -> システムの設定 -> github
- github server
  - name
    - Github
  - API URL
    - https://api.github.com
  - credential
    - secret textで追加
      - 先程作成したpersonal access tokenを登録
  - manage hooks
    - よくわからん、とりあえずチェックなしにした
  - test connectionでちゃんとつながればおk
ジョブの設定
- フリースタイルプロジェクトのビルド
  - github projcet
    - project url
      - ビルドしたレポジトリのURL
    - ビルドのパラメータ化
      - 名前
        
        payload
      - デフォルト値
        
        none
  - ソースコード管理
    - リポジトリURLと認証情報を設定
    - ブランチ指定
      - origin/*
  - ビルド・トリガ
    - GitHub hook trigger for GITScm polling
  - ビルド
    - シェルの実行
      - 任意のシェルスクリプトを書く
  - ビルド後の処理
  - うまく設定できていればレポジトリにpushされたときに自動でbuildが走ってcommit statusがgithub上から確認できる

2018-11-24

fastaiのバージョン0.7をインストールする

fastaiという無料でディープラーニングについて学べる講座がありますが、その講義の中でfastaiというライブラリが使われています。 github.com

このライブラリはpytorchのラッパーのような形になっており、実際にディープラーニングをする上でのベストプラクティスが簡単に適用できることが特徴のようです。

実際に最適な学習率の初期値を見つけてくれる関数や[1506.01186] Cyclical Learning Rates for Training Neural Networksのような手法が簡単に使えるようになっています。

fastaiのライブラリは現在v1.0が公開されていますが、講義で使われてものやkaggleのkernelで使われているのはv0.7が多いようでv1を使っているとそのままでは動かないスクリプトが多数あります。 Githubにあるcondaやpipをつかってインストールすると最新版が入ってしますのでv0.7を使いたい場合は別の方法でインストールする必要があります。

fastaiのforumにはcondaの仮想環境を使ってv0.7のインストール方法がありますが、私の場合はどうもエラーが出てうまくいかなかったので別の方法をとりました。

v0.7のコードはfastaiレポジトリの old/fastai に移されているのでここにpythonのパスを通すことで使うことにします。

まず適当なディレクトリに移動してfastaiのレポジトリからクローンしてきます。

cd /tmp/
git clone https://github.com/fastai/fastai
cd fastai/old/

その後、pythonのスクリプトでパスを通すことでimport できるようになります。

import sys
sys.path.append("/tmp/fastai/old") # on windows use \'s instead
import fastai

fastaiは裏でpytorchやtorchvisionを呼び出しているので別途インストールしておいてださい。

conda install pytorch torchvision cuda92 -c pytorch

2018-05-06

Hash Tables (Cousera Data Structure Week 4)

CouseraのData Strucureコースのweek4の内容です。
www.coursera.org

前回のweek3の内容の記事はこちら
rikeiin.hatenablog.com

Week4の内容はHash Tablesです。

Hashingの応用例

プログラミング言語
- Pythonでは辞書、 JavaではHashMapなど
File Systems
Password Verification
Storage Optimization

IP Addresses

あるWebサーバにアクセスしてきた各IPアドレスが過去一定期間にアクセスがあったか判定するという問題を考える。

単純に配列を使った実装の場合、考えうるIPアドレス数の長さの配列を用意し、該当するIPアドレスに対応するインデックスの要素をインクリメントする方法がある。
このとき、

アクセスリストを更新する操作は(UpdateAccessList)は一つのログにつきO(1)
一定期間にアクセスがあったか判定する操作(AccessedLastHour)はO(1)
IPv4でも2の32乗のメモリが必要
IPv6では2の128乗であり、もはやメモリに乗らない

配列を使った実装はメモリを多く消費するため、リストを使った実装を考える。

List-based Mapping

過去一定期間にアクセスしてきたIPアドレスのみをリストに保存する。
このとき、アクセス順にリストにつなげていく。

f:id:rikeiin:20180503183048p:plain

nは一定期間にアクセスがあったIPアドレスの数
メモリ消費量は $\Theta (n)$
L.Append, L.Top, L.Popは $\Theta (1)$
L.Find, L.Eraseは $\Theta (n)$
UpdateAccessListは $\Theta (n)$
AccessedLastHourは $\Theta (n)$

Hash Functions

ハッシュ関数の定義

あるオブジェクトの集合 $\mathcal S$ と $m>0$ となる整数があるとき、関数 $h: \mathcal S \rightarrow \{0, 1,\dots, m-1\}$ をハッシュ関数と呼ぶ。

このとき、 $m$ をハッシュ関数 $h$ の基数(cardinality)と呼ぶ。

ハッシュ関数の望ましい要件

$h$ の計算が早い
異なるオブジェクトには異なる値
メモリ使用量が $O(m)$ でマップできる
基数 $m$ は小さくしたい
もしオブジェクトの数 $|\mathcal S|$ が $m$ より大きいとき、すべてを異なる値にマップすることは不可能である

Collisions

$h(o_1)=h(o_2)$ かつ $o_1\neq o_2$ のとき、これを衝突(collision)と呼ぶ。

Chaining

Map

マップはあるオブジェクトからあるオブジェクトへのマッピングを行う。
例えば、以下のような例がある。

ファイル名→ディスク上のファイルの場所
学生ID→学生名
契約名→契約電話番号

$\mathcal S$ から $\mathcal V$ へのマップはHashKey(O), Get(O), Set(O, v)の操作を持つデータ構造である。このとき、 $O\in S, v \in V$

Chaining

f:id:rikeiin:20180505224216p:plain

マップに関する各操作の疑似コードを以下に示す。

f:id:rikeiin:20180505225558p:plain
f:id:rikeiin:20180505225620p:plain
f:id:rikeiin:20180505225641p:plain

の最大のチェインの長さをとすると、HashKey, Get, Setの時間計算量は
- $c=0$ のとき $O(1)$
$n$ を現在のマップの異なるキー $O$ の数、 $m$ をハッシュ関数の基数とするとメモリの消費量は $\Theta(n+m)$

Hash Tables

Set

SetはAdd(O), Remove(O), Find(O)の操作を持つデータ構造である。
chainingを使ったSetの実装方法は二通りある。
f:id:rikeiin:20180505233025p:plain

Setは $S$ から $V=\{true, false\}$ へのマップと等しい
$(O, v)$ のペアを保存する代わりに $O$ のみを保存する

Setに対する各操作の疑似コードを以下に示す。

f:id:rikeiin:20180505233025p:plain
f:id:rikeiin:20180505233046p:plain
f:id:rikeiin:20180505233204p:plain

SetもしくはMapを用いたhashingの実装をHash tableと呼ぶ。

各プログラミング言語では以下のようなクラスに実装されている。

Set
- unordered_set in C++
- HashSet in Java
- set in Python
Map
- unordered_map in C++
- HashMap in Java
- dict in Python

まとめ

Chainingはhash tableを実装するためのテクニックのひとつである
メモリ消費量は $O(n+m)$
各操作の時間計算量は $O(c+1)$
どのようにmとcの両方を小さくするか？

2018-04-30

Disjoint Sets (Cousera Data Structure week3)

CouseraのData Strucureコースのweek3の内容です。
www.coursera.org

前回のweek3の内容の記事はこちら
rikeiin.hatenablog.com

Disjoint-set

Disjoint-setは以下の操作を持つデータ構造である

MakeSet(x)：集合{x}を作る
Find(x)：xを含む集合のIDを返す
- もしxとｙが同じ集合に属していればFind(x)==Find(y)
Union(x, y)：ｘとｙを含む２つの集合を結合する

単純な実装

集合の最も小さい値の要素をその集合のIDとして使う
smallest[1...n]のような配列を使う
- smallest[i]にiが所属する最小の要素の値を入れる

f:id:rikeiin:20180428215229p:plain
f:id:rikeiin:20180428215301p:plain
f:id:rikeiin:20180428215438p:plain

効率的な実装

単純な実装のボトルネックはUnion操作である。
Linked listを使うことでより効率的な実装が可能。
- 集合をLinked listで表し、listの末尾を集合のIDとして使う

f:id:rikeiin:20180428220453p:plain

↓

f:id:rikeiin:20180428220528p:plain

メリット
- Unionの実行時間がO(1)
デメリット
- 末尾を探すためにリストを走査する必要があるため、Findの実行時間がO(1)
- ｘのリストの末尾とｙのリストの先頭を定数時間で取得できる場合のみUnionの実行時間はO(1)

木構造を用いたさらに効率的な実装

集合を一つの木で表す
IDはその木構造のルート
parent[1...n]という配列を使う
- parent[i]はiの親もしくはiがルートであるならばi自身

f:id:rikeiin:20180428223100p:plain
f:id:rikeiin:20180428223204p:plain

どのように２つの木をマージさせるか？
片方の木をもう片方のルートノードの下にぶら下げる
- 木を浅くしておくため、短い木をぶら下げる

f:id:rikeiin:20180428225415p:plain

木の高さを素早く見つけるために各サブツリーの高さを配列rank[1...n]に保持しておく
- rank[i]はルートがiであるサブツリーの高さを表す
高い木の下に短い木をぶら下げることをunion by rank heuristicと呼ぶ

まとめ

union by rank heuristicを使うことでUnionとFindの実行時間がO(log n)になる

Path Compression

木の高さを短くする方法。例えば以下の図の例でFind(6)を実行する場合、ノード6からルートノードまで親を辿っていく必要があるが、その際12と3もルートノードも同時にわかるので以下の様に木を変形できる。

f:id:rikeiin:20180428232818p:plain

O(log n)の操作をn回繰り返すときの計算量をlog*nと定義する。
f:id:rikeiin:20180430161203p:plain

f:id:rikeiin:20180430161247p:plain

つまり一回の操作の時間計算量は漸近的にO(log*n)となり、実質的にlog*n < 5のときは定数時間とみなせる。

まとめ

各集合を木構造で表現する
ルートノードをその集合のIDとする
Union by rank heuristic
- 高い木のルートの下に短い木を吊り下げる
Path Compresion heuristic
- ある特定のノードのルートを見つけるときに、走査したノードをルートの下に吊り下げる
償却的時間計算量はO(log*n)
- 現実的なｎの値でほぼ定数時間

2018-04-21

Priority Queues (Cousera Data Structure week3)

CouseraのData Strucureコースのweek3の内容です。
www.coursera.org

前回のweek2の内容の記事はこちら
rikeiin.hatenablog.com

Priority Queues (優先度付きキュー)

Priority Queueは通常のキューに格納されている要素に優先度がついたデータ構造である。
C++ではpriority_queue、JavaではPriorityQueue、Pythonではheapqとして実装されている。
典型的な用途としてはジョブのスケジューリングなどがあげられる。

priority queueは以下の操作を持っている。

Insert(p)：新しい要素を優先度pで挿入する
ExtractMax()：優先度が最大の要素を取り出す

オプションで以下の操作を定義することもある

Remove(it)：イテレータitでポイントされた要素を削除する
GetMax()：要素のセットは変えずに優先度が最大の要素を返す
ChangePriority(it, p)：イテレータitでポイントされた要素の優先度をpに変える

単純な実装

ソートされていない配列・リスト

f:id:rikeiin:20180415135651p:plain

Insert(e)
- 要素eを末尾に追加する
- 実行時間はO(1)
ExtractMax()
- 配列・リストを走査する
- 実行時間はO(n)

ソートされた配列

f:id:rikeiin:20180415140333p:plain

ExtractMax()
- 最後の要素を取り出す
- 実行時間はO(1)
Insert(e)
- 要素eの場所を探す(二分探索でO(log n))、右の要素を一つずつづらし(O(n))、挿入する(O(1))
- 実行時間：O(n)

ソートされたリスト

f:id:rikeiin:20180415141534p:plain

ExtractMax()
- 最後の要素を取り出す
- 実行時間：O(1)
Insert(e)
- 要素eの場所を探し(二分探索が使えないため、O(n))、挿入(O(1))
- 実行時間：O(n)

実行時間まとめ

f:id:rikeiin:20180415141825p:plain

Priority Queues: Binary Heaps(バイナリーヒープ)

Binary max-heapの定義は子より親のほうが値が大きい場合の二分木である。
以下がヒープである例
f:id:rikeiin:20180415142706p:plain

ヒープではない例
f:id:rikeiin:20180415142741p:plain

基本的なヒープに対する操作

GetMax

f:id:rikeiin:20180415142940p:plain

Insert

新しい要素を木の末端の葉にくっつける。
f:id:rikeiin:20180415143357p:plain

この操作において子より親の値が大きくなればならないという条件を満たしていな場合、以下のSiftUpという操作を条件が満たすまで行う。

SiftUp

シフトアップは子の大きい値と親の小さい値を入れ替えるという操作であり、木がヒープの条件を満たすまで繰り返す。
実行時間はO(木の高さ)である。

ExtractMax

木の根と葉を入れ替えることで行う。
f:id:rikeiin:20180415144715p:plain

上の木に対してExtractMaxを行うと以下のようになる。
f:id:rikeiin:20180415144819p:plain

当然これはヒープの条件を満たしていないため、以下のSiftDownという操作を行う。

SiftDown

SiftDownは親の小さい値と子の大きいを入れ替えてノードを下にずらす操作である。
上の図の例では12と29を入れ替える。このとき左右の子の大きいほうと入れ替えること。
この操作をヒープの条件を満たすまで繰り返す。
もちろん実行時間はO(木の大きさ)

ChangePriority

任意のノードを任意の値に変える。その後にヒープの条件を満たすようにSiftUpかSiftDownを繰り返す。

Remove

削除したいノードの値を∞にかえる。
f:id:rikeiin:20180415150027p:plain

その後、ヒープの条件を満たすようにSiftUpを繰り返す（最終的に∞が根に来る）。
その後はExtractMaxと同じ操作を行う。
実行時間はO(木の高さ)

ヒープ操作のまとめ

GetMaxはO(1)だが他の操作はO(木の高さ)
木は出来る限り浅くしたい

どうやって木を浅くするか？

Complete binary tree の定義は最後の深さ以外のノードが全て埋まっており、最後の深さのノードは左から順に埋まっていることである。

Complete binary tree の例：
f:id:rikeiin:20180417172103p:plain:w500

Complete binary tree ではない例：
f:id:rikeiin:20180417172155p:plain:w500

n個のノードを持つcomplete binary treeの深さは最大で $O(log n)$
complete binary treeのメリットととして以下のように配列で表現できる。

f:id:rikeiin:20180417174103p:plain:w600

complete binary tree をキープしておくために

新しい要素をInsertするときは最後の深さで左から順に挿入する
ExtractMaxするときはルートノードと最後の葉と入れ替える

f:id:rikeiin:20180417174658p:plain:w200

Complete Binary Tree まとめ

すべての操作がO(log n)で動作して高速である(GetMaxはO(1))
配列で保持しておけるのでメモリ空間の効率がよい
実装が簡単

Heap Sort

Heap Sortのやり方

ヒープ構造を作る
ExstraMax()を繰り返す

ヒープ構造の作り方

下から上に向かっていくようにヒープ構造を修正していく
最初は深さ1のサブツリーから修正していき、ルートまでたどり着いたときにすべてのサブツリーに対してヒープ構造が保たれている
参考URL：Heap Sort Visualization
SiftDownをO(n)ノードに行うため計算量はO(nlog n)
ノードが葉に近ければShifDownは高速に行える

ヒープソートまとめ

PriorityQueueは主にInsertとExtractMaxという操作を持つ
リストと配列による実装は片方の操作はとても高速(O(1))だがもう片方の操作はとても遅い(O(n))
バイナリーヒープによる実装は両方の操作がO(log n)で行え、かつメモリスペース的にも効率がよい

記事が長くなってしまったのでDisjoint Setに関する内容は別記事にします。

追記：練習がてらにpythonでヒープソートを行うコードを書いてみました。

import numpy as np
import random

class HeapBuilder(object):

    def __init__(self, array_length):
        self._heap = np.random.permutation(np.arange(1,array_length+1))
        self.size = len(self._heap)
    def _parent(self, i):
        return (i - 1) // 2

    def _leftChild(self, i):
        return 2 * i + 1

    def _rightChild(self, i):
        return 2 * i + 2

    def _swap(self, i, j):
        temp = self._heap[i]
        self._heap[i] = self._heap[j]
        self._heap[j] = temp

    def _siftUp(self, i):
        while (i > 0) and (self._heap[self._parent(i)] < self._heap[i]):
            self._swap(i, self._parent(i))
            i = self._parent(i)
            
    def _siftDown(self, i, size):
        maxindex = i
        l = self._leftChild(i)
        if (l < size) and (self._heap[l] > self._heap[maxindex]):
            maxindex = l
        
        r = self._rightChild(i)
        if (r < size) and (self._heap[r] > self._heap[maxindex]):
            maxindex = r

        if i != maxindex:
            self._swap(i, maxindex)
            self._siftDown(maxindex, size)

    def buildHeap(self):
        for i in reversed(range(0, self._parent(self.size))):
            self._siftDown(i, self.size)

    def heapSort(self):
        self.buildHeap()
        n = self.size
        for _ in range(self.size):
            self._swap(0, n - 1)
            n -= 1
            self._siftDown(0, n)
    def showHeap(self):
        print (self._heap)

if __name__ == '__main__':
    heap = HeapBuilder(1000)
    heap.showHeap()
    heap.heapSort()
    heap.showHeap()

2018-04-14

海外では「技術面接の突破法」なんて授業がある

最近Rui Ueyamaさんのturingcomplete.fmを聞いて初めて知ったんですが海外の大学では「技術面接の突破法」なんて授業があるんですね。技術面接っていうのはいわゆるプログラミングなどコーディング面接です。 13. 自作アセンブラ、リンカの最適化、トリッキーなビット操作の楽しさ、外資系IT企業のコーディング面接対策 (hikalium)

以下はスタンフォード大学の授業のページです。スライドもすべて公開されています。 CS9: Problem-Solving for the CS Technical Interview

日本の大学ではこんなことまず教えないですよね。いかに英語と日本語で情報格差があるかを実感させられます。

資料を軽く読んでみたので簡単に内容をまとめてみました。

履歴書について

履歴書の書き方の原則

自分がやったことをすべてリストアップするな。戦略的に優先順位を付けて書くべし
内容に嘘は書かず正直に書け
履歴書に書いたことはすべて話せるように準備しておこう
専門家であれ。あなたの履歴書は誰が読むかわからない

履歴書クイックチェック

自分の履歴書に以下の内容が入っているか確認しましょう。

名前と連絡先
目的（必要であれば）
学歴
職歴
過去のプロジェクト（あれば）
スキルとプログラミング言語

以下詳細

名前と連絡先

以下のものは正確、かつ最新のものに

名前
メールアドレス(へんな名前のメールアドレスは使わないように)
電話番号
住所

目的

履歴書に目的を書くことで職探しをする上であなたが何を気にするかを伝えることができる。例えば、下記のような例がある。

「ソフトウェアエンジニアのサマーインターンシップを探しています」
「目的：大きな影響と成長の機会があるフロントエンドエンジニアのポジション」
「人々の生活に幸せをもたらすデザインと開発の経験」

目的は必須ではないが戦略的に使えば非常に有効である。

学歴

卒業大学、専攻など
GPAが良ければ(一般的に3.5+以上)載せましょう
関連した専攻あれば最も重要なものの概要を載せてよい
高校に関しては面接で聞いてほしいことがある場合のみ書いても良い

職歴

あなたが過去に携わった仕事の概要を以下の情報とともに記載

会社の名前と場所
働いていた期間
仕事の名前

その後にあなたが仕事で達成したことを書く

業績について

特定の動詞を使うとよい。 "worked"や"programmed"といった動詞より"Designed", "implemented", "prototyped", "tested", "deployed", "maintained"のような動詞がよい。

業績は可能ならば定量的に
技術面接であればそこで使った技術の概要を簡潔に含めるとよい
簡潔に書くべし。少ない文で書くことが難しければ重要なポイントをピックアップしてみる

最初の仕事の応募の場合

最初の仕事の応募である場合は職歴は必要ない。以下のようなことを書いてもよい。

他の分野で行ってきた仕事
クラブや組織でのリーダー経験
いままでやってきた個人的なプロジェクト（あれば）

極端に言えばあんたが「賢く」て「懸命に働く」ことが伝わればよい。

ちなみに、講義スライドでは「スタンフォード大学の学歴は非常に強い。同じ大学内の人と争う必要はない」とも言っている（笑）

過去のプロジェクト

個人的なプロジェクトを行っていればそれも書くことができる。なくても心配しなくてOK！もし書くなら以下の情報を載せる。

プロジェクト名
誰と一緒にやったか
プロジェクトの内容
あなたが特にやったこと
可能であればプロジェクトのURL

プログラミング言語とスキル

あなたが使いこなせるプログラミング言語と技術を書く。リストアップする際の注意点

あなたが履歴書で上げたプログラミング言語について面接で聞かれる可能性がある
経験したすべての言語を書くのではなくあなたが本当に使いこなせる言語を書くべし
「慣れている」や「いくつかの経験がある」といった書き方でもよい

履歴所については以上のような感じです。他にもコーディング面接に関する講義資料もあったので気が向いたときに別途記事にしたいと思います。

やりたいこと

github側の設定

jenkins側の設定

Hashingの応用例

IP Addresses

List-based Mapping

Hash Functions

ハッシュ関数の定義

ハッシュ関数の望ましい要件

Collisions

Chaining

Map

Chaining

Hash Tables

Set

まとめ

Disjoint-set

単純な実装

効率的な実装

木構造を用いたさらに効率的な実装

まとめ

Path Compression

まとめ

Priority Queues (優先度付きキュー)

単純な実装

ソートされていない配列・リスト

ソートされた配列

ソートされたリスト

実行時間まとめ

Priority Queues: Binary Heaps(バイナリーヒープ)

基本的なヒープに対する操作

GetMax

Insert

SiftUp

ExtractMax

SiftDown

ChangePriority

Remove

ヒープ操作のまとめ

どうやって木を浅くするか？

Complete Binary Tree まとめ

Heap Sort

ヒープ構造の作り方

ヒープソートまとめ

履歴書について

履歴書の書き方の原則

履歴書クイックチェック

名前と連絡先

目的

学歴

職歴

業績について

最初の仕事の応募の場合

過去のプロジェクト

プログラミング言語とスキル