情報科学と人工知能のノート

初等的な知識から最新論文の解説まで色々集めていきます.備忘録兼用.

有向グラフの強連結成分分解

ナイーブなアルゴリズム ある頂点 からグラフ探索(深さ優先探索など.なんでもよい)を始めて訪れることができた頂点の集合 と,グラフの全ての辺を逆向きにしてから からグラフ探索を始めて訪れることのができた頂点の集合 に対し, によって誘導される部…

主成分分析ってたぶんこういうもの

例によってさも分かってるかのように説明していますので間違ってたら教えてください。 たたき台 以下のように四次元の点が 10 個並んだ表があったとします。 > round(a, 3) [,1] [,2] [,3] [,4] [1,] -0.043 0.026 -0.005 -0.013 [2,] -1.314 0.785 -0.150 -…

R と MATLAB の実行時間計測

乗り換えを検討するために R と MATLAB で単純な処理の実行時間を計測してみました。なお、以下の実験ではそもそもソフトウェアを動かしているマシンが違います。 自宅PC の R と大学PC の MATLAB と自分にとってどっちが都合がいいかを計っただけです(どこ…

R 備忘録 2013/05/11

今日は短めです。 ベクトルの要素のうち条件を満たすもののインデクスを集める ということが which 関数を使うと実現できます。 > a > a [1] 1 4 7 10 13 16 19 22 25 28 > which(a %% 2 == 0) # 偶数 [1] 2 4 6 8 10 > which(max(a) == a) [1] 10 この whic…

R 備忘録 2013/05/10-3

中心極限定理をシミュレーション 平均 、分散 の分布に従う独立した 個の確率変数 について と定義する。 が大きいとき、 は平均 、分散 の正規分布に従う。 とのことです。つまり をたくさん作ってヒストグラムを作ったら正規分布の密度関数の曲線が現れる…

R 備忘録 2013/05/10-2

ちなみに、「意味がわかる 統計解析」の流れに沿って、書いてあることが R で実行できるように R の機能を勉強しています。 確率分布 R には確率分布 DIST ごとに(DICT の累積分布関数を F(x)、確率密度関数を f(x) とおくと) dDIST(x):f(x) の値を返す。…

R 備忘録 2013/05/10

データを視覚化する方法について、軽くまとめ。 とりあえずベクトルの値を並べる plot 関数を使うとベクトルの要素をインデクス順にプロットすることができます。 > plot(c(1:5, 5:1)) ちなみにうちの環境では出力はこのようになりました。 グラフを画像に保…

R のデータ構造

とりあえず現状の理解をまとめます。 属性 R オブジェクトには属性というものを割り当てることができます。 そして、全てのオブジェクトは少なくとも mode と length の二つの本質的属性を持っています。 いくつかの属性の値は専用の関数で調べることができ…

R 備忘録 2013/05/09

データフレームの作り方(要素直打ち) > # 人間の性別と身長と体重が並んだ個表データを作る。 > # 値は適当です。 > sex > height > weight > people > people SEX HEIGHT WEIGHT 1 F 154 48 2 F 145 40 3 M 170 50 4 F 167 52 5 M 180 80 6 M 165 75 7 F …

R 備忘録 2013/05/08

言語の仕様なんてあんまり書きたくないのですが(細かいし、つまらないし、そのうち変わったり消え去ったりするし)どっかに書いとかないと忘れるのでしょうがない。 データ構造 僕の理解です。間違ってたらごめんなさい。 ベクトル := 1次元配列 行列 :…

モデルの良さを調べなくてよいのか

相変わらず統計学を勉強中です。 間違ってたら突っ込んでください。世の中には統計手法や機械学習に関する入門書・記事が山ほどありますが、ニューラルネットワークやサポートベクトルマシンなどといったそれぞれのモデルに対して、「モデルのパラメータはこ…

引き続き統計を勉強中

引き続き統計学について勉強しています。 今回も数学関連の書籍を紹介。 もう少し色々理解したら、かなり重要なのにネットに証明が全く無いような定理について解説を書こうと思います。 統計科学の基礎(白石高章 著) 前回紹介した「意味がわかる統計解析」…

標本の要素は確率変数

統計学の基礎に関する本を何冊か読みました。 統計に限った話ではないかもしれませんが、いい本と悪い本の差が激しいです。 今日はいい本を二冊紹介します。 まずはこの一冊から 意味がわかる統計解析(涌井貞美 著) 読んだ中で入門書として一番お勧めなの…

人工知能と離散と連続と統計

アクセス数の推移からして定期的にこのブログを購読されている方はいらっしゃらないとは思いますが(虚空に向かって)お久しぶりです。 一週間前くらいまでは凄く忙しくて、それから今日まではプレGWとしてだらだらしてました。 記事書くのは82日ぶりだ…

タブロー法の謎の木

本日は大学の修論研究発表会でした.何故タブロー法は変な木を生成するだけで充足可能性判定ができるんだろうかとずっと疑問に思っていたのですが、あの木は(与えられた論理式が充足可能なときは)論理式を充足するあるモデルそのものなんだそうです.様相…

Minty 1960 の定理 3.1

Korte と Vygen の「組み合わせ最適化」を読んでいたら、突然以下のような補題が出てきました(以下は第二版 23 ページからの引用). 補題 2.6 (Minty [1960]) を有向グラフとし, とする. は黒で彩色され,残りの各辺は赤,黒あるいは緑のいずれかで彩色…

雑記2013/02/06

広告つぶしにコメント.最近忙しいです.今度、IJCAI 2011 に出てた Civilization 関連の論文でも読んでみようかなぁと思っています.

ボロノイ図

距離空間とその中の複数個の点(母点、seed などと呼ばれます)が与えられたときに、空間上の各点が与えられたどの点に最も近いかを分類した図をボロノイ図といいます. 与えられた距離空間を 、与えられた点を とおいて数式で書くと 点 に対応する領域は と…

リアリティを考慮した都市地区自動配置アルゴリズム

この記事では Procedural City Layout Generation Based on Urban Land Use Models (Groenewegen, et al., EUROGRAPHICS 2009) という論文の都市地区自動配置アルゴリズムを紹介します. 最近、ゲームに関する自動化技術を勉強したり考えたりしているのです…

おねえさんの栞

いっときほどほどに流行ったおねえさんの動画の栞をいただきました.知り合いが関係者です. ぽぽぽぽーんとか選挙とかと同種の流行り方だったと思うのですが*1、大ブームに至らなかったのは、キャラクターの固有名称も不思議な歌も無かったからかなと推測し…

深さ優先探索

深さ優先探索はグラフを探索するためのアルゴリズムです*1.注意書きの通り、細かいことを言うと面倒なのですが、以下ではグラフ上の二頂点間の連結性を判定するアルゴリズムだと思って説明を進めましょう. 定義 入力:グラフ 、始点 、終点 . 出力: と …

Chu-Liu/Edmonds のアルゴリズム

有向最小全域木問題を解くアルゴリズム.1965 年に Chu と Liu が提案し、それとは独立に Edmonds が 1967 年に提案したらしいです. 定義 入力:グラフ 、コスト関数 、根 . 解: を根とした有向全域木.すなわち から全ての頂点への経路が存在する有向木 …

最小全域木問題

最小木問題、あるいはカタカナ英語で最小スパニング木問題、最小スパニングツリー問題とも. 例 ある電力会社が全国に電気を送り届けるべく、日本中に電線を張り巡らせようと考えています.発電所と接続されていない家が無いようにもれなく電線を張り巡らせ…

ベルマン-フォード法

最短経路問題を解くアルゴリズム.ベルマンとフォードが共著の論文で一つのアルゴリズムを提案したわけじゃないようなのですが、なんでベルマン-フォード法って呼ぶのでしょうね?*1 定義 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への…

ダイクストラ法

グラフ上の最短経路問題を解くアルゴリズム.エドガー・ダイクストラが 1959 年出版の論文で提案. 入出力 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への経路.すなわち、次を満たす頂点の列 (ただし ). 、 、 任意の について . 解…

グラフ理論における最短経路問題

あるいは最短経路探索問題. 定義 入力:グラフ 、コスト関数 、始点 、終点 . 解:始点から終点への経路.すなわち、次を満たす頂点と辺の列 (ただし ). 、 、 任意の について . 解のコスト:経路に含まれる各辺のコストの和. 出力:コスト最小の解.…