遺伝的アルゴリズム - Wikipedia
遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。 遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。 この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。 必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることであ
人工知能基本問題研究会(SIG-FPAI)での岡野原さんの発表のときに取ったメモ - yasuhisa's blog
hillbig.cocolog-nifty.com ということで僕が取ったメモも出してみようと思う。内容としては大体3つで オンライン学習 L1正則化 索引を用いた効率化, 全ての部分文字列を利用した文書分類 という感じだったんだけど、最後の索引の付近はid:syou6162の勉強不足によりよく分からなかった。が、最初の二つはなんとか付いていけたので、出してみます。主に自分用のメモですが。 オンライン学習自然言語処理のデータは3つの特徴がある。 高次元 疎 冗長 で、あとはデータがばかでかいので、いわゆるバッチ処理だとメモリに乗り切らなかったりとかということがある。それでオンライン学習というのが今よく使われているようだ。オンライン学習の方法には下のような方法がある。簡単なものから難しいものへ。 perceptron 自然言語処理と相性がよい 色んなもののベースになる 線形分離できるときには
大規模データを基にした自然言語処理 - DO++
人工知能基本問題研究会 (SIG-FPAI)でタイトルの題目で一時間ほど話してきました。 発表資料 [pptx] [pdf] 話した内容は - 自然言語処理における特徴ベクトルの作り方と、性質 - オンライン学習, Perceptron, Passive Agressive (PA), Confidence Weighted Learning (CW) 確率的勾配降下法 (SGD) - L1正則化, FOLOS - 索引を用いた効率化, 全ての部分文字列を利用した文書分類 で、スライドで70枚ぐらい。今までの発表とかぶっていないのはPA CW SGD FOLOSあたりでしょうか オンライン学習、L1正則化の話がメインになっていて、その両方の最終形の 確率的勾配降下法 + FOLOSの組み合わせは任意の損失関数に対してL1/L2正則化をかけながらオンライン学習をとても簡単にできるという一昔前
【人工知能】物理エンジンで人工生命つくって学習させた
運動学習させました。この仮想生物が試行錯誤をして動き方を学習しました。この動画はマルチエージェント進化シミュレータのanlifeを開発していたときに作りました。2020/10/4 追記この後作ったゾンビを宮崎駿監督にみていただいたところが2016年にNHKで放送され一部話題になりました。2016年超会議での超人工生命の生放送企画を経て、ドワンゴにて新たな人工生命を開発することに→ リリース後半年でサービスクローズ人工生命を作る会社を立ち上げました→ https://attructure.com/
ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog（ブログ）
こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。 当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。 で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。 特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。 ウィキペディア日本語版の解説
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる
Yahoo! ウェブ検索 API で単語同士の近さを総当たりで調べる 2009-02-26-2 [Programming][YahooHacks] あらかじめ用意された単語セットがあり、それぞれの単語同士の近さを検索ヒット数とそれによるシンプソン係数で求める手順について。 使用している Web API の提供が終了となったため、現在動作しません。ご了承ください。 Yahoo!デベロッパーネットワーク (YDN) のウェブ検索 API を用いる。 - Yahoo!デベロッパーネットワーク http://developer.yahoo.co.jp/ - Yahoo!デベロッパーネットワーク - 検索 - ウェブ検索 http://developer.yahoo.co.jp/webapi/search/websearch/v1/websearch.html ロジック やってることは、下記で書かれ
リアルとWebのネットワーク分析:先端研ブログ
先端研レポート第一弾は、2月にヤフー社内で開催された安田雪先生のセミナーのレポートをお届けします。 人脈づくりの科学 ： 関係構造の不思議 - リアルとWebのネットワーク分析 講演者：安田雪（やすだ ゆき） GBRC社会ネットワーク研究所所長 概要： 現実の人間関係と、Web上にみられる人間関係は、表裏一体である。現実社会では観察できない関係構造がWebから可視化できる一方、Web上の情報には反映されない関係が現実には存在する。リアルな社会での人や組織のつながりと、WEB上での単語や概念のつながりを対比しながら、その特徴を考えてみたい。論点は、人々は本当にWebを通じてつながっているのか、そして、つながりの検索は可能かである。 GBRC社会ネットワーク研究所所長、東京大学ものづくり経営研究センター特任助教授の安田雪先生は、数理社会学が専門で、関係構造の分析、数量化、可視化などがメイン。サ
シンプソン係数とは何？ わかりやすく解説 Weblio辞書
IT用語辞典バイナリ 索引トップ 用語の索引 ランキング 画像一覧 カテゴリー シンプソン係数 読み方：シンプソンけいすう 【英】Simpson's Coefficient シンプソン係数とは、自然言語処理における係数の一種で、XというキーワードとYというキーワードが同じページや同じ文書内で出現する（共起する）場合の頻度の強さを表現する指標として使用される係数のことである。主にWebなどの大規模文書において採用されている。 シンプソン係数は、次のような式で表される。 例えば、検索エンジンを使って「りんご」「みかん」と検索した場合、仮に「りんご」というキーワードの検索結果が5,830,000件、「みかん」というキーワードの検索結果が5,370,000件、「りんご みかん」という検索条件の検索結果は1,970,000件ヒットしたとする。この場合、「りんご」と「みかん」に関するシンプソン係数は、
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 に関して信頼できる情報源」ということ
リンク解析とか: 重要度尺度と von Neumann カーネル - smly’s notepad
NAIST の入学手続を終えた. 残りの期間はサーベイするぞーということで shimbo 先生の講義資料「リンク解析とその周辺の話題」を読んでいます. 一日目, 二日目の資料は PageRank, HITS, SALSA などの重要度尺度の紹介と, von Neumann Kernels と HITS の関係についてのお話が中心. これらを実装してみた. 後半に進むほど力尽きて記述が適当になってます:)PageRankポイントはランダム遷移行列による random walk では定常分布に収束しない (エルゴード性 (ergodic) を満たさない) という点. どうして満たさないかというと. sink (出次数のない節点) が存在するとき, 明らかに既約 (irreducible) でないのでエルゴード性を満たさない. 複数の強連結成分を持つケース => 周期性を持つと考えてよい? 周期
DO++: 機械学習による自然言語処理チュートリアル
自然言語処理のときに使う機械学習手法のテクニックをざーっと２時間程度で紹介してほしいとのことだったので今日話してきました。基本的に、そんなに頑張らなくても効果が大きいものを中心に説明（特にパーセプトロンとか）を説明してます。 紹介した手法はパーセプトロン、最大エントロピー、正則化、多クラス分類、系列分類（CRF, Structured Perceptron）などなどです。どれも一かじりする感じで網羅的に見る方を優先してます。個々の詳しい話はそれぞれの文献や実装などを当たってみてください。 スライド [ppt] [pdf] ここで話しているのは線形識別モデルの教師有り学習が中心で教師無し学習（クラスタリングなど）など他の自然言語処理を支える技術は省いてます。 こういうのを使って（使わなくてもいいけど）どんどんアプリケーション作らないといかんね。 Tarot is not used to ma
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万という大きさの行列を扱うことになりますが、単
CNET Japan
人気記事 1 テスラの「紛らわしい機能名」めぐりカリフォルニア当局が30日の販売停止を要求 2025年07月22日 2 「Pixel 10」の姿が明らかに、グーグルが映像公開--8月20日発表へ 2025年07月22日 3 「たんぱく質がとれる水」発売--500mlペットボトルに5g配合 1本178円 2025年07月22日 4 マニアック過ぎたソニーXperia、変わり始めた矢先の不具合--文鎮騒動を解説（石川温） 2025年07月22日 5 山手線で5人負傷--発火相次ぐモバイルバッテリー、注意すべき8つのポイント 2025年07月22日 6 「ドン・キホーテ」初の無人店舗--商品を手にとって店を出るだけでOK セルフレジ不要 2025年07月22日 7 サムスン最新折りたたみスマホを入手も、すぐ「コンクリ地面」に落としてしまった話 2025年07月19日 8 アップル「AirPods
最長しりとり連鎖問題 - Satomilogical Research
こういう問題を思いついた。 次に言う言葉がもうない場合、最後に「ん」がついた場合にしりとりが終了するとして、ある辞書に登録された単語のみを使ってしりとりをするとしよう。もっとも長いしりとり連鎖の回数（とその連鎖のリスト）を出力するアルゴリズムを考えよ。 twitter/satomilogy ある辞書に登録された単語に限定してしりとりを行うとどうなるんだろうと考えた。まずしりとりはちゃんと終わるだろうか。有限の単語数の辞書なんだから必ず終わる。「ん」がついても終わる。では、ある辞書の中でどれくらい長くしりとりを続けることができるのだろうか、というのがこの問題です。可能なしりとり連鎖の組み合わせを総当りで求めて、その中から最長のものを選ぶというアルゴリズムはすぐに思いつきましたけど、おもしろくないですね。 問題を単純化してみてわかったこと 実際の国語辞典を使ってやる場合には、しりとりのローカル
綱引きに蛇口当てゲーム？！ 楽しく学ぶベイズフィルターの仕組み
付き合いたくないスパムと付き合うために 受信者の意向を無視して、一方的に送りつけられる迷惑メール（スパム）は、いまやメールボックスを雑音でいっぱいにしてしまい、大事なメールを見過ごしかねないほどの量に膨れ上がり、大きな問題となっています。 残念ながら、このようなスパムを発生源から断つような根本的な対策はいまだになく、私たちは、せめてメールサーバで受け取った大量のメール群からスパムと大事なメールを仕分けしてくれる仕組みに頼らざるを得ません。 スパムを判定する方法は、次の2つに大別することができます。 本稿では前者の方法に着目します。メールを受け取った人にとっては、メールの中身を読めば、そのメールがスパムかそうでないかを判定するのは容易なことです。スパムの定義は、メールを読む人によって変わる可能性があります。例えば、まったくゴルフをしない人にゴルフの勧誘メールが来た場合はスパムといえるでしょう
Webstemmer のしくみ
back [English] 基本的な原理 レイアウト分析ツール analyze.py 本文を抽出する extract.py パターンファイルの構造 おわりに 基本的な原理 Webstemmer では、以下のような仮定をもとにして Web ページを分析しています。 すべての記事には共通した (たかだか数種類の) レイアウトが使われている。 各ページにはメインとなる文章がひとつ含まれている。 (従って、この原理は日記や掲示板などのサイトには使えません) 記事の文章は毎日変わっても、そのレイアウトは変わらない。 バナー広告やナビゲーションの HTML タグは同一レイアウトのページで不変。 Webstemmer はこの仮定をもとに、 あるニュースサイトの同一レイアウトをもつページをまとめ、 それらのページ中で「変化していない部分」をさがします。 バナーやナビゲーション用のリンクなどはレイアウトが
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
