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 ベースでインストールできるサードパーティーの

データ検証などで利用するMerkle Treeのメモ

データの検証などで利用される Merkle tree/マークル木/hash tree/ハッシュ木についてメモ。 Merkle Tree の概要 wikipedia の概要をそのままコピペ。 暗号理論および計算機科学において、ハッシュ木(Hash tree, ハッシュツリー)またはマークル木(Merkle tree)とは、より大きなデータ（例えばファイル）の要約結果を格納する木構造の一種であり、データの検証を行う際に使用される。このデータ構造はハッシュリストとハッシュチェインの組み合わせでできており、ハッシュ法の延長上にある手法といえる。 Merkle tree の利用例 merkle tree が2つ与えられた時に、ルートノードから子ノードに向かってハッシュ値をたどっていけば、どこが壊れているのか特定が簡単で、壊れている部分木だけを更新すればよい。 Amazon dynamo/cassandra/riak はレプリカ間の同期(anti-entorpy)に Merkle tree を使っている。 別の例として、AWS Glacier のマルチパートアップロードは マルチパートアップロード開始時にブロックサイドを指定 マルチパートアップロード時に各ブロックのデータとハッシュ値と位置(アーカイブのXバイト-Yバイト目)を指定 マルチパートアップロード終了時にアーカイブ全体のファイルサイズと Merkle tree のルートハッシュ値を指定 するAPIになっている。 サーバ側は、分割アップロードされた各ブロックを位置順に並び直し、Merkle tree のルートハッシュ値を求め、クライアントがマルチパート終了時に送信したチェックサムと突き合わせている。 ハッシュ値を実際に計算してみる Merkle Tree の理解を深めるため wikipedia の記事で使われてる例を元に 実際に Merkle Tree のハッシュを計算してみる。 処理の流れは以下 データをブロックサイズで分割 各ブロックのハッシュ値を求め、葉ノードとする 親ノードは各子ノードのハッシュ値を連結した文字列のハッシュ値とする 根ノードに辿り着くまでこの操作を繰り返す。 データを分割 ハッシュ値を求めるファイル(サイズは

AWS REST リクエストの署名についてメモ

AWS の REST API のリクエストでは署名(signature)を使って、API のセキュリティチェックを行っている。 サービス開始時に Version 1(いまは使われていない) が公開されたあと、2, 3, 4 という合計4種類が存在する。 この署名の仕様をメモ。 version 1 最も古い Version 1 というような PARAM=VALUE がずらずらと並んだ GET リクエストを考える。 STEP1 パラメーターを大文字/小文字を無視して辞書順にソート。 このリクエストから version1 で署名する文字列を以下のルールで生成。 クエリーストリングの先頭の ? を削除 クエリーストリングを大文字/小文字を無視して辞書順にソート &name=value 形式の & と = を削除 ※ name=value 形式の name と value は % エンコードしない より具体的には というようになっている。 この文字列を canonical string と呼ぶ。 この文字列を署名する。

近似文字列アルゴリズムのgestalt pattern machingについてメモ

Google 検索でタイポをすると、意図したであろう綴りを教えてくれたり、意図通りの検索結果を返してくれる。   このスペルチェック機能では、入力文字列が本来の文字列とどのくらい似ているのかを評価するアルゴリズムが肝で、編集距離のアルゴリズムはよくしられている。 ふとしたことから、Ratcliff/Obershelp pattern recognition(gestalt pattern maching ともいう) という編集距離とは別のアルゴリズムに出くわした。 このアルゴリズムは1980年代から存在するが、より利便性の良いアルゴリズムが発明されていったからなのか、wikipedia に載っていないくて、手元のアルゴリズム本にもみあたらない。 まだこのアルゴリズムが輝いていた 1988 年に、 Dr. Dobb’s Journal に発表された次の記事(サンプル実装はアセンブリ言語!)を元にこのアルゴリズムをメモ。 John W. Ratcliff and David Metzener, Pattern Matching: The Gestalt Approach, Dr. Dobb’s Journal, page 46, July 1988. http://www.drdobbs.com/database/pattern-matching-the-gestalt-approach/184407970 gestalt の意味 記事の冒頭で gestalt の意味が説明されている。 Gestalt is a word that describes how people can recognize a

ansible-vault の暗号処理について調べた

ansible ではパスワードなど重要な情報を保全するために、ファイル単位で暗号化する ansible-vault というコマンドがある。 この暗号方式について調べたのでメモ。 3行でまとめると Entrypt-then-MAC(EtM)の認証付き暗号 ファイルの対称暗号方式は AES-CTR MAC は HMAC-SHA256 暗号処理の流れ 0. 前提 インプットとしては 暗号化するファイル ユーザーが入力したパスワード がある 1. salt の生成 /dev/urandom で salt を生成 2. 暗号鍵 の生成 salt パスワード をもとに、 PBKDF2 を使って暗号鍵を生成(ラウンド数は 10000, PRF は HMAC-SHA256) この鍵を、 key1 key2 IV(nonce) に分割 3. ファイルデータの暗号 key1 IV(をもとにした counter) ファイルデータ(plain text) を元に AES-CTR で暗号化(cipher text) 4.

呼損率を求めたい

呼損率とは 通信回線の世界では呼損率(こそんりつ)という考え方がある。 ユーザーが電話サービスおよびISDNサービスを利用する時に，ビジーで利用できない率。呼がなんらかの理由（話中など）で拒絶されてサービスを受けることができない割合を指す。 http://itpro.nikkeibp.co.jp/word/page/10007943/ Erlang B formula を使うと呼損率を求めることができる。 wikipedia の Erlang (unit) に丁寧にまとめられているので、読めば一般の人が知りたいであろうことはわかる。 Erlang(単位)の定義 Erlang B formula には単位の Erlang が出てくるので、まずはこの定儀から。 λ:単位時間あたりの呼び出し件数 h:を1件あたりの処理時間 とした時に E = λh と定儀する。 例) 1時間あたり200回の呼び出し(200 call/hour)、1件あたり0.1時間(0.1 hour/call) かかるとすると E = 200 * 0.1 = 20(erlang) となる。 Erlang B formula の定義 早速覚えた単位 Erlang を使うと、ビジーだった時にリトライしない(loss system)という前提のもとで、次の式(Erlang B formula)で呼損率 を求めることができる。 ここで m は並列処理数。 この式は、漸化式を使っても定義できることが知られている。

exponential backoffのメモ

exponential backoffとは? データ送信処理が失敗して再送信するときに、失敗回数が増えるに連れて再送信するまでの待ち時間を指数関数的に増やす仕組みを exponential backoff という。 有名な例としては Carrier sense multiple access with collision detection (CSMA/CD) や Carrier sense multiple access with collision avoidance(CSMA/CA) といった通信方式で、失敗回数 N に対して、[0, 2^N-1] からランダムな数を選び、その slot time 分だけ待って再送信するようになっている。 ランダムに選んでいるのは、複数の通信が同じタイミングで失敗した時に、また同じタイミングで再送されないようにするため。 また、失敗回数が一定値を超え場合に、待ち時間に上限を設けているものを truncated exponential backoff と呼ぶ。例えば、失敗回数 N が 10 以上を超えると truncate する場合、失敗回数が 10 でも 16 でも [0, 2^10 – 1] = [0, 1023] の間から選ぶ。16回目だからといって [0,