wavelet行列で高速な「もしかして友だち？」検索 | 株式会社サイバーエージェント
執筆者 執筆者：井上ゆり 所属部署：アドテク本部 アドテクスタジオ 業務経歴：Sierでのソフトウェア開発・大手メディアでのサービス運用を経て2012年サイバーエージェント入社。 アメーバ事業本部コミュニティサービスの開発責任者を経て、現在はアドテクスタジオで広告配信技術に注力。 好きな分野はグラフ探索とチューリングマシン。 ソーシャルサービスでは、ユーザ間のつながりやユーザ同士の類似性がとても重要です。 つながりの近いユーザや自分と似ているユーザを「もしかして友だち？」とサジェストすることでユーザ間のつながりを伸展させることができます。 そこで、ユーザの「つながり」具合が似ているユーザを「友だちかもしれないユーザ」としてサジェストを行うことを考えました。 しかし「つながり」のデータというのはユーザ数のベキ乗であるため、容量が大きくなりやすい性質があります。 即ち、「つながり」類似度の
Wavelet Trees: an Introduction
Today I will talk about an elegant way of answering rank queries on sequences over larger alphabets – a structure called the Wavelet Tree. In my last post I introduced a data structure called RRR, which is used to quickly answer rank queries on binary sequences, and provide implicit compression. A Wavelet Tree organises a string into a hierarchy of bit vectors. A rank query has time complexity is
Wavelet Treeをもう一度 - 気ままなブログ
文字列本のメインであるウェーブレット木をもう一度素直に見直すことにした。 高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 15人 クリック: 324回この商品を含むブログ (5件) を見る Wavelet Treeに関する著者のスライドは以下である。 http://www.slideshare.net/pfi/ss-15916040 ふらふらと論文を眺めていたら、Navarro神の「Wavelet Trees for All」というサーベイ論文が加筆されて更新されていた。内容自体はあまり変わっていないと思うが図が増えていた。以下がその論文である。 http://www.dcc.uchile.cl/~gnavarro/ps/jda13.pdf 大半の内
An Efficient Parallel Algorithm for Graph Isomorphism on GPU using CUDA
Modern Graphics Processing Units (GPUs) have high computation power and low cost. Recently, many applications in various fields have been computed powerfully on the GPU using CUDA. In this paper, we propose an efficient parallel algorithm for graph isomorphism which runs on the GPU using CUDA for matching large graphs. Parallelization of a sequential graph isomorphism algorithm is one of the harde
全点対間最短路を高速に求める - Fixstars Tech Blog /proc/cpuinfo
それぞれのプロセッサ用の愚直な実装と比べてみると、CPUでは約25倍、GPUでは約42倍の性能向上となりました。 また、CPUでは限界の65%程度、GPUでは限界の80%程度の性能を出すことができています。 なんとなくではありますがCPU版はもう少し詰められそう、GPU版はCUDA Cでここから先はきつくなりそうといった気がします。 まとめ ワーシャル-フロイド法を通して、同じハードウェア・同じ計算量であっても性能に大きな差が出る例を示しました。 ICPCのようなコンテストではあまり定数倍のチューニングは重要視されませんが、このような方法でのアルゴリズムの高速化にも興味を持っていただければ幸いです。 参考文献 [1] Joon-Sang Park, Michael Penner and Viktor K Prasanna. “Optimizing graph algorithms for
マジックカーネル – 画像のリサンプリングのメソッド | POSTD
マジックカーネルとは？ “マジックカーネル”とは、極めて高速で（一番単純なバージョンなら、必要なのは少しの整数加算とビットシフトのみです）、驚くほどの結果を出してくれる効果的な画像のリサンプリングのメソッドです（エイリアシングノイズやリンギング、細かい物体の”Width beat”の発生を防ぎます）。 私がこのマジックカーネルと出会ったのは2006年、一般的に使われているJPEGライブラリのソースコードを扱っていた時のことです。それ以来、この素晴らしい特性を深く探り、任意のリサンプリングファクタのケースにまでこのメソッドを広げました。 このWebページでは、それらの特性を要約して説明し、画像への適用も含めてマジックカーネルのC#のコード実装の全てをご紹介します。 マジックカーネルはどこから来たのか 2006年に私は、JPEGを過剰に圧縮すると発生するブロックノイズを最小限に抑えるいい方法は
A Big Result On Graph Isomorphism
Jumping GI down from the nearly-exponential neighborhood to the nearly-polynomial one László Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him. Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time. More exactl
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
NMFアルゴリズムの紹介 その② GCD - 北の大地から
2015-10-05 NMFアルゴリズムの紹介 その② GCD 研究が進んでいないので，記事を書いて，モチベーションを高めることに．．．． 今回の紹介アルゴリズムはNMFで現在(2015年10月)で最速といわれている(筆者の知る限り）手法Greedy Coordinate Descent Algorithmの紹介です． 元論文は， Hsieh, C.-J., & Dhillon, I. S. (2011). Fast coordinate descent methods with variable selection for non-negative matrix factorization. In ACM SIGKDD (pp. 1064–1072). https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3
HL decomposition+SegTreeのlogを1個消す - よすぽの日記
はじめに この記事はHL分解について書きます。 HL分解+SegTreeでパス上のクエリに答えると、最悪ケースで O(log2 N) per query ですが、これを O(logN) per query に改善したいと思います。 アイデア HL分解の詳細についての解説は省きます。たくさんネットに資料は転がっているので探してください。 HL分解+SegTreeでパス上のクエリに答えるのは 木をHL分解でパスに分解し パスをSegTreeで管理する という 2ステップからなります。パスに分解してまとめた後の木の高さが O(logN)、そのパスへのクエリが O(logN) で、合わせて計算量は O(log2 N) です。 実は 2つめのステップで、あえてアンバランス(完全二分木ではない)なSegTreeを使うことで、logを1つ落とすことができます。 1つめのステップは普通のHL分解と全く同一
高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開
Yahoo! JAPAN研究所の岩崎です。 私は主に特定物体認識の研究開発を行っていますが、その一方で特定物体認識において必須技術である高次元ベクトルデータの近傍検索の研究開発も行っています。近傍検索の一種であるk最近傍検索とは、クエリとしてベクトルデータが与えられた時に、クエリと空間内に点在するベクトルデータとの距離に基づき近い順にk個のデータを検索する、ことです。kが5の場合の最近傍検索の例を図1に示します。図中の数字は距離の順位で、青い点が検索結果となるデータです。 空間内のすべてのデータとの距離を計算すると時間がかかるので、高速化のためにインデックスを利用します。インデックスを用いることにより数次元といった低次元のベクトルデータ空間では高速な検索が比較的容易に実現できます。しかし、インデックスを用いても100次元を超えるような高次元ベクトルデータの場合には高速に検索することが困難と
パターン認識に関する公開プログラム
宇野毅明と有村博紀による公開プログラム（コード） このページでは、公開しているプログラムのコードがダウンロードできます。主に、列挙アルゴリズムやデータマイニングに関するものです。全て、宇野毅明、あるいは、良く一緒に研究をしてお世話になっている北海道大学の有村博紀先生によって作られたものです。各プログラムに使用言語とコード作成者が書いてありますので、質問、あるいはバグの報告などは、作成者にご連絡ください。宇野毅明は uno@nii.ac.jp、有村博紀先生は arim@ist.hokudai.ac.jp です。 !!! コードの最近のバージョンに、マッキントッシュのフォーマットではエラーが出るというバグがありました。現行バージョンではこのバグは治っています。 LCM (Linear time Closed itemset Miner) ver.2 (C言語、宇野毅明) [文献 1]
焼きなまし法でThomson問題の解を探索する - lan496の日記
Thomson問題 Thomson問題とは、三次元単位球の表面にN個の電荷の等しい粒子を配置するとき、クーロンポテンシャル\( U = \sum_{i < j} \frac{1}{|\rm{r}_{i} - \rm{r}_{j}|}\)が最小となる配置となるを求める問題です。詳しくはwikiをThomson problem - Wikipedia, the free encyclopedia。N=5のときにて三方両錐形が解になったり、N=8で立方体が解にならないなどいろいろと面白い問題です。 去年の12月頃、そもそもこの問題設定に名前が付いていることをある方から教えていただき、N=5の場合で実際に初期条件を与えて時間発展させることで本当に三方両錐形になるのか実験してみました。 球面上の点電荷が最も安定する配置(thomson problem)のRK4を利用したシミュレーションの進捗 pic
Reverse Search - Sebastian Nowozins slow blog
One of my all-time favorite algorithms is reverse search proposed by David Avis and Komei Fukuda in 1992, PDF. Reverse search is an algorithm to solve enumeration problems, that is, problems where you would like to list a finite set of typically combinatorially related elements. Reverse search is not quite an algorithm, rather it is a general construction principle that is applicable to a wide var
t-SNE
t-Distributed Stochastic Neighbor Embedding (t-SNE) is a technique for dimensionality reduction that is particularly well suited for the visualization of high-dimensional datasets. The technique can be implemented via Barnes-Hut approximations, allowing it to be applied on large real-world datasets. We applied it on data sets with up to 30 million examples. The technique and its variants are intro
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
任意の学習率の式に対する効率的なL1正則化の計算方法 : Preferred Research
今回はaveraged FOBOSの導出をしてみたのでその話を書こうかと思ったのですが、導出途中に平均化劣勾配法の場合と大差ないと気付いてしまってテンションが下がってしまいました。というわけで、ちょっとネタを変えて、学習率をいい感じに減衰させながら学習するためにはどうしたらいいのか、ありがちな実装テクニックについて書いてみます。 前提知識 前提知識として最適化問題をどう解くかを知っている必要があります。これについては以前に入門記事を書きましたので適宜ご参照下さい。文字数制限の関係で4回目と5回目のみリンクしておきます。 劣微分を用いた最適化手法について(4) やっとFOBOSが出てくる第4回 劣微分を用いた最適化手法について(完) 感動の最終回 問題提起 最近のオンライン学習において重要なテクニックの1つとして、パラメーター更新の遅延（lazy update）があります。これは、正則化の計
AAAI2015で発表した - でかいチーズをベーグルする
AAAI2015で発表してきた。タイトルは"OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation"。必殺チェアーからの質問による時間稼ぎは出ずにちゃんと聞いてくれてる人たちから質問が出たから良かったかな。 今回はソーシャルネットワークにデータを限らずに出来るだけ広範囲のグラフに適用できるアルゴリズムを提案した。話を一般的にしようとすればするほど大変だといういい経験が出来た。ドメインに特化した問題を解くアルゴリズムももちろん重要だけど、やっぱりいろんなデータに対して適用できるアルゴリズムを提案するってのはその分野の発展にも寄与できるしもっと重要だと思う。 OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation from
Python Packages for Graph Cuts on Images
A graph for a small image of 512x512 pixels has 261144 nodes and 523264 edges in the 4-connected pixels case. Graphs in this scale require a fast construction interface. I reviewed a few python packages mainly from this perspective. The comparison is by no means exhaustive and fair! Based on Kolmogorov min-cut / max-flow C++ library original Kolmogorov’s code: http://vision.csd.uwo.ca/code/#Max-fl
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Chromeのなかのコンピュータ・サイエンス
