推論システムにおける「妥当性」という概念

研究

最近では，推論システム関係の文献をよく参照するので，論理学関係の言葉の使い分けがシビアになってきました．
特に，無矛盾性，妥当性，健全性，完全性といった概念は，推論システムに求められる要件であるため，正確に把握しておく必要があります．

妥当性

妥当性とは，システム内で行われる推論そのものが妥当であることをいいます．妥当であるとは，登場する命題の真理値がどんなものでも推論が成立するということです．
妥当な推論と妥当でない推論の例は以下のとおりです．

妥当な推論 ((p=>q) and (q=>r)) => (p=>r)
妥当でない推論 (p or q) => q

前者の場合，p, q, r の真理値の組み合わせが何であっても，推論が成立します．一方で，後者の場合は，p=True, q=False という条件で矛盾が発生します（True => False という推論が行われるため）．

このように，推論の妥当性を検証するには，反例の存在を調べれば良いことが分かります．これをアルゴリズムに落とし込んだものがタブロー法です．タブロー法ではあらかじめ推論が成立しないと仮定した上で，いかなる条件でも矛盾が発生することを場合分けによって確かめます．矛盾が発生しない場合は，それが反例になります．

タブロー法については，こちらの文献が詳しいので参考にしてください．

タブローの方法による論理学入門

タブローの方法による論理学入門

社会ネットワーク分析の用語について

読書記録

安田雪著『実践ネットワーク分析』(2001)を読みました。Evernote にメモした用語だけブログにまとめます。

ソシオマトリクス
人間をノード，紐帯をエッジと見立てたネットワークの隣接行列
ブロック・モデル
サブネットワークを一つのノードにまとめたようなモデル．社会ネットワークを俯瞰的に把握するために使われる．

  • イメージ行列：行列を要素に持つ行列．コミュニティのネットワークなど
  • 縮約：ノードをまとめること．

非対称データ
ソシオ・マトリクスが対称行列にならないようなデータ(注：Twitterのフォロー関係は非対称データ，mixiのマイミク関係は対象データ)．研究内容によっては，適宜対称化を行う必要がある．

  • 対称化：有向グラフを無向グラフに写像する操作．「双方向のもの以外はエッジとして認めない」「片方向のものもエッジとして認める」「平均値を取る」などのポリシーが存在する．

弱い紐帯
接触頻度・接触期間・連鎖の長さなどから，ネットワークにおいて関係が薄いと判断されるような人間関係のこと．グラノベッターによる論文「弱い紐帯の力」「転職」によって，人間は転職などの意思決定において，強い紐帯よりも弱い紐帯による情報を信頼して行動するとされる．
中心性
権力や構成人物との関わりの多さなど，その人物がネットワークにおいてどの程度中心的な役割を担っているかという指標．測地線に基づく「ボーチャムの近接性」や，固有ベクトルに基づく「ボナチッチ中心性」など．
媒介性
その人が，ネットワークにおいて，どの程度の関係を媒介しているかという指標．「すべてのノードのペアにおいて，その人を通る測地線の数」などの計算方法がある
測地線
グラフ上で，二つのノードを結ぶ最短経路．
構造同値
社会ネットワークにおいて，ラベルを付け替えても変化しないような人間同士の間に成立する関係(注：顧客に対するサービス・プロバイダーの集合など)．構造同値な関係下にある人間は，社会においてアイデンティティを獲得しようとするため，競争が発生するとされる．

  • 第三者戦略：競争が起こっている二社間に介入し，利益を得る戦略．

PRML第4章メモ

http://d.hatena.ne.jp/alembert/20090726/p1 の続きです。

4.3 確率的識別モデル

  • 確率的生成モデル＝入力変数のモデル , 確率的識別モデル＝出力変数のモデル
  • ロジスティック回帰
    • 活性化関数としてロジスティックシグモイド関数 σ(a) を利用
    • 尤度が指数型分布族の場合に適用可能
    • 誤差関数 : E(w) = -Σ(t ln y + (1-t)ln(1-y))
    • 誤差関数の勾配 : ∇E(w) = Σ(yn - tn)φn
      • 目標値と予測値の誤差×基底関数ベクトル
      • 線形基底関数モデルと一緒というのが興味深いね、という話（cf. 正準連結関数）
    • 誤差関数のヘッセ行列 : ∇∇E(w) = ΦTRΦ（R = diag{yn(1-yn)} = cov[t]）
    • 最尤推定
      • 過学習の結果は直感通り、w=∞、ヘヴィサイドステップ関数によってクラスが分類される
      • 解析的には困難 -> IRLS（反復重み付け最小二乗）
  • プロビット回帰
  • 正準連結関数
    • 連結関数（活性化関数の逆関数）の一種
    • 指数型分布族の場合、これを連結関数として採用すると、誤差関数の勾配＝目標値と予測値の誤差×基底関数ベクトル になる
      • 非常にシンプル。そして汎用性が高い。（IRLS の際に便利）

4.5 ベイズロジスティック回帰

  • ロジスティック回帰をベイズ的に取り扱いたい => 解析的には無理 => ラプラス近似をしよう！←ｲﾏｺｺ
  • 基本的には式の展開・近似の繰り返し。解析学の基礎知識で何とかなる。
  • トリッキーな変数変換があったのでメモ。よく使われる手法なのか？
    • ∫f(ax) g(x) dx = ∫(∫δ(y-ax) f(y) dy) g(x) dx = ∫∫δ(y-ax) f(y) g(x) dy dx = ∫f(y) (∫δ(y-ax) g(x) dx)dy = ∫f(y) u(y) dy　（ただし δ: ディラックデルタ）

PRML 読書会で発表します。

今回も発表します。参加はこちらからよろしくどうぞ : C.M.ビショップ「パターン認識と機械学習(PRML)」読書会（第５回） : ATND

パターン認識と機械学習 上 - ベイズ理論による統計的予測

パターン認識と機械学習 上 - ベイズ理論による統計的予測

二大短縮 URL サービス（bit.ly, TinyURL）の API 仕様

Twitter の短縮 URL サービスと言えば、bit.ly, TinyURL がその軒を連ねていますが、この圧倒的なシェアは、Twitter の統計データからも伺うことができます。

http://www.nikkeibp.co.jp/article/column/20090729/170760/?P=2

Twitter上で使用されている短縮URLの実に82.0％がbit.lyによるものだった。逆にTinyURLのシェアは11.0％に過ぎない。

これらの短縮 URL サービスの API の仕様を調べてみました。

bit.ly

こちらにリファレンスがあります : Google Code Archive - Long-term storage for Google Code Project Hosting.

  • 入力の形式は GET。出力の形式は xml, json から選べる
  • 主なメソッド
    • shorten : URL を短縮
      • 短縮URLの実体は、URL だけでなく、「URL と短縮したユーザ（or NULL）のタプル」になっているようで、これで複数同じ実体を持った短縮 URL を生成することを防いでいるようです。
    • expand : URL を展開
    • info : ページの情報（短縮した人、サムネイル、等）
    • stats : ページの統計（クリック数）
  • Javascript のコールバックは使用可（callback という GET パラメータで指定可能）

TinyURL

公式のドキュメント見つけられず。こちらを参考にしました : TinyURL の api を使う - モノラルログ

今日知った Twitter 関連サービス 3 つ

Twitter

add a tweet

screenshot

今見ているページに対して Twitter 上でどんな post がされているのか確認できる Firefox アドオン。この手のサービスは実は前からあったのですが、アドオンという形をしている点が新しいですね。
via : ウェブページごとにTwitterの発言を残せるアドオン「add a tweet」*二十歳街道まっしぐら（FC2ブログ時代）

GeoChirp

screenshot

地理的な位置と範囲を指定して、つぶやきの検索ができる検索エンジン。あくまで憶測ですが、つぶやくから独自に位置を抽出しているのではなく、恐らく Twitterの API の仕様をまんま使っているだけな気がするので、技術的に特に新しくはなさそう。Twitter の Search API の仕様に geocode というパラメータがあるのですが、これを使うと地理的な位置と範囲でつぶやきを絞り込めるようになります。

http://apiwiki.twitter.com/Twitter-Search-API-Method%3A-search

  • geocode: Optional. Returns tweets by users located within a given radius of the given latitude/longitude, where the user's location is taken from their Twitter profile. The parameter value is specified by "latitide,longitude,radius", where radius units must be specified as either "mi" (miles) or "km" (kilometers). Note that you cannot use the near operator via the API to geocode arbitrary locations; however you can use this geocode parameter to search near geocodes directly.

実装が容易でパッと見目新しいサービスが構築できることから、今後は、この仕様を使った B 級ウェブサービスが増えていくのではないかと推測しています。

via : ウェブページごとにTwitterの発言を残せるアドオン「add a tweet」*二十歳街道まっしぐら（FC2ブログ時代）

TwitterCounter

screenshot

自分のフォロワー数の推移を確認できるサイト。他のユーザと比較することもできるので、「あいつはいつ頃俺を追い抜いたんだろう」なんてときに効果を発揮してくれるかもしれません。

via : Twitterのフォロワーの統計データをグラフ化してくれる「TwitterCounter」

Ubuntu で Cake が使える環境を構築するまで

研究室の先輩に勧められて、Twitter のクローラ用に Ubuntu を使ってみることにしました。予想以上にユーザフレンドリーな OS で、パッケージ管理の整備のされ具合にただただ感動していました。Screen も最初から幾つかテーマが用意されているので、快適に作業が始められます。


PHP の O/Rマッパーを新しく覚えるのが面倒だったので、Cake を使おうと思い、Ubuntu に環境を整えてみました。以下、作業手順メモ

パッケージのインストール

私が入れたパッケージは以下の通りです。apt-get install でドバっと入れました。

  • apache2-mpm-prefork（prefork を使いました）
  • php5
  • libapache2-mod-php5
  • mysql-server-5.1
  • phpmyadmin
  • cake
  • bake

mod_rewrite を ON に

8/2 変更。こちらの方法の方がよりスマートでした（@repeatedly さんに感謝）

a2enmod rewrite

これで、あとは /var/www あたりに /usr/share/cake/app/* をコピーすれば良いと思います。



動いた！

参考URL