SciPyで線形計画問題を解く

Pythonの数値計算ライブラリ SciPy には線形計画問題を解くための scipy.optimize.linprog という関数が存在します。 この関数を使って、線形計画問題を実際にといてみます。 例として次のような線形計画問題を考えましょう maximize subject to 目的関数の右辺に -1 をかけて、目的関数の最大化を目的関数の最小化に変えます。 minimize これを行列で表します。 あとは、行列をリストで表現し、SciPyプログラム(linear-prog.py)に落とします。 実行します。 linprog関数の引数で {“disp”: True} にしていると のブロックのメッセージが表示されます。 “Optimization terminated successfully.” というメッセージからわかるように、問題は無事とけました。 出力結果をもう少し詳しく見てみましょう。 status: 0 最適化の終了ステータスです。 最適解を見つけられると 0 になります。 指定されたイテレーション内にとけないなど、とけなかった時は1以上の値になります。 slack: array([ 0., 0., 4.]) 制約の不等式を等式標準形に直します。 subject to 目的関数が最小値を取るとき、このスラック変数 x_3, x_4, x_5 はそれぞれ 0, 0, 4 の値を取ります。 fun: -18.0 目的関数の最小値です。 x:

情報検索の評価についてメモ(適合率,再現率,F値)

あるモデルによって情報を分類した時に、どのくらいうまく分類しているのか評価するためのメトリクスについてメモ。 テーマを単純にするために、文書から関連する文書を探すような情報検索システムを考える。したがって、関連する・関連しないの二値分類。 適合率(precision) 探した文書に含まれる関連文書の割合。 どれだけ正確に関連文書を探せているかを判定。 再現率(recall) 関連文書をどこまで探し出せているか。 網羅性を判定。 F値(F-score, F-measure, F_1 score) 適合率と再現率はトレードオフの関係にあるため、調和平均してバランスを見るのがF値 例 関連するドキュメントは relevant の頭文字をとって R、関連しないドキュメントは nonrelevant の頭文字をとって N で表すことにする。 3個だけ関連文書があるとする。 R R N R N N N N N N 例1)極端な例として、システムがすべての文書を関連すると判断した場合 正解 R R N R N N N N N N 検索 1 1 1 1 1 1 1 1 1

類似係数(Jaccard/Simpson/Dice)をPythonで求める

語が2つ与えられた時に、どのくらい似ているのか計量評価したいといった目的のために類似指数というのが存在します。 今回は、よく知られていて、かつ、実装の簡単な Jaccard 係数 Simpson 係数 Dice 係数 を Python で実装します。 これら3つの係数は、0から1までの値を取り、1に近づくほど類似し、0に近づくほど類似していないことを表します。 Jaccard 係数 Jaccard index, Jaccard similarity coefficient などとも呼ばれます。 次の式で表されます。 xとYが完全一致 の場合に1となります。 Simpson 係数 overlap coefficient, Szymkiewicz-Simpson coefficient などとも呼ばれます。 次の式で表されます。 XとYが完全一致 XがYの部分集合(またはその逆) の場合に1となります。 Dice 係数 Dice’s coefficient/Sørensen-Dice coefficient などとも呼ばれます。 次の式で表されます。 xとYが完全一致 の場合に1となります。 三角不等式を満たさないため、 計算してみる night nacht nuit の3語に対して、各組み合わせの類似係数を求めてみましょう。 実行してみると、次のような結果となりました。 その他 今回は類似指数を「語」を対象にしましたが、2つのベクトル間の類似性を求めるなど、広い意味での類似性の抽出に利用出来ます。 関連リンク https://en.wikipedia.org/wiki/String_metric https://en.wikipedia.org/wiki/Jaccard_index

MARISA-TrieをコマンドラインとPythonから使う

概要 Matching Algorithm with Recursively Implemented StorAge (MARISA) という Trie に対する高い空間効率とそれなりの時間効率を実現するデータ構造があります。 動的な更新には対応していませんが 辞書引き（Lookup） : 入力文字列が登録されているかどうかを確認 逆引き（Reverse Lookup） : 入力された ID から登録文字列を復元 Common Prefix Search : 入力文字列の前半部分に一致する登録文字列を検索 Predictive Search : 入力文字列で始まる登録文字列を検索 といった操作が可能です。 今回は marisa-trie 0.2.4 をベースに コマンドラインプログラム Python バインディング から MARISA を触ってみます。  Install MARISA 環境は Amazon Linux とします。 まずはC++のプログラムビルドに必要なツール群をインストールします。 次に C++ プログラムのよくある手順でインストールします。 最後に Python バインディングをインストールします。 marisa-trie には SWIG ベースのバインディングもありますが、今回は pip ベースでインストールできるサードパーティーの

tornadoでWebSocketサーバを動かしてみる

Tornado で HTTP サーバを用意 HTML ファイルの JS が WebSocket サーバと通信 ブラウザでこの HTML ファイルを表示。 WebSocket クライアントが WebSocket サーバにメッセージを送信すると、HTML が書き換わる というようなシナリオを実現するシンプルなデモを作ってみました。 WebSocket Server サーバには表題の通り Python Tornado を利用します。 パッケージのインストール Tornado のビルドには Python のヘッダーファイルが必要です。 以下は RedHat 系でのインストール例です。 コード クラス Tornado.websocket.WebSocketHandler を継承して WebSocket サーバを実装します。 WebSocket サーバがメッセージを受け取ると、 on_messege ハンドラーが呼びだされます。 HTML/JS ファイル WebSocket 用の JavaScript は HTML ファイル内にベタッと書きます。 WebSocket クライアント送信されたメッセージは の箇所に反映されます。 WebSocket

real time/user CPU time/system CPU timeの違いをメモ

time(1) コマンドの出力内容 Linux で time(1) コマンドを実行すると、real time/user CPU time/system CPU timeが出力されます。 わかるような、わからないようなこの出力される時間の意味についてメモします。 各フィールドについて Real time について どの処理に時間がかかっているかはさておき、プログラムの開始から終了までを計測した時間 wall clock timeや wall time と呼ばれることもある。 User CPU time について プログラムがユーザースペースで CPU が利用された時間 ライブラリコードの実行などがここに含まれます System CPU timeについて プログラムがカーネススペースで CPU が利用された時間 システムコール(例えば disk I/O で使う read/write)の実行などがここに含まれます。 User/System CPU time が増えないケース ネットワークを介するプログラムは、通信の待ちが長いため、 CPU time を合算しても Real time よりはるかに少ない事が多いです。 sleep 処理も

Ubuntu14.04でNFSv4を動かしてみる

ゴール nfs-server nfs-client というホスト名の Ubuntu 14.04 のサーバを2台用意し、nfs-server サーバに Network File System バージョン 4(以下 NFSv4) を構築、nfs-client サーバからマウントしてみる。 NFSv4 サーバを構築 まずは nfs-server に NFSv4 サーバを構築します。 必要なパッケージのインストール NFS サーバに必要な nfs-kernel-server パッケージをインストールします。 nfs-kernel-server は NFSv3 にも対応しているようですが、今回は NFSv4 として利用します。 共有ディレクトリを作成 次に共有ディレクトリを作成します。 今回は /tmp/no_root_squash /tmp/root_squash /etc を共有します。 ディレクトリが存在しない /tmp 以下のディレクトリを作成します。 共有ディレクトリを bind mount する NFSv3 では export するディレクトリごとに export していましたが、NFSv4 では擬似的に 1 ディレクトリにまとめ(pseudo

AWS CLIにオレオレwaitコマンドを追加する

aws cliには API 呼び出し後、特定のステータスになるまでポーリングする wait コマンドがあります。 例えば ec2 インスタンスを起動する API を呼び出し後、インスタンスの起動が完了するまで待つには $ aws ec2 wait instance-running –instance-ids xxx のようにします。 この wait 機能が実装されるまでは というように、ポーリング処理を自前で実装しなければいけ ませんでした(例外処理も真面目にやるとさらにごちゃごちゃする)。 この wait 系コマンドを独自追加する方法をメモ。 cloudformationでスタック構築完了を待つ 例として cloudformation でスタックの作成APIをたたいたあと (crete-stack)、スタックの構築が完了するまでポーリングするコマンド $ aws cloudformation wait stack-completed を実装してみましょう。 AWS CLI で wait を使わず cloudformation のスタックを構築 wait を使わずに cloudformation のスタックを構築するには $ aws cloudformation create-stack –stack [STACKNAME] でスタックの作製命令をし $

bashでコマンドライン引数にファイルの中身を渡す

標準出力先としてファイル名を指定するのではなく、ファイルの中身(body)を引数として渡すにはどうすればよいのか? 実験用スクリプト 確認のため、次の簡易的なシェルスクリプトで各コマンドライン引数を表示させる。 入力ファイルとしては次のように改行やスペースを含んだ JSON ファイルを渡す 実行コマンド 結果論としては、以下のように printf と cat をコンボすればよい 解説 ポイントとなるのは次の箇所 ここを単純に $(cat test.json) や bash 方言のショートカットである $(< test.json) とすると、改行・スペースを引数の区切りとしてみなされてしまう この問題を回避するために、ファイルの中身全体を1文字列として扱うために printf ‘%s’ でラップさせるというわけ。 Reference linux – command line arguments from a file content – Stack Overflow http://stackoverflow.com/questions/4227994/command-line-arguments-from-a-file-content

HTTP ベンチマークツール wrk についてメモ

モダンな HTTP ベンチマークツール wkr の簡単な使い方についてメモ。 wrk の特徴は以下。 C で書かれている マルチコア CPU を 活かした高負荷をかけられる スレッドと epoll/kqueue のイベントドリブンを活用して負荷をスケールさせる(NOTICE ファイルを読むと Redis Event Library(ae event loop) を拝借しているようです) Lua スクリプトで HTTP クライアントの処理や実行結果のレポートをカスタマイズできる Installing wrk in CentOS 6 まずはビルドに必要なパッケージをインストールします。 openssl-devel をインストールしていないと、make 時に以下のようなエラーが発生します。 次にソースコードから wrk をビルドします。 Usage 上の例では 12 スレッド(-t12) 同時 400 コネクション(-c400) 負荷は 30 秒かける(-d30s) リクエストヘッダー “User-Agent: MyBrowser” を送信(-H”User-Agent: MyBrowser”) 通信は5秒でタイムアウト(–timeout 5)