Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（２） - llameradaの日記
GoogleのFellowであるJeffrey Dean氏のWSDM'09における講演"Challenges in Building Large-Scale Information Retrieval Systems"のスライドの翻訳の第2回です。Googleの検索システムの10年間の進化の軌跡が紹介されており、今回は2000年から2001年ぐらいまでの検索システムの一部の紹介となっています。個人的には転置インデックスの詳細な符号化方式が公開されているのが印象に残りました。Googleにとっては過去のインデックス構造でしょうが、商用の全文検索エンジンの詳細な仕様が公開されるのは珍しい気がします。なお、イタリック体で一部解説・感想をいれています。翻訳は素人なので詳しくは元の資料を参照してください。 第1回：Google WSDM'09講演翻訳：大規模な情報検索システム構築における課題（１）
画像符号化
画像の符号化 （Image Coding） １． はじめに ここでは、画像を圧縮する符号化方式の概要について紹介します。 画像信号の情報量は極めて多く、伝送や蓄積を効率的に行うため、これらを圧縮する技術が用いられています。 これらの技術を、符号化（Image Coding）と言います。 この符号化では、方式の互換性を保証するための標準化が重要です。 たとえば、JPEG方式やMPEG方式は、ISO等の機関が中心となって、標準化作業が行われています。 なお、厳密には「符号化」は次の２つに分類されます。 (1) 情報を圧縮する情報源符号化 （Source Coding） (2) ネットワークや伝送路の特性に合わせて、変調や誤り訂正等を行う通信路符号化 （Channel Coding） ここでは、(1)の情報源符号化について解説します。（以下単に、「符号化」と呼ぶことにします。） なお、画像符号化
[B! algorithm] urza358のブックマーク
こんにちは。今回は、GeminiとClaude 4という2つのAIアシスタントだけを使って、正規表現ライブラリを一から作成した体験をお話しします。 きっかけ：古い理論への興味 驚異的な開発速度：正味数時間で完成 AIアシスタントによる開発プロセス 役割分担の自然な発生 AIによるコード生成の質 学術論文レベルの理論整備 Abstract（概要）の自動生成 先行研究との詳細比較 理論的基盤の文献調査 完成したライブラリの機能 基本機能 高度な機能 AIアシストの革新的側面 1. 理論の現代的解釈 2. 包括的なテスト設計 3. ドキュメント作成の自動化 4. 段階的な機能拡張 開発体験から見えたAIの可能性 驚いたこと 課題として見えたこと 将来への示唆 研究開発の加速 教育への応用 産業応用の可能性 まとめ We are hiring! きっかけ：古い理論への興味 事の始まりは、1964年
[B! Algorithm] agwのブックマーク
このコーナーでは、2014年から先端テクノロジーの研究を論文単位で記事にしているWebメディア「Seamless」（シームレス）を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。 X： ＠shiropen2 米国マサチューセッツ工科大学（MIT）のライアン・ウィリアムズ教授が発表した論文「Simulating Time With Square-Root Space」は、コンピュータが計算処理を行う際の「時間」と「空間」の関係性について、従来の理論を大幅に改善するという研究報告（査読前のプレプリント）である。速く計算するには多くのメモリが必要という50年来の常識を覆す可能性を示す。 計算機科学で「時間」とはコンピュータが実行する処理ステップの数を意味し、「空間」とは計算に必要なメモリ使用量を指す。 約50年前の1970年代、チューリングマシンが時間tを要する
The Anatomy of a Search Engine
Computer Science Department, Stanford University, Stanford, CA 94305 In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at leas
初代Googleのアルゴリズム解説 - GIGAZINE
いまやネットの世界を左右する強力な検索エンジンとなったGoogle。日本ではまだYahoo！の方がはるかに利用者が多いのでさほどではないですが、アルゴリズムの基本的な考えが似ているため、同じような結果が出てきます。つまり、既存の検索エンジンのその基礎となった一番最初のGoogleの検索アルゴリズムを理解すれば、検索エンジン対策にも役立つはず。 ということで、初代Googleのアルゴリズムをできるだけわかりやすく解説してみます。既存の他サイトの解説とは違い、きちんとした最初のGoogleの数式に基づいています。 詳細は以下から。The Anatomy of a Search Engine http://www-db.stanford.edu/~backrub/google.html Googleの画期的なランク付けの方法が数式による全自動のページランクというのは聞いたことがあると思いますが、
コンピュータ将棋協会blog
諸事情により、コンピュータ将棋協会blogを、この記事が表示されているURLから新しいURLへと移転いたしました。 今後、トップページは 旧: http://www.computer-shogi.org/blog/ から 新: http://blog.computer-shogi.org に変更されます。 当ブログをチェックされている皆様には、お手数ですが、ブックマーク等を上記の新URLに変更していただきますようお願いいたします。今後、新たな記事はすべて新URL側に追加されます。 こちらの移転前のブログは当面残す予定ですが、今後更新されることはありません。一定期間経過後、閉鎖される予定です。 移転後も引き続き、コンピュータ将棋協会blogをよろしくお願いいたします。
モンテカルロ囲碁は必ず半目勝ちを目指す - 武蔵野日記
コンピュータ囲碁の世界でモンテカルロ法という確率的な手法が成功を収めていることは前も書いたが、今号の情報処理学会誌に「プロ棋士対コンピュータ:FIT2008における囲碁対局報告」と題して村松正和さんが記事を書かれており、最近の様子が(棋譜付きで)書かれているのでおもしろかった。 結論から言うとプロ棋士(4段)に8子置いて勝った(実力的にはアマ2-3段程度)というけっこうすごい話で、自分ではもう平手では勝てないところまで来てしまったのかなぁ、という感じ(自分はアマ2級くらいだった)。ここで使われた Crazy Stone というプログラムは第1回 UEC 杯コンピュータ囲碁大会(2007年12月開催)で優勝したプログラムである。 モンテカルロ囲碁の特徴について同記事でいくつか書かれている(pp.70-71)ので引用すると、 Crazy Stone も含め，モンテカルロ囲碁の打ち方には非常に特
モンテカルロ法 - Wikipedia
モンテカルロ法（モンテカルロほう、（英: Monte Carlo method、MC）とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。 計算理論の分野において、モンテカルロ法とは誤答する確率の上界が与えられる乱択アルゴリズム（ランダム・アルゴリズム）と定義される[1]。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。一般にモンテカルロ法は独立な乱択を用いて繰り
Schwartzian transform - Wikipedia
This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2024) (Learn how and when to remove this message) In computer programming, the Schwartzian transform is a technique used to improve the efficiency of sorting a list of items. This idiom[1] is appropriate for
線形合同法 - Wikipedia
線形合同法（せんけいごうどうほう、英: Linear congruential generators, LCGs）とは、擬似乱数列の生成式の一つ。 漸化式 によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B≥0である。 上の式で、が、乱数の種であり、これに数を代入すると、が得られる。さらにを生成する場合には、を使う。以後、同様に行う。 例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種=8とすると、（上の式においてはXn+1を左辺に置いたが、今回は便宜上、右辺に置く） 次に乱数を生成する際は前回生成された乱数（今回は3）を使って、 以下、同じように、 となる。 生成される乱数列は周期性を持ち、上の例では8→3→1→8→3→……、を繰り返す。この周期は最大でMであり、以下の条件が満たされたときに最大周期Mをもつ。 BとMが互いに素である。 A-1が、Mの持つ全ての素因
[P2P]位置情報を数値1つで表す手法「Z-ordering」 - Tomo’s HotLine
IT技術を中心に、暮らしに役立つ情報からクラシック音楽の解説まで気軽に情報発信しています。 WEBサイトはhttp://toremoro21.world.coocan.jp/ Twitterは@toremoro21です。 □はじめに ＤＨＴやＳｋｉｐｇｒａｐｈなどの技術が注目されるとともに、位置情報をP2Pで扱いたいという要望がでてきている。だがＤＨＴやＳｋｉｐｇｒａｐｈは1次元の数値で各ノードが扱う情報範囲を扱うため、位置情報など多次元の情報を扱うのには、当初は向いてないと見られていた。しかしあるテクニックを使うとそれは一発で解消する。それがZ-orderingである。なお、このZ-orderingは位置情報を扱えるP2PミドルウェアPIAXでも採用されている。 □簡単な例 多次元を1次元で表すにはどうすればよいのだろうか？まずここで一例を挙げてみる。 例えば、2次元空間においてｘ＝｛１
![[P2P]位置情報を数値1つで表す手法「Z-ordering」 - Tomo’s HotLine](https://cdn-ak-scissors.b.st-hatena.com/image/square/b4e38426fa9529bdb687a0c8ea1406a0f5bee683/height=288;version=1;width=512/http%3A%2F%2Ftoremoro.tea-nifty.com%2F.shared-cocolog%2Fnifty_managed%2Fimages%2Fweb%2Fogp%2Fdefault.png)
最近傍探索 - Wikipedia
最近傍探索（英: Nearest neighbor search, NNS）は、距離空間における最も近い点を探す最適化問題の一種、あるいはその解法。近接探索（英: proximity search）、類似探索（英: similarity search）、最近点探索（英: closest point search）などとも呼ぶ。問題はすなわち、距離空間 M における点の集合 S があり、クエリ点 q ∈ M があるとき、S の中で q に最も近い点を探す、という問題である。多くの場合、M には d次元のユークリッド空間が採用され、距離はユークリッド距離かマンハッタン距離で測定される。低次元の場合と高次元の場合で異なるアルゴリズムがとられる。 ドナルド・クヌースは、The Art of Computer Programming Vol.3（1973年）で、これを郵便局の問題で表した。これはすな
zuzara.com » ブログの記事本文を抽出するスクリプトをつくってみた
ブログ検索において、RSSは必ずしも記事全文を配信していないので、クローラーが記事のURLにアクセスし記事の本文を取得するケースが多いようです。 「gooブログ検索」「ブログレンジャー」開発者が語るブログ検索技術Yahoo!検索 スタッフブログ Yahoo!ブログ検索より細部改善のお知らせ上記の記事ではどちらも本文を抽出してくる、とあっさり書かれていますが100%に近い精度を実現するとなるとそう簡単ではないはず。 ちょっと調べてみたら以下のような取り組みが論文として読めました。英語圏の文献は、検索語が悪かったのかいまいち。「blog entry extract body text etc…」 NRI 技術創発 ブログ記事の自動分類により消費者意識の側面を捉える試み（PDF）なんでもRSS! HTML文書からのRSS Feed 自動生成 南野朋之 奥村学：人工知能学会研究会資料 SIG-SW
Webstemmer（クローラーツール）
日本語サイトでは、具体的な性能は測定していませんが、 以下のようなサイトで正しく動くことがわかっています: アサヒ・コム Nikkei NET Mainichi INTERACTIVE Yomiuri On-line IT media 東京新聞 日刊スポーツ 信濃毎日新聞 livedoor ニュース 使いかた Webstemmer をつかったテキスト抽出は以下のようなステップになります: まず、特定のニュースサイトから種となる HTML ページを多数取得する。 取得したページのレイアウトを学習する。 別の日に、同一のニュースサイトから新しい HTML ページを取得する。 2. で学習した結果をつかって、新しい HTML ページから本文を抽出する。 1. および 2. のステップが必要なのは最初の 1回だけです。 ひとたびサイトのレイアウトを学習してしまえば、 あとはレイアウトが大きく変更さ
MOONGIFT: » タイトル・本文抽出クローラー「Webstemmer」:オープンソースを毎日紹介
これはやばい！凄すぎる。 現在進めようと思っているプロジェクトでは、サイト上の本文抽出が重要な技術になっていた。だが、それを一から開発していたのではあまりに時間がかかってしまう。さらに重要な技術ではあるが、それが売りと言う訳ではなかった。 そこで見つけたのがこのソフトウェアだ。まさに理想的な方法かも知れない。 今回紹介するオープンソース・ソフトウェアはWebstemmer、タイトル・本文抽出クローラーだ。 WebstemmerはPythonで作られたクローラーで、Webクローラー/レイアウト分析/テキスト抽出/URL DB操作/簡易的なテキスト抽出の5つの機能が提供されている。 動作原理については公式サイトを参考にして欲しいが、個人的にも考えていた（考えていただけ）方法に近い。学習時間が長いのが難点だが、複数台のPCで分散化できれば問題なくなるだろう。 特徴的なのは、特定の言語に左右される
Webstemmer のしくみ
back [English] 基本的な原理 レイアウト分析ツール analyze.py 本文を抽出する extract.py パターンファイルの構造 おわりに 基本的な原理 Webstemmer では、以下のような仮定をもとにして Web ページを分析しています。 すべての記事には共通した (たかだか数種類の) レイアウトが使われている。 各ページにはメインとなる文章がひとつ含まれている。 (従って、この原理は日記や掲示板などのサイトには使えません) 記事の文章は毎日変わっても、そのレイアウトは変わらない。 バナー広告やナビゲーションの HTML タグは同一レイアウトのページで不変。 Webstemmer はこの仮定をもとに、 あるニュースサイトの同一レイアウトをもつページをまとめ、 それらのページ中で「変化していない部分」をさがします。 バナーやナビゲーション用のリンクなどはレイアウトが
英語に苦心 大人なVOCALOID「巡音ルカ」ができるまで
「初音ミク」「鏡音リン・レン」に続いて1月30日に発売された、音声合成ソフト「キャラクター・ボーカルシリーズ」第3弾の「巡音ルカ」は、VOCALOID初の日本語・英語バイリンガルで、シリーズ初の「成人」だ。 ミクが16歳、リン・レンが14歳だったのに対して、ルカは20歳という設定。声も大人びている。「お酒やたばこもOKの年齢。ディスコ、ナイトクラブといった、ミクやリン・レンでセーブされていた夜の大人の曲も作ってもらえれば」と、開発したクリプトン・フューチャー・メディアの佐々木渉さんは期待する。 イメージは、アジアのエキゾチックな歌姫。ルカの歌を英語で聴いてくれるであろう欧米のユーザーに受け入れてもらえるよう、ミステリアスなキャラクターを目指した。 カタカナ英語の限界を打破したかった ルカの構想を始めたのは、「初音ミク」考案前の2007年初旬。ヤマハが「VOCALOID2」を発表した直後で、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
コンピュータ囲碁におけるモンテカルロ法 ~理論編~ 美添一樹
RubyForge: ExtractContent: Project Info