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

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

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

Tagged with: ,
Posted in python, web

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

Tagged with: , , , ,
Posted in linux

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 を共有します。 ディレクトリが存在しない

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