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 に関して信頼できる情報源」ということ
Google の PageRank に関する参考書 - 武蔵野日記
今日は理論的な話をするのではなく、単なる参考書についてのポインタ。今週時間取って Google's Pagerank and Beyond: The Science of Search Engine Rankings 作者: Amy N. Langville,Carl D. Meyer出版社/メーカー: Princeton Univ Pr発売日: 2006/07/03メディア: ハードカバー購入: 6人 クリック: 50回この商品を含むブログ (11件) を見る をちゃんと読んでいるのだが、なかなかこの本はよい。そんなに分厚くないのだが、理論的な話と実装の話がバランス取れていて、ときどき入っている小話(中国の検索がどうだとか、Google が株式公開したときの Dutch Auction はどうだとか)もおもしろい。Google's PageRank と書いてはいるが、Kleinberg
Bonanzaのソースが公開された！ - やねうらおブログ(移転しました)
■ Bonanzaのソースが公開された ついにBonanzaのソースが公開された。パラメータを学習させる部分は無いが、思考部はまるごと公開されている。 19回コンピュータ将棋選手権使用可能ライブラリ http://www.computer-shogi.org/library/ ■ Bonanzaのソースの内容は？ 1時間ほどかけてざっとソースを読んでみたが、ソースはCで書かれており(C++ではなく)、C++のtemplateを駆使したGPS将棋のソースとは対照的。GPS将棋のソースに比べれば格段に読みやすく、かつ、素人くさい。率直かつ正直に言わせてもらえれば、GPS将棋のソースのほうが何倍も参考になる。 ただ、Bonanzaのソースの ・どんな評価因子を採用しているのか ・ビット演算のテクニック は注目に値すると思う。あとは、GPS将棋に比べてソースが簡素なので将棋プログラムの思考部の書き
ニコニコ動画の大規模なデータに対するタグ付けとリンク解析 - 武蔵野日記
ニコニコ動画データ分析研究発表会というのが開催されていたようだ。 タイトルや説明文はノイジーなので、動画につけられたタグを使うと割ときれいなデータとして可視化したりできる、という話は、はてなブックマークの関連エントリー機能のときも聞いたような話で、基本的にはインターネットユーザに無料でデータのタグ付けをしてもらっている、という話なんだろうな、と思う。以前紹介したRion Snow の論文 (彼は2005年に Microsoft Research でインターンし、2006年に Powerset (現在は Microsoft に買収済み)、2007年には Google でインターンした人物。ACL という自然言語処理のトップカンファレンスで2006年にベストペーパー受賞)で、 今年の Rion Snow のトークは、Amazon Mechanical Turkというシステムを使って、非常に安価
K-means法によるクラスタリングのスマートな初期値選択を行うK-means++ - kaisehのブログ
K-means法は、入力データからK個のランダムな個体を初期クラスタの中心として選択し、以降、クラスタの重心を移動させるステップを繰り返すことでクラスタリングを行う非階層的手法です。K-means法はシンプルで高速ですが、初期値依存が大きいのが弱点で、不適切な初期値選択をすると間違った解に収束してしまいます。 以下は、Introduction to Information Retrievalの16章に出てくる例です。 {d1, d2, ..., d6}をK=2でクラスタリングする場合、{{d1, d2, d4, d5}, {d3, d6}}が大域最適解ですが、初期クラスタの中心をd2, d5で与えると、{{d1, d2, d3}, {d4, d5, d6}}という誤った解に収束してしまいます。 この問題を改善するK-means++という手法を見つけたので、試してみました。 K-means+
GoogleNewsのレコメンドの中身 - UMEko Branding
先日、全体ゼミで発表したときの内容ですが、ここにまとめときます。。GoogleNewsのレコメンドの中身を追った論文の要約です。少し前の全体ゼミで用いた資料です。ソース：Abhinandan Das,Mayur Datar,Ashutosh Garg,Shyam Rajaram,"Google News Personalization: Scalable OnlineCollaborative Filtering",WWW2007不勉強な個所が多々ありますので、誤っている箇所等ありましたら、是非ご指摘ください。 個人的には、最近のモデルベースの手法の勉強・おさらいという意味で用いているので、GoogleNews独自の拡張なり実装の部分の内容が省かれている場合があります。また、データ構造やMapReduceを用いた計算の仕組みの部分は、ここでは省略しています。。一応、 全体像 ・LSH(Lo
情報検索ことはじめ〜教科書編〜 - シリコンの谷のゾンビ
2011-01-18追記 教科書編その2 にて2011年版のIR教科書を紹介しています 情報検索(IR)の勉強を本格的に始めて8ヶ月．大体どんな分野があって，どんなことを勉強すればいいのかわかってきた（と思う）．この気持ちを忘れないうちにメモしておこう．以下，若輩があーだこーだ言ってるだけなので，間違いや他に情報があれば，ぜひコメントをお願いします． # ここで述べている情報検索とは，コンピュータサイエンスの一分野としての情報検索です．図書館情報学の側面は一切扱っていません，あしからず． というわけでまず教科書編． 本腰を入れて勉強する場合，基礎づくりのためには教科書選びがいちばん重要だと思っている．自分の知っている限り，情報検索における教科書の選択肢はそれほど広くはない．以下に紹介する本は，情報検索を学ぶ上で「買い」の本．これらを読めば，最新の論文を読めるだけの土台はできるし，専門家と議
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
具体例で学ぶ！情報可視化のテクニック 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
GT Nitro: カーレーシング・ドラッグレーシングゲーム - Google Play のアプリ
GT Nitro: Car Game Drag Raceは、典型的なカーゲームではありません。これはスピード、パワー、スキル全開のカーレースゲームです。ブレーキは忘れて、これはドラッグレース、ベイビー！古典的なクラシックから未来的なビーストまで、最もクールで速い車とカーレースできます。スティックシフトをマスターし、ニトロを賢く使って競争を打ち破る必要があります。このカーレースゲームはそのリアルな物理学と素晴らしいグラフィックスであなたの心を爆発させます。これまでプレイしたことのないようなものです。 GT Nitroは、リフレックスとタイミングを試すカーレースゲームです。正しい瞬間にギアをシフトし、ガスを思い切り踏む必要があります。また、大物たちと競いつつ、車のチューニングとアップグレードも行わなければなりません。世界中で最高のドライバーと車とカーレースに挑むことになり、ドラッグレースの王冠
【人力検索】圧縮されたデータを高速に検索するアルゴリズム【類似検索】 ふと気になったので、調べ物をお願いします。…
【人力検索】圧縮されたデータを高速に検索するアルゴリズム【類似検索】 ふと気になったので、調べ物をお願いします。 圧縮されたデータを対象に検索を行うアルゴリズムで 下記のようなもので、目ぼしい成果を上げているものを探してください。 （人力検索としては、次の類似を検索する形になります。） [PPT] 高速検索可能なテキスト圧縮法に関する研究 （復号処理を行わずに高速に検索を行う圧縮法の研究） www.tkl.iis.u-tokyo.ac.jp/~otsuka/profile/kenkyu3.ppt くどく補足しますが、「検索インデックスを圧縮することにより高速に検索が行えるようになりました」という種類のものを紹介する回答は不要です。 「gzipで圧縮されたファイルを、自動的に解凍して検索できます」という類のソフトの紹介も不要です。 上に挙げたものそのものも不要です。 ※ 探すのは難しいかもし
Visual C++の勉強部屋
理工系、特に電気系、の学生と技術者を対象としたVisual C++の解説を行います。Visual C++を始めたいが、よく分からないという人は、これを参考にしてください。ただし、初めてプログラムを学ぶ全くの初心者向けではありません。 本資料の一部のJava版が（株）翔泳社のウエブサイトＣｏｄｅＺｉｎｅにありますので、こちらもご利用ください（Java版とある場所をクリックして下さい）。Visual C++ 6.0版（現在は全部削除）が最初に公開され、そのJava版がCodeZineに寄稿され、その後に現在のVisual C++ 2005 Express Edition版が作成されています。 Java版は、すべてアプレットになっていますので、ブラウザから試してみることができます（Javaランタイム必要）。 Visual C++ 2008 Express Editionが無償でダウンロード
ARToolKitの解析 その① 変換行列の計算 - Pipe Render
安定化の次は、プログラムの高速化などをやってみようと思ってましたが、 高速化のためには、ARToolKitのソースをもっと理解していなければなりません。 そこで、次に「ARToolKitの解析」を行うことにしました。 解析のその１は、変換行列の計算アルゴリズムの解説をやってみます。 ここでいう変換行列とは、マーカー（オブジェクト）座標系から、グローバル（カメラ）座標系へ変換する行列のことです。 これは、ARToolKitの重要な仕組みの１つです。 ---- < 変換行列計算の概要 > ---- BGM：エコテロニカ（sansuiさん） OpenGLなどの３DCGでは、３Dモデルの移動・回転などを行うために、座標系の変換行列を用います。 ARToolKitの場合も、この変換行列がないと、マーカー上にモデルを表示できません。 プログラムでは、スクリーン上に映ったマーカーの画像から、この変換行列
LZ法再び - DO++
可逆データ圧縮としてはgzipやlha, pngなどダントツで使われているLZ法（Lemple Ziv法）ですが、他のデータ圧縮法（BWT法、PPM法、CM法）に比べ圧縮率が低いということで研究の対象としてはあまり注目をあびていませんでした。ところが次の論文で真面目にやれば圧縮率は非常に高くなる可能性があり、BWT法とかそれを超える可能性があることが示されています。。 "On the bit-complexity of Lempel-Ziv compression", SODA 2009, P. Ferragina, et. al. [pdf] まず、LZ法についておさらいですが、基本的にはデータを前から順番に見ていったときに、既に出現した文字列がもう一度出現（マッチング）したら、その文字列を前回出現した（相対）位置と長さのペア(pos, len)で置き換えることで圧縮する方法です。データ
Diary of DQ1-PASSWORD.
DQ1 復活の呪文解析日記 [ Back to DQ-Password Room ] [ Top ] ●日記の一覧 【1998/05/31】最後のフラグ 【1998/02/07】戦士の指輪 【1997/07/27】マジックナンバー 【1997/07/25】完成！！かな？ 【1997/07/22】チェックコード 【1997/07/20】各データ 【1997/07/19】名前 【1997/07/18】勇者「００００」 【1997/07/13】勇者「あああ＊」 【1997/07/12】差分の見方 【1997/07/11】120 bit 【1997/07/10】勇者「ああああ」 【1997/07/09】コード表 【1997/07/08】その２ 【1997/06/08】DQ1 の復活の呪文解析 注意書き しばらく前までは某ページにて DQ1 の復活の呪文が作成できました。 現在では残念ながら、そのペ
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
Perl で Range Coder - naoyaのはてなダイアリー
練習がてら、圧縮符号化の手法のひとつである Range Coder を Perl で実装してみました。 http://github.com/naoya/perl-algorithm-rangecoder/tree/master Range Coder は算術符号を実数ではなく整数で実現した手法です。高速な算術圧縮を実現する「Range Coder」 (1/2)：CodeZine（コードジン） に詳しい解説があります。今回の実装も、この記事にあるソースコードを参考に実装しました。参考、というか結局ほとんど移植に近くなってしまいました。 インタフェースは以下のようになっています。入力文字列における各記号の出現頻度、累積出現頻度をあらかじめ算出して RangeCoder オブジェクトにセットしてから、encode することで圧縮結果が得られます。(出現頻度表をバイナリに添加する実装は行っていませ
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
著名ソーシャルメディアが使っているアルゴリズムを大公開！ | Moz - SEOとインバウンドマーケティングの実践情報
“アルゴリズム”は、もっとも非人間的なものの代表だともいえる。ソーシャルメディアにとって、そのアルゴリズムが不可欠だというのは、実に皮肉めいている。 僕はこの間、グーグルがどうやってユーザーデータを集めているかについて書いた記事を掲載した（前編、後編）。今回は、著名なソーシャルメディアサイトが、ユーザーデータを活用する上でどのようにアルゴリズムを用いているのか、白日の下にさらそう。 ソーシャルメディアを成り立たせているのは人間の力だが、ユーザーが入力したデータを利用できる状態にする仕組みは、アルゴリズムによって作られている。現在活動している無数のソーシャルメディアサイトで実証済みのことだが、ユーザーの関与とアルゴリズムによる処理ルールの上手いバランスを見出すことは、とても難しくなりがちだ。これから紹介するアルゴリズムは、悪意のないユーザーと結びついて初めてうまくいくものだ。 人気ソーシャル
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Kademlia
