Blog Archives

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.]) 制約の不等式を等式標準形に直します。

Tagged with: ,
Posted in algorithm, python

情報検索の評価についてメモ(適合率,再現率,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

Tagged with: , , ,
Posted in algorithm, nlp

類似係数(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 などとも呼ばれます。

Posted in algorithm, nlp, Uncategorized

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

Tagged with: ,
Posted in algorithm, nlp, Uncategorized

データ検証などで利用する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

Tagged with: , ,
Posted in algorithm

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

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

Tagged with: , , , , ,
Posted in algorithm, aws

近似文字列アルゴリズムの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

Tagged with: , , ,
Posted in algorithm
Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 7 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 7 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 7 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 1 year ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago