Looks Like It - The Hacker Factor Blog
For the last few months, I have had a nearly constant stream of queries asking how TinEye works and, more generally, how to find similar pictures. The truth is, I don't know how the TinEye image search engine works. They don't disclose the specifics of the algorithm(s) that they use. However, based on the type of results it returns, it appears to me to be some variation of a perceptual hash algori
Complement Naive BayesをPHPで実装した - よしだ’s diary
アルゴリズムの理解を深める為、Rubyで書かれた実装をそのままPHPに移植してみた。 Complement Naive Bayes らしきものをRubyで書いた - 記録用 http://d.hatena.ne.jp/laughing/20101114/1289698415 <?php class CNB { public function __construct($smoothing_parameter=1) { $this->frequency_of_word_by_class = array(); $this->number_of_training_data_of_class = array(); $this->smoothing_parameter = $smoothing_parameter; } public function training($label, $sosei)
complement naive Bayes - 機械学習の「朱鷺の杜Wiki」
多項モデル† 単純ベイズで文書分類をする場合によく用いられるのが多項モデル． 単純ベイズでは，文書 \(\mathbf{x}_i\) が与えられたとき，クラス \(c\) になる確率は次式 \[\Pr[c|\mathbf{x}]\propto\Pr[\mathbf{x}|c]\Pr[c]\] \(w\) 種類の語があるとき，文書ベクトル \(\mathbf{x}_i=(x_{i1},x_{i2},\ldots,x_{iw})\) の要素は，語 \(j\) が文書 \(i\) 内で生じる回数． 多項モデルでは，この要素の頻度が多項分布に従うとする．クラス \(c\) の任意の文書のある語を選んだとき，その語が語 \(j\) である確率を \(\theta_{cj}\) で表す．すると，文書 \(\mathbf{x}_i\) は次式で決まるクラスに分類される \[\arg\max_c=\ln\
b-Bit MinHashによる高速かつ省スペースな類似度判定 | SmartNews開発者ブログ
ゴクロの浜本です。ネットカフェでコードを書くのが好きです。 前回のエントリーでも触れられていますが、SmartNewsはホットな話題をユーザにお届けするために、常時、膨大な数のツイートおよびURLをクロールしています。こうして収集した記事に対し、様々な分析が施されますが、その中でも重要な処理の1つに、記事の類似度判定があります。内容の似通った記事をインデックスから発見し、グループ化する処理です。 毎秒、大量の新着記事が到着することから、この類似度判定は高速に実行する必要があります。また、インデックスを全てメモリに載せているので、類似度判定を実現する際の空間効率も要求されます。 今回は、SmartNewsが高速かつ省スペースな類似度判定のために使用しているb-Bit MinHashと呼ばれる手法を紹介します。2年前に、PFIの岡野原さんが非常に分かりやすい解説記事を書かれており、本エントリー
MinHashによる高速な類似検索 - Preferred Networks Research & Development
年が明けてもう一ヶ月経ちましたね．岡野原です． 今日はMinHashと呼ばれる手法を紹介します．これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている）． 今や世の中のあらゆる種類のデータが，高次元のバイナリベクトルからなる特徴ベクトルで表されて処理されるようになってきました．例えば文書データであれば文書中に出現する単語やキーワードの出現情報を並べた単語空間ベクトル（Bag of Words）で表し，画像データも，SIFTをはじめとした局所特徴量を並べた特徴ベクトル（とそれをSkecth化したもの）として表せます．行動情報や時系列データも特徴量をうまく抽出する．グラフデータもFast subtree kernels[1]と呼ばれる方法で非常に効率的に特徴ベクトルに変換することができ，グラフの特徴をよく捉えることができるのが最近わかっ
ベイズ分類をベースにしたSmartNewsのチャンネル判定 | SmartNews開発者ブログ
株式会社ゴクロの中路です。普段は機械学習の手法を用いたアルゴリズム改善など、サーバーサイドの開発を行っています。 SmartNewsでは様々なニュース記事を「エンタメ」「スポーツ」「グルメ」などのチャンネルに分けて表示しています。そのようなことを可能にするためには、ニュース記事がどのチャンネルに属するのかを判断する必要があるわけですが、それを行っているのは人ではありません。機械が、アルゴリズムに基づいて、自動的に行っています。 今回のエントリーでは、その「自動的にチャンネルに分類する仕組み」について書こうと思います。 SmartNewsにおける、ニュース記事のチャンネル判定を単純化すると、ベースには「ナイーブベイズ分類器」と呼ばれる、機械学習の初歩的な知見があります。このエントリーではナイーブベイズ分類器をメイントピックとして取り上げます。ナイーブベイズ分類器については、すでに様々なとこ
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました 12/11 前編の図２つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
CodeIQで結城先生が出題されたCrossingが神がかっていた件 - やねうらおブログ(移転しました)
CodeIQで挑戦者数が400人超えという異例の事態になったCrossingとはどんな問題だったのか。twitterでも恐ろしい勢いで拡散され、最終日に100人を超えるチャレンジがあった、この問題。一体どこにそんな魅力があったのかについて考えてみる。 まず、このように注目されるためには満たすべき条件が二つある。 繁盛する飲食店を考えてもわかるように、まず美味しくなければならない。CodeIQで言うと、問題として良問でなければならない。解答後の達成感がなくてはならない。 次に、飲食店なら、その店に入ってみようという気にさせなければならない。入りにくそうなお店でも、料理さえ美味しければその後口コミで広がることもあるだろうが、それだと繁盛するまでに時間がかかりすぎる。だからCodeIQで言うと、まず問題を解いてみようという気にさせなければならない。 このどちらが欠けても駄目である。この問題はこの
マラソンマッチの取り組み方 – システム工房コルン
目次 はじめに マラソンのノウハウは、たった３つ １．問題をしっかり把握する 問題をちゃんと読む テスタを読む 問題を理解するために回答プログラムを書く ビジュアライザの自作 ２．判断基準を明確にする テスト環境の構築 部分問題の基準構築 点数モデルの脳内構築 ３．反復期間を短くする 周辺技術の調査 プロトタイピング 解法の構成 寄せて行くノウハウ 付録 テクニック的なこと 高速化について ローカルテスト実行時に追加情報を与える 枝刈りを観測的に行う方法 より複雑な点数モデル 最後に はじめに 皆さんこんにちは。 この記事は、下記のイベントの一環として書かれたものです。 Competitive Programming Advent Calendar http://partake.in/events/ee35b200-e151-44c1-b123-482d0a7447b5 マラソンマッチ上位
CODE VS 2.0 - kusano-k’s blog
CODE VS 2.0に参加した。 結果は、予選が総合9位、学生7位。決勝が初戦負けだった。5位の賞状（たぶん一回戦で負けた人全員が5位）を貰ったので、結果を訊かれたら、5位だったと言おう( ･`д･´) 予選 基本的に、3手（小）2手（中大）を全探索して最も評価値の高いところに落とすだけ。工夫したところは、 盤面を一次元配列で表すと、縦・横・斜めのラインが等差数列になるので、ラインを等差数列として管理する。似たような処理を何回も書かなくて済む。 落下・消去時の処理は変化したブロックが含まれるラインだけで良いので、各ラインごとに処理する必要があるかを覚えておいて高速化。 スコアではなく現在できている連鎖数を評価する。連鎖数は全ての場所に全ての数値を1個落としてみて、最多の連鎖数を採用する。1手深く読んだくらいの時間がかかるけど、こうしないと、例えば連鎖を伸ばしておいて10手先のブロックで発
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
短いハッシュの作り方 - OKWAVE
いくらでも方法はあるので、質問者さんが挙げられているサイトが実際にどうやっているかはわかりませんが、 6文字程度の文字列では、「衝突しないハッシュ関数」を作るのは非常に困難であり、「衝突が発生する」ことがあるのを前提にして設計しないとといけません。 こういう場合、「ハッシュテーブル」におけるハッシュの取り扱いが参考になるでしょう。 ハッシュテーブルにおけるハッシュ関数は、名前が同じ「ハッシュ」でも、取り扱い方はmd5やsha1などとは異なります。 ハッシュテーブル用のハッシュ関数にはいろいろありますが、 中でもKnuth のアルゴリズムが有名です。 そういったハッシュ関数を使って最大値[62^6]のハッシュを生成し、それを 62進数に6桁に変換して、それを文字列化すればいいでしょう。 Knuth のハッシュ関数: http://d.hatena.ne.jp/yamanetoshi/2009
プログラマの実力は経験だけであがらないことがレベル格差につながる - きしだのはてな
プログラマというのは、道具に慣れることが、実力があがることにならないのですよね。だから、勉強せず業務経験だけだとレベルが低いままということになってしまう。 Javaを10年さわり続けて、Strutsを5年さわり続けても、それだけでは、与えられた画面を手際よく作成できるようになるだけで、たとえばStrutsすらよりよく使えるようになるわけではなかったりする。 Javaにしても、「volatileってなんですか？」という問いに、まあ知らないのはしかたないとしても、解説を見ながらですら答えられない可能性がある。 プログラムの反復生産は、プログラミング能力の向上にあまりつながらない。設定や記述に慣れるだけだ。そして、この「慣れ」というのには「難しいからそもそも実装を回避する」というようなものも含まれる。実力の向上は、作業ができるレベルで止まってしまう。 プログラマとしての実力をあげるための勉強が自
高層ビルのエレベーターホールには、なぜ階数表示がないのか - 本当は怖いHPC
以前に高橋幸雄先生の授業で聞いて非常に面白いと思ったこと。 オフィスビルとかホテルとか、エレベーターが何基も設置されているビルの場合、エレベーターホールに階数表示が無いことが多い。エレベーターホールで画像検索してみればわかると思う。 これはなぜだろうか。 その理由は、「客がいても、その階を通過することができるようにするため」だ。 基本的に、多数のエレベーターを効率よく動かすのは難しい。工夫された高度なアルゴリズムが使われていることが多い。目標は「客の平均待ち時間を短くする」ことだ。ある階でボタンが押された場合、どのエレベーターがその客を迎えに行くか、という判断が平均待ち時間に大きな影響を与える。難しいアルゴリズムの中で、この点がもっとも重要なところだ。 高層ビルの場合、エレベーターはかなりの速度で走っている。既に客を乗せて走っているエレベーターが他の客を乗せるために停止すると、減速→停止→
TANAKA Tetsuro
Japanese version is here. Name TANAKA Tetsuro Birthday February 1965 Club University of Tokyo Micro Comuputer Club (UTMC) Interests Kanji Skeleton Font to see a sample file), Lisp Implementation, Parallel Functional Programming language Papers Back to ECC staffs page Back to ECC home page TANAKA Tetsuro ()
【PDF】田中哲朗「「どうぶつしょうぎ」の完全解析」
Japanese version is here. Name TANAKA Tetsuro Birthday February 1965 Club University of Tokyo Micro Comuputer Club (UTMC) Interests Kanji Skeleton Font to see a sample file), Lisp Implementation, Parallel Functional Programming language Papers Back to ECC staffs page Back to ECC home page TANAKA Tetsuro ()
このプログラミング問題が解けたら書類選考無し＆高級うなぎGET！ | Technology-Gym
—–7月5日追記—– たくさんの”解けた！”連絡ありがとうございました！ お陰様で、先着5名様についてはすぐに埋まってしまいました。 （該当の方には別途ご連絡いたします） 採用へのご応募と、解けたかどうかの確認については引き続き受け付けておりますので、 是非チャレンジしてみてください。 また機会をみて開催させていただきます！ ご興味を持っていただき、ありがとうございました。 ———- みなさんこんにちは！ 株式会社プラスアールではiOS/android問わずスマートフォンアプリ開発エンジニアを募集しています。 ただ単に募集をかけてもあまり面白くないので、 今回は特別に、下の問題を解けた方の書類選考を無しにいたします！ かつ、オフィスすぐそばにある野田岩のうなぎ（ランチ）をごちそういたします！ 応募以外の方でも、 問題が解けた＆ランチ時間帯に赤羽橋まで来ていただけるようでしたら、 野田岩のう
数独を解く(画像解析) - cuspy diary
画像として与えられた数独を解きます。 新聞に掲載されていたこの問題をOpenCVを使って画像解析する。(画像が斜めなのはワザとです) グレースケール変換画像解析の前処理として、まずグレースケールに変換し、ガウシアンフィルタをかけてぼかします。ガウシアンフィルタをかける事で、安定した二値化画像が得られます。 二値化次に二値化を行います。 二値化には、普通の方法、大津さんの手法、適応的二値化、などさまざまな手法が在ります。いろいろ試した所、適応的二値化(Adaptive Threshold)が最も数独の認識に適していることが解りました。 適応的二値化(Adaptive Threshold)であれば、影になってしまった部分も上手く処理できます。 膨張処理次に、数独の盤面の外枠を認識を行います。 二値化の影響で枠線が途切れてしまう可能性がありますので、膨張処理(dilate)を行います。 (膨張処
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
九段破れたり AIとプロ棋士のタッグ戦、思わぬ番狂わせ ジャーナリスト 新 清士 - 日本経済新聞
ハッシュ法入門