HITS, 主成分分析, SVD - naoyaのはてなダイアリー
ウェブグラフのリンク解析によるページの評価と言えば PageRank が著名ですが、もうひとつ Jon Kleinberg による HITS (Hyperlink-induced topic search)も有名です。最初の論文 Authoritative Sources in a Hyperlinked Environment は 1999年です。IIR の 21章で、この PageRank と HITS についての解説がありました。 HITS HITS はウェブページの評価に二つの軸を用います。一つが authority スコア、もう一つが hub スコアです。 例えば「Perl の情報が欲しい」という検索要求に対しては CPAN や 開発者である Larry Wall のホームページなどが重要度の高いページかと思います。これらのページは「Perl に関して信頼できる情報源」ということ
Latent Semantic Indexing - naoyaのはてなダイアリー
情報検索におけるベクトル空間モデルでは、文書をベクトルとみなして線形空間でそれを扱います。この文書ベクトルは、文書に含まれる単語の出現頻度などを成分に取ります。結果、以下のような単語文書行列 (term document matrix) が得られます。 d1 d2 d3 d4 Apple 3 0 0 0 Linux 0 1 0 1 MacOSX 2 0 0 0 Perl 0 1 0 0 Ruby 0 1 0 3 この単語文書行列に対して内積による類似度などの計算を行って、情報要求に適合する文書を探すのがベクトル空間モデルによる検索モデルです。 見ての通り、単語文書行列の次元数は索引語の総数です。文書が増えれば増えるほど次元は増加する傾向にあります。例えば索引語が100万語あって検索対象の文書が 1,000万件あると、100万次元 * 1,000万という大きさの行列を扱うことになりますが、単
non-Negative Matrix Factorization (NMF) - naoyaのはてなダイアリー
以前に Latent Semantic Indexing (LSI) や HITS 絡みで SVD や主成分分析について少し書きました。 http://d.hatena.ne.jp/naoya/20090212/latent_semantic_indexing http://d.hatena.ne.jp/naoya/20090301/hits LSI では SVD を使って単語文書行列を分解し、低階数近似を行います。これにより、似たような次元をまとめたりといった効果が得られるのでした。自分の考察では HITS も同様のことを行っているという認識でした。 さて、集合知プログラミングを読んでいたら、第10章で "non-Negative Matrix Factorization" (非負値行列因子分解, 以下NMF) という手法が出てきました。NMF も SVD や主成分分析に同じく行列を分解
BigQuery と Google の Big Data Stack 2.0 - naoyaのはてなダイアリー
先日、有志で集まって「BigQuery Analytics」という書籍の読書会をやった。その名の通り Google BigQuery について書かれた洋書。 BigQuery を最近仕事で使い始めたのだが、BigQuery が開発された背景とかアーキテクチャーとかあまり調べもせずに使い始めたので今更ながらその辺のインプットを増やして以降と思った次第。 それで、読書会の第1回目は書籍の中でも Overview に相当するところを中心に読み合わせていった。それだけでもなかなかに面白かったので少しブログにでも書いてみようかなと思う。 BigQuery の話そのものも面白いが、個人的には Google のインフラが書籍『Google を支える技術』で解説されたものが "Big Data Stack 1.0" だとして、BigQuery は Big Data Stack 2.0 の上に構築されており
Linux の close は fsync 相当を調べる - naoyaのはてなダイアリー
Linuxのcloseは暗にfsyncするから、ここであげられている 100000回繰り返し open 8K write close というパターンだとfsyncコストが見えちゃうので良くないんじゃないかな とのことで、そうなのか! と思ったので例によって深追いしてみました。 まず fsync(2) の実装は fs/sync.c にあります。 asmlinkage long sys_fsync(unsigned int fd) { return __do_fsync(fd, 0); } static long __do_fsync(unsigned int fd, int datasync) { struct file *file; int ret = -EBADF; file = fget(fd); if (file) { ret = do_fsync(file, datasync);
γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー
通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。 Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビット
naoyaのはてなダイアリー - さくらインターネット移行記#1
先日のライブドアのテクノロジーセミナー(http://d.hatena.ne.jp/naoya/20061214/1166063145)でも少し触れたのですが、はてなのサーバーは今後さくらインターネットのiDCでホストすることになりました。 複数の iDC を検討しましたが、最終的にさくらインターネットに決めた理由は回線品質の高さと回線が低価格である点でした。 はてなのようなコミュニティ中心のサービスは、お金の面では、どうしても回線コストと収益の間にアンバランスが生じがちです。ショッピングサイトや各種メディアのようなコンテンツに比べてマネタイズが難しい、というのがその主な理由です。 例えばはてなのトラフィックの多くははてなダイアリーの日記へのアクセスで占められていますが、基本的に個人の日記にははてな側からは広告を掲載しないポリシーでいます。そのためトラフィックを多数必要とされる箇所で収益を
Chef Solo の Environments - naoyaのはてなダイアリー
今年3月に入門Chef Soloを書いた時点では、Chef Solo は Environments の機能をサポートしてなかったため解説は省略しました。 その後、Chef はバージョン 11.6.0 (現在は 11.8.2) で Chef Solo での Environments をサポートし、入門Chef Solo で推薦している knife-solo も 10月末にリリースされた 0.4.0 から Environments をサポートしました。というわけで、現状 Chef と knife-solo が最新版であれば Environments を利用することができます。 たまたま今手をつけている仕事で Environments のことを調べたので備忘録的に記しておきます。 Environments とは Chef の Environments は、例えば development や pr
Linux のプロセスが Copy on Write で共有しているメモリのサイズを調べる
Linux は fork で子プロセスを作成した場合、親の仮想メモリ空間の内容を子へコピーする必要があります。しかしまともに全空間をコピーしていたのでは fork のコストが高くなってしまいますし、子が親と同じようなプロセスとして動作し続ける場合は、内容の重複したページが多数できてしまい、効率がよくありません。 そこで、Linux の仮想メモリは、メモリ空間を舐めてコピーするのではなく、はじめは親子でメモリ領域を共有しておいて、書き込みがあった時点で、その書き込みのあったページだけを親子で個別に持つという仕組みでこの問題を回避します。Copy-On-Write (CoW) と呼ばれる戦略です。共有メモリページは、親子それぞれの仮想メモリ空間を同一の物理メモリにマッピングすることで実現されます。より詳しくは コピーオンライト - Wikipedia などを参照してください。 この CoW に
Vagrant + Chef Solo + serverspec + Jenkins でサーバー構築を CI - naoyaのはてなダイアリー
Jenkins おじさんと戯れること半日、うまくいったので備忘録を残しておく。 やりたかったのは Chef で構築したサーバーを Jenkins で CI する、というもの。このときサーバーはテストが終わる度に破棄して、テスト開始時に再度真っ新な状態から立ち上げたい。(こういうサーバーを壊して作ってというテストはなんという名前で呼ばれるのだろう?) 仮想サーバーを破棄/作成をプログラマブルにやるのはもちろん Vagrant プロビジョニングは Chef Chef の環境を整えるのに knife-solo 0.3.0.pre3 テストは serverspec コードは Github に上げる (https://github.com/naoya/jenkins-vagrant-test) CI は Jenkins という構成になっている。ひとまず Jenkins や Vagrant はローカル
Titanium - JavaScript で iPhone/Android アプリを作る - naoyaのはてなダイアリー
Titanium Mobile は JavaScript で iPhone/Android のアプリ (not Webアプリ) を開発できる開発環境。詳しくは Titaniumで始めるモバイルアプリ作成の基礎知識 (1/3)：Web技術でネイティブアプリを作れるTitanium（2） - ＠IT などに解説があります。 少し時間があったので、JavaScript で作るというのがどんな感じか試してみました。作ったアプリは こんな感じで TableView があり、選択すると WebView でアプリ内ブラウザが立ち上がる、ブラウザはツールバーで「戻る」や「リロード」が可能。あとはタブコントロールがあったり･･･という単純なもの。初期起動画面のサイトリストは、HTTP でローカルに立てたサーバーから JSON で読み込んでいます。 Web上のドキュメントを見ながら2, 3時間試行錯誤で一応の
prototype.js でデザインパターン - Bridge
結城さんのデザパタMLでも紹介されてしまった手前、さぼるわけにもいくまい、ということで「機能の階層と実装の階層を分ける」 Bridge パターンです。 使いどころはたくさんありそうでなさそうでありそうな(どっちだ)、個人的には結構好きなパターンです。プログラムを拡張するには、クラスを追加するわけですが、あらかじめ「機能」を追加するのか、「実装」を追加するのかという視点で二つの階層に分けて実装しておくことで、拡張しやすい構成にしましょうというパターンです。 +-------------+ |Hello, Japan.| +-------------+ +-------------+ |Hello, World.| +-------------+ +----------------+ |Hello, Universe.| +----------------+こんな感じの出力を作りたい場合、まず
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
