0x5f3759df
This post is about the magic constant 0x5f3759df and an extremely neat hack, fast inverse square root, which is where the constant comes from. Meet the inverse square root hack: float FastInvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int*) &x; // evil floating point bit level hacking i = 0x5f3759df - (i >> 1); // what the fuck? x = *(float*)&i; x = x * (1.5f - (xhalf*x*x)); return x; } What
ALENEX'15 論文採択：指数時間 Branch-and-Reduce アルゴリズムの実性能 - iwiwiの日記
国際学会 ALENEX 2015 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカの San Diego です． 今回の論文は "Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover" というタイトルで，研究室同期の岩田との共著です． 背景１：アルゴリズム研究における理論と実性能の乖離 アルゴリズムが好きな人はよ
Cuckoo Filters
My take on computer science -- algorithms, networking, information theory -- and related items. An upcoming paper appearing at CoNext will be of interest to any Bloom Filter user or aficionado: Cuckoo Filter: Practically Better than Bloom (Bin Fan, David Andersen, Michael Kaminsky, Michael Mitzenmacher) Let me describe a cuckoo filter and some of what's in the paper for you. If you want to avoid
可視化で理解するマルコフ連鎖モンテカルロ法(MCMC) - ほくそ笑む
先日行われた第9回「データ解析のための統計モデリング入門」読書会にて、 「可視化で理解するマルコフ連鎖モンテカルロ法」というタイトルで発表させて頂きました。 発表スライドは以下です。 可視化で理解するマルコフ連鎖モンテカルロ法 from hoxo_m この発表は、みどりぼんに登場する、マルコフ連鎖モンテカルロ法(MCMC)のアルゴリズムである「メトロポリス法」と「ギブス・サンプラー」について、可視化して理解しようというお話です。 「マルコフ連鎖モンテカルロ法」というのは、字面だけ見ると難しそうですが、この発表で理解すべきポイントは、次のスライド 1枚に凝縮されています。 このことを念頭に置いて、それぞれの手法を見ていきましょう。 まず、メトロポリス法ですが、これは、 前の状態の近くの点を次の遷移先候補として選ぶ（マルコフ連鎖） そのときの確率比 r < 1 ならば確率 r で棄却する。それ
非負値行列因子分解（NMF）によるレコメンドのちょっとした例 - About connecting the dots.
最近線形代数についていろいろ読みなおしたりしてるのですが（線形代数チートシートを前の記事でまとめてあります），その一環でレコメンドアルゴリズムについていくつか試してみたので，それを解説します．順序としては，基本の協調フィルタリング（ユーザベースド，アイテムベースド）→特異値分解（SVD）→非負値行列因子分解（NMF）になります． 基本的な考え方 ここで取り扱うのは，すべて以下のようなユーザ×商品のマトリックスをベースとしたレコメンドになります*1．ここでは映画レンタルサービスを例にして考えます．6人のユーザが，4つの映画*2のうちレンタル視聴したものについては，1-5点の5段階評価を行いました．0になっているものは「みていない」ということになります． まずはざっと評価の状況をみると，「千と千尋の神隠し」が最もよく視聴されていて，6人中4人がみています．次にみられているのは「となりのトトロ」
AdaGradが12倍速くなる魔法
AdaGradは学習率を自動調整してくれる勾配法の亜種で、いろんな人が絶賛しています。 勾配を足し込む時に、各次元ごとに今までの勾配の2乗和をとっておいて、その平方根で割ってあげるだけと、恐ろしくシンプルです。 Adaptive Subgradient Methods for Online Learning and Stochastic Optimization John Duchi, Elad Hazan, Yoram Singer. JMLR 2011. 丁度、 @echizen_tm さんがブログを書いてました。 AdaGrad+RDAを実装しました。 通常のSGDなどは学習率をだんだん減衰させながら勾配を足していくわけですが、どの様に減衰させるかという問題にいつも頭を悩ませます。 AdaGradでは最初の学習率こそ外から与えますが、減衰のさせ方や減衰率といったハイパーパラメータから
L1正則化を導入した Online学習手法
L1正則化を導入した Online学習手法 数理言語情報学研究室 修士一年 大岩秀和 目次 はじめに 紹介論文概要 問題設定：教師あり学習 Online学習／L1正則化 Online学習 L1正則化 Forward Backward Splitting(FOBOS) FOBOS Algorithm Regret分析 実験 まとめ 2 目次 はじめに 紹介論文概要 問題設定：教師あり学習 Online学習／L1正則化 Online学習 L1正則化 Forward Backward Splitting(FOBOS) FOBOS Algorithm Regret分析 実験 まとめ 3 紹介論文概要 Efficient Online and Batch Learning using Forward Bac
ボロノイ図を使ってラベルの重なり合いを解消する
画像をクリックすると、デモページに飛びます。 見づらいラベル 地図上に沢山のラベルを並べると、位置によっては重なり合ってとても見ずらくなります。 このラベルの配置位置をボロノイ図を利用して重なり合わないように配置してみます。 母点から中心点へ まず、ポイントを母点としたボロノイ図を描きます。 各ボロノイのセル（ボロノイ領域）の中心点を求め、母点から中心点へのラインを引きました。 ボロノイ領域の中心点は、母点から見て空きスペースの方角となります。 この角度を利用してラベルを配置します。 中心点に向けてラベルを配置 単純にラインに沿う角度でテキストを回転(rotate)させました。 重なり合いは解消されましたが、必ずしも見やすくはありません。 （これはこれで活用方法がありそうですが） ラベル開始位置をずらす 母点からボロノイ領域の中心点の方角へ、ラベルの開始位置を少しずらして配置した例です。
Programming and DIY Projects: Advanced Tools and Techniques
By choosing the right language for the job, developers can optimize productivity and project outcomes. 3. Linux and Open Source for Developers Linux remains a developer’s paradise with its flexibility, tools, and open-source support. Top Tools for Developers in Linux tmux: Terminal multiplexer for managing multiple sessions. htop: A process viewer for real-time resource monitoring. Docker: For con
wavelet行列で高速な「もしかして友だち？」検索 | 株式会社サイバーエージェント
業務経歴： Sierでのソフトウェア開発・大手メディアでのサービス運用を経て2012年サイバーエージェント入社。 アメーバ事業本部コミュニティサービスの開発責任者を経て、現在はアドテクスタジオで広告配信技術に注力。 好きな分野はグラフ探索とチューリングマシン。 ソーシャルサービスでは、ユーザ間のつながりやユーザ同士の類似性がとても重要です。 つながりの近いユーザや自分と似ているユーザを「もしかして友だち？」とサジェストすることでユーザ間のつながりを伸展させることができます。 そこで、ユーザの「つながり」具合が似ているユーザを「友だちかもしれないユーザ」としてサジェストを行うことを考えました。 しかし「つながり」のデータというのはユーザ数のベキ乗であるため、容量が大きくなりやすい性質があります。 即ち、「つながり」類似度の算出には時間がかかる、ということです。 この「つながり」類似度算出
冗長性が低く重要度の高いパターンの抽出(1) - sfchaos's blog
パターンマイニングはデータマイニングを代表する手法の一つで，特にアソシエーションルールを適用した「ビールとおむつ」などの例が有名です． 最近は，Rなどのデータ分析ツールでもAprioriやEclat(頻出パターンマイニング), CSPADE(系列パターンマイニング)等のアルゴリズムを実行するライブラリが提供されており，パターンマイニングを実行することの障壁は比較的低くなっています． パターンマイニングでは，一般的に膨大な数のパターンが抽出されます．この事象はアイテムの組み合わせや順列の数が膨大になることに起因しており，少量のトランザクションから大量のパターンが抽出されることも決して珍しくありません*1．このような背景の下，パターンマイニングで抽出されたパターンから重要なパターンを抽出することは，大きな技術的課題の一つだと言えるでしょう． 抽出したパターンは膨大な数に 以上で説明したことを実
実践・最強最速のアルゴリズム勉強会 第三回講義資料(ワークスアプリケーションズ & AtCoder)
Image Retrieval Overview (from Traditional Local Features to Recent Deep Lear...
楓 software: mozjpeg はどのようにして圧縮率を上げているのか？
« Android 対応必要項目と工数見積もり | メイン | Lanczos3 を組み込んだ » 2014年03月10日 Misc.:: mozjpeg はどのようにして圧縮率を上げているのか？ Tweet @jin1016をフォロー ざっくりソースコード見たりしただけなので、間違っているかもしれないが書いておく。 一言で書くと「プログレッシブ方式で、DC成分の分割サイズを最適なものにすることで偏りを増やし圧縮率を上げている」ということのようだ。 この説明だと知っている人以外にとっては意味不明だと思うので、どのように圧縮しているのかある程度説明し、なぜ圧縮率が上がるのか説明してみる。 JPEG では、色空間変換 → DCT → 量子化 → ハフマン符号化+ランレングス と言う手順で圧縮している。 この中で実際に圧縮を行っているのは、「ハフマン符号化」と「ランレングス」の部分。 これ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://imi.kyushu-u.ac.jp/~waki/ws2013/slide/suzuki.pdf
Account Suspended
Raft
乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
実践・最強最速のアルゴリズム勉強会 第一回 講義資料(ワークスアプリケーションズ & AtCoder)
いつからFIFOがスケールしないと錯覚していた
Boost.Graphの設計と、最短経路アルゴリズムの使い方いろいろ
