sam_yusukeの日記

機械学習について書きます。

TodoistとPomodoneがいい感じ

今までRemember The Mlikを使っていましたが、久々にタスクツールを変えてみました。

  • タスク管理:Todoist
  • ポモドーロタイマ-: Pomodone

pomodoneはtodoistのタスクから撮ってきてポモドーロタイマーを開始できますし、 しかも、1日の統計情報も出してくれるので割と便利です。

  • できること
    • Projectごとにタスクをグループ化できる
    • 優先度付ができる
    • タスクを選んでポモドーロタイマーを開始できる
    • いろんなアプリからTOdoistのタスクを作れる(iOSで確認)
  • できないこと
    • タスクにかかる時間の見積もり
    • タグを付ける(有料プラン)
    • 5個以上のプロジェクトをPomodone側に同期する(有料プラン)

割と便利なのが、見ているWebサイトのURLをもとにタスクを作れることです。 昔と比べてアプリ間連携が強くなって使いやすくなった気がします。

タスク見積もりができないのでベロシティの管理はあまりできなさそうです。 個人のタスク管理なので、多少の予測性は犠牲にしてもいいかと、 それよりもタスクの洗い出しと自分の中の期限管理を優先したいので、 そういう意味ではTodoistで十分な気がします。

Scrapyを使ったクローラ開発

アーキテクチャ

実際のコードの書き方は公式DocやQiitaにたくさん書かれているので省きます。 ここでは主にアーキテクチャや提供されている機能をさらっと見ます。

クローラ作成フレームワークScrapyのアーキテクチャを見ていきます。

Scrapyは下の図のようなアーキテクチャになっています。 クローラを書きたいユーザはSpider, Item Pipelineを定義すると最低限データのクローリングができます。SpiderはHTTPのレスポンスのようなものを受け取り次にたどるべきWebサイトと収集対象の収集をします(Scrapyでは収集対象をItemと呼んでいます)、Item Pipelineはデータに前処理やバリデーションをかけて保存する役割とされています。 ScrapyとItem Pipelineが分離されていることで、保存方法と収集方法を粗結合にできるメリットがありそうです。それすら必要なくて、スケジューラと並列ダウンロードなどの機能だけ使いたければ、Spiderに全部処理を書いてしまえば良いと思います。

arch

機能

ダウンローダ

ドキュメントには明示されていないませんが、設定ファイルの説明から推測するに、少なくともつぎの機能が提供されています。   * 並列ダウンロード * IPごと * ドメイン名ごと * 並列ダウロード制限数 * タイムアウト * 同ドメイン or 同IPに対するダウンロード可能のディレイ * 一様分布で設定値の前後50%から

スケジューラー

  • ダウンロード優先度
    • 深いURL優先(DFS)
    • 浅いURL優先(BFS)
  • キューの実装の変更

その他のライブラリ

フレームワーク以外にも、ライブラリ的な立ち位置で使える

  • Link extractor:  Responseからリンクを抽出してくれるもの
  • Item Loader: XPathでHTMLないのデータと構造データとの関係を定義するためのクラス
  • Feed Exports: JSONcsv形式で保存

なども提供されています。

Jupyterを使ってリモート上に手軽にインタラクティブなUIを作る

背景

EC2などリモート上でJupyterがすでに動いている前提です。 Reactなどのフレームワークを使ってGUIを作っても良いのですが、 Jupyterではそれよりも手軽でPythonのみでかけるため手軽にGUIを作るのにおすすめです。

初期設定

初期設定をします。

Jupyterのwidget用のextensionをオンにする。 これがないとwidgetが表示されません。

jupyter nbextension enable --py widgetsnbextension

スクロールをオフにする。(セルを作るたびに実行します)

Cell -> Current Outputs -> Toggle Scrolling

Output領域が狭いと表示されるUIが小さくなるので、Jupyterの幅を広くします。テーマ変更ツールをインストールします。

pip install jupyterthemes

# kernelのバージョンが変わるよう(用調査)
pip install --upgrade ipykernel

jt -t grade3 -fs 95 -altp -tfs 11 -nfs 115 -cellw 88% -T -f roboto -fs 9

ipywidget

ipywidgetを使ってGUIの構築を行います。 ユーザガイドを見れば十分ですが、下記に基本知識をまとめます。

  • ipywidget: widgetが定義されているライブラリ
  • IPython.display: IPythonの表示領域の制御

ipywidget以下にあるWidgetオブジェクトを作成して、 Ipython.display.displayメソッドで表示する流れと、 eventに関数などをsubscribeする方法を知っていればいろいろと作れそうです。

例:簡単なラベル付ツールの作成

データを可視化してアノテーションすることにもJupyterが役立ちます。 例えば、可視化をmatplotlibで実現して、その内容にラベル付をするようなものを作りたいと思います。

画像が表示されて、ボタンを押して次々にラベル付していくようなUIを考えます。とりあえず、次のようなコードでできそうです。

import ipywidgets
from IPython.display import display, clear_output
import functools as ft

class SimpleLabelingUI(object):
    DEFAULT_GRAPH_SIZE = 300
    
    def __init__(self, data_iter, labels, visualizer):
        self.data_iter = data_iter
        self.labels = labels
        self.visualizer = visualizer

        self.btns = []
        for label in self.labels:
            btn = ipywidgets.Button(description=label)
            btn.on_click(ft.partial(self.annotated, label))
            self.btns.append(btn)
        
        self.btn_box = ipywidgets.HBox(self.btns)
        self.max_slider = ipywidgets.IntSlider(self.DEFAULT_GRAPH_SIZE, 0, 600, continuous_update=False)
        self.max_slider.observe(self.graph_size_changed, names='value')
        self.enc = ipywidgets.VBox([self.btn_box, self.max_slider])

        self.current_data = next(data_iter)
        
        self.__draw()

    def graph_size_changed(self, change):
        self.__draw()
        
    def annotated(self, label, b):
        self.current_data = next(self.data_iter)
        self.__draw()

        ## Save annotation here

    def __draw(self):
        clear_output()
        display(self.enc)
        self.visualizer(self.current_data, size=self.max_slider.value)

使い方は、

SimpleLabelingUI(pil_images, ['cute', 'sexy', 'normal'], pil_image_visualizer)

といった感じで使えます。

リモート上でコーディングしやすい環境を整える(Python)

リモート上でコーディングしやすい環境を整える(Python)

背景

MLの分析環境など、リモート環境に大量のデータがあり、すべてをローカルに持ってこれないなど、リモート環境で作業をせざるを得ない状況であるため、楽に開発するための環境を構築します。 (プロダクション環境向けの設定じゃありません。)

基本リポジトリRsyncベースで同期する

ノートブックは別のリポジトリにする想定です。

次のコマンドを実行することで、編集モードでrepositoryをモジュールとしてインストールします。

cd $REPO && pip install -e .

jupyterやipythonでリポジトリ内のモジュールを使って上位のコードを書く。もしくはリポジトリのモジュール自体を作ったり編集したりするのが主な作業である想定です。

次にリモートからローカルに同期させます。 ローカルとリモートの動機にsshfsを使ってもいいですが、ネットワークを切り替えたりするとよく不具合が起きるので、rsyncを使います。 下記のコマンドを実行します。

rsync -Pav -e "ssh -i キー" RemoteHost:~/gitrepos/Repository ~/gitrepos

ソースコードを編集するたびにサーバー側にローカル側を同期させます。

rsync -Pav -e "ssh -i キー" ~/gitrepos RemoteHost:~/gitrepos/Repository

使っているエディタに登録すると良いでしょう。 Visual Studio Codeにはタスクを登録する機能があります。

あと、ローカル側でpip install -e .を実行することを考え、同期ファイル一覧からegg-infoなどの情報を除外します。gitignoreを使って除外できるので、--filter=':- .gitignore'などとすれば良いです。 また、ssh/configにキーを登録して更に便利です。

Jupyterの設定

次に、autoreloadの設定をします。そうすることで、rsyncでリモート側に同期されて変更されたモジュールが自動的にリロードされます。

まずは、IPythonのprofileを設定します。 ここにIPython起動時にロードできるextensionやコードを設定できます。 その後、Python用のkernel.jsonを書き換えて、そのprofileを使ってIPythonを起動するようにします。 jupyter kernelspec listにてPython3用のカーネルのパスを調べ、その中にあるkernel.jsonargs"--profile=default"を追加します。 すると、すべてのノートブックで自動的にモジュールがロードされるようになり、毎回ノートブックの戦闘にリロードの設定を書かなくて良くなります。

まとめ

これでローカルでコードを書いてリモート側に反映することが簡単にできるようになりました。必要に応じて、ipythonやjupyterを使ってコードを効率よく回いけます。

基本的なデータ構造のちょっとした整理

データ構造、一般的な用途、MLとの関係を表にまとめました。

データ構造 一般的な用途 MLとの関係
配列 末尾追加によるデータ追加が主。ランダムアクセスしたい場合 大規模データ(単体PC)
連結リスト 末尾先頭追加によるデータ追加が主。 大規模データ(単体PC)
Red-Black Tree キーによる順序付き連想配列 大規模データ(単体PC)
Hash Table キーによる順序なし連想配列 大規模データ(単体PC)
Heap Tree 優先度つきキュー(取り出し、入れるの計算時間制約が同程度) データ配置アーキテクチャ
B Tree インデックスの管理 大規模データ(単体PC)、データ配置アーキテクチャ

学習データ管理のアーキテクチャを考える場合や、単体PCでMLのモデルを開発していく場合などは、これらのデータ構造を状況に合わせて使い分けられる必要があります。 特に単体PCでモデルを作る状況はインフラに載せる前の実験的な作業でしょうから、 実行速度が試行錯誤の速度に大きな影響を与えるはずで、重要です。

個々のデータ構造のまとめ

  • 配列:末尾追加削除はO(1)。任意の位置のランダムアクセスO(1)。任意の位置の追加削除が遅い。
  • 連結リスト:先頭末尾の追加削除はO(1), 任意の位置のランダムアクセスO(n)、インデックスによる任意の位置削除はO(n)だが、ポインタがあれば任意の位置の削除はO(1)
  • Red-Black Tree: 追加削除検索がO(logn)。最悪時間も。キーによる順序付け
  • Hash Table: 追加削除検索がO(1), 最悪時間はO(n)
  • Heap Tree: 最小要素の取り出しO(logn), 要素の追加削除更新(logn)
  • B Tree: 追加削除検索がO(logn)、底はノードのサイズ。実際のメモリアクセス数はノードサイズが大きいと常に大きくなる。

例えば、Qt5のリストではUIの表示とリスト内容の変化への対応をするために、リスト内容は連結リストで管理されています。それにより、イテレーション速度はO(n)と配列と比べると多くなく、リストのポインタによる要素の削除はO(1)、任意のポインタのあとへの挿入はO(1)となることがわかります。 例えば、要素をクリックするとクリックされた要素が手に入るので、その要素の下に新しい要素を追加するなどといったことができます。

まとめ

データ構造を理解することとMLの関係が少しだけわかりました。

B TreeとML

背景

MongoDBやMySQLではインデックスとしてBツリーが使われています。 インデックスが表形式のデータの高速アクセスの要なので、 大量データを扱う上でMongoDBやMySQLの制約を知る上で理解しておく必要があります。

B treeの基本とアプリケーション

Bツリーの平均計算量と最悪計算量は

  • insert: O(logn)
  • delete, update: O(logn)
  • search: O(logn)

です。オーダー上はRed-Black Treeと同様になりますが、 B Treeはディスクやストレージに格納されてアクセスされる場合にRed Black Treeよりも性能が優位になります。 その理由は今のストレージシステムはある単位でデータを読み出すことで最も性能が引き出せるので、その性質を親和性が高いからです。 例えば、Amazon EBSでは最大IOPSはSSDでは、16KB読み出した場合、HDDの場合は1MB読み出した場合の性能になり、その単位で読み出すことで最大性能が出せます。

B TreeはRed-Black Treeなどの2分探索木とは次の2点で異なります。

  • 子は2つ以上でも良い
  • 一つのノードは複数のキーを持つ

なので、一つのノードのサイズを高速に読める読み出し単位例えばSSDなら、16KBにすることでディスクアクセス回数がかなり減ります。 Red-Black Treeなら、O(logn)で対数の底は2、B Treeは底が約16000になります。 B Treeは読み出し単位に合わせたツリーと言えるでしょう。

ディスクの選択

例えば、AmazonのEBSの中でB Treeインデックスに適したものはEBS Provisioned IOPS SSDです。 このSSDであれば1兆レコードあるインデックスであったとしても、3ブロック読み込めば良いだけなので、約20マイクロ秒でディスクから読み込め、それメモリ上でプラス16000レコードからの二分探索をすれば良いだけでかなり高速にデータをとれます。1兆レコードで整数IDなら数十TBのデータになるので容量的には厳しいかもしれませんが...

とにかく、速度のこと飲みを考えるのであれば、SSDになるでしょう。

基本的な操作

(省略)

まとめ

今後、MLの適用範囲が増えていくに従い、実験にML環境を自前で構築するといった用途も増えてくると思います。その場合に、Bツリーを知っておくことでどういったケースでMySQLやMongoDBが使えて、どういったケースで他の方法を頼らなければならないか想像がつく手助けになると思います。

連想配列とヒープを少し真面目に見る

背景

ヒープや連想配列は汎用性が高いデータ構造です。 少し真面目に見る価値はあると思うので中身を見ていきます。

C++GCCPythonはCPythonを見ていきます。

順序付き連想配列

アルゴリズム

C++のstd::map, std::setはred-black treeで実装されています。 Red-black treeはbinary treeの一種でself-balancingな木とのことです。 ちなみにpythonのdictはinsert順を保存するのみでキーによるソートはされません。

self-balancingの効率と最悪ケースのunbalancingの度合いを下げるようにノードに色をつけることでworst caseでO(logn)の探索、更新、削除なっています。rebalancingもO(logn)で、かなり安定したアルゴリズムと捉えられます。色は二色なのでノード数nでnビットの追加程度で住むとのことです。さらに小さい順、大きい順のtraverseも効率よくできます。

red-black treeでは、根から葉までの最も短い距離と最も長い距離の関係は最短*2<=最長となるようで、その程度の平衡が保たれるようです。

To see why this is guaranteed, it suffices to consider the effect of properties 4 and 5 together. For a red–black tree T, let B be the number of black nodes in property 5. Let the shortest possible path from the root of T to any leaf consist of B black nodes. Longer possible paths may be constructed by inserting red nodes. However, property 4 makes it impossible to insert more than one consecutive red node. Therefore, ignoring any black NIL leaves, the longest possible path consists of 2B nodes, alternating black and red (this is the worst case). Counting the black NIL leaves, the longest possible path consists of 2B-1 nodes.

さっくりまとめると、根から葉までの黒ノードの数は同じでなければならない。となると、赤ノードを追加するしかないが、赤ノードは黒ノードと同数しか追加できないので、最長は最短の二倍以上にはなれない。とのことです。

応用例

このデータ構造であれば、範囲検索が必要な場合もO(logn)程度で住みます。 構築コストは高そうですが、ノードをあとから追加しても順序が保証されたりするメリットはあり、データベースのインデックスとしても使えそうです。MySQLなんかはBツリーですが...

Wikipediaにかかれているものだと、

に使っているようです。 今後、AVL TreeやWAVL Treeとの比較とか詳しく見てもいいかもしれません。

ヒープ

C++priority_queuePythonheapqの実装を見てみます。 heapqもpriority_queueも最も小さい要素の取得がO(1)という実装になっています。 insert, deleteはO(logn)とのことです。キーの更新もO(logn)とのことです。

ヒープツリー

heapqは配列で実装されていて、binary heap treeのようです。 追加のみ、削除更新しない、ランダムアクセス多いと考えると良いチョイスです。

heapの詳細はwikipedia)が詳しいです。binary search treeと比較して、上下関係は保証されるが、横の関係は定義されていなく、最大・最小要素を連続的に取っていくような用途に適しているようです。

応用例

名前の通り優先度つきのキューの実装に使えます。 実装するには安定性のためにtupleではなく、独自クラスを作ったりすれば良くて、 キューの削除や優先度の変更。削除更新はヒープの再構築が必要になるためフラグなどで対応する例が挙げられていました。

確かに他の方法だと、 例えば、配列を常にソートしていて、追加時にbinary searchで追加箇所を探して追加。 最小要素取り出し時は[0]を取り出して削除とかだと。 配列なら追加削除でメモリの移動にO(n), 連結リストで実装すると、追加がO(nlogn), 取り出しがO(1)になる。

追加、取り出し双方O(logn)でバランスが良い。 また、最小値を参照するだけなら、O(1)になり、かなり速いので、 そういったケースに使うのが良いと思います。