Ruby1.9以前でバイナリサーチ - Qiita
Ruby2.0以降はArray#bsearchが、2.3以降はArray#bsearch_indexが標準でありますが、どうしても1.9を使わなければいけないことがあったので、自前で実装しました。 仕様としてはRuby2.0のArray#bsearchのfind-minimumモードと同じにしてあります。 class Array def bsearch(&block) index = bsearch_index(&block) index.nil? ? nil : self[index] end def bsearch_index(&block) return nil if length == 0 bsearch_impl(self, &block) end def bsearch_impl(ary, &block) if ary.length == 1 return block.call
平方根を使わずに高速で２点間の距離を近似する - きしだのHatena
２点間の距離の計算では平方根が必要になりますが、平方根は少し重い計算です。ということで、平方根を使わず、掛け算・割り算・足し算と絶対値・最大・最小だけで距離を近似する方法についての記事を翻訳してみました。 flipcode - Fast Approximate Distance Functions (12:02 補足：おそらく今の標準的なCPUでやる意味はほとんどないと思います。近似のアプローチとして面白いというくらいの話。Z80でやりましょう) 距離関数高速近似 by Rafael Baptista (27 June 2003) ２点間のユークリッド距離を求める計算式は次のようになる。 二次元では次のようになる。 この関数の計算には、平方根が必要になる。これは最近のコンピュータでも高価な計算である。平方根は逐次近似によって求められる。つまり、コンピュータは平方根近似のループを行って、与え
浮動小数点数型と誤差
有限桁 Ｃ言語で扱える実数値は，２進数の有限小数で表された数値である．例えば次のようなものである． 1.5(10) = 1.1(2) 3.25(10) = 11.01(2) 理論的には小数が無限に続く値でも，そのうちの有限個の桁数でその値を表すしかない． 例えば，0.1 を２進数の小数で表すと 0.1(10) = 0.000110011001100110011...(2) と無限に続くが，コンピュータの内部では有限桁で丸められている． このような場合には，本当の値ではなく，近似値でしか表すことができない． 指数表記（浮動小数点表記） 科学計算では非常に大きな実数値や非常に小さな実数値も扱うことがある． そのようなときには，通常の１０進数の表記ではなくて，次のような指数表記で表すれば 無駄な 000...000 という桁を表記しなくてもよくなる． 1234567890000000000000
Count 1 in bits - Qiita
Problem: Count 1 in 32 bits 00000000000000000000000000001110 answer is 3. Bruteforce approach iterate from whole bit and count 1. if input is n bits, the answer is O(n) Better approach Utilizing bit operation. x is the input. x - 1 would find the first set bit from the end, and then set it to 0, and set all the bits following it.
パッケージユーザーのための機械学習(12)：Xgboost (eXtreme Gradient Boosting) - 六本木で働くデータサイエンティストのブログ
今やKaggleやKDD cup以下名だたる機械学習コンペで絶大な人気を誇る分類器、Xgboost (eXtreme Gradient Boosting)。特にKaggleのHiggs Boson Machine Learning Challengeの優勝チームが駆使したことで有名になった感があるようで。 その実装ですが、C++ベースで高速化したものにRとPythonのラッパーをつけたものが既にGitHubで公開されています。 Rパッケージである{xgboost}のインストールについての注意事項は前回の記事に書いていますので、インストールの際はご参考にしていただければと。 さて。これだけ大人気の分類器となると国内外問わず色々な解説記事に溢れておりまして、例えば日本語ブログでもこれだけの記事が既に出てます。 勾配ブースティングについてざっくりと説明する - About connecting
E-musu's Tech Memorandum
1. 導入 これはMetropolis Hastings Algorithmについてまとめたものです． この手法はマルコフ連鎖モンテカルロ法の1つです． マルコフ連鎖モンテカルロ法とは多次元の確率変数を発生させるサンプリング方法の1つであり，複雑化しているモデルの推定方法として多くの分野で使用されています． そこでMCMCを使うことになった背景やその仕組みについて考えていき，メトロポリス・ヘイスティングス法やそれに類する手法を説明します． 2. 共役分布を用いたパラメータ推定 ベイズ統計ではパラメータ推定などの統計的計算は基本定理 \begin{equation} f\left( \theta | x \right) = \frac{f\left( x | \theta \right)f\left( \theta \right)}{f\left( x \right)} \propto f\
年の瀬！リアルタイム通信ゲームサーバ勉強会
FINAL FANTASY XVにおけるPhoton利用事例 - Photon運営事務局 GTMF 2018 OSAKA / TOKYO
住宅の外観画像と内装画像をディープラニングして、リコメンドをつくってみる | Tech Blog - リクルート住まいカンパニー
こんにちは。データソリューショングループの李です。 データソリューショングループでは、ウェブリコメンドやターゲティングバナー設置のアルゴリズム実装、賃料の予測、投函チラシの配布エリア最適化など、こんにちは。データソリューショングループの李です。 データソリューショングループでは、ウェブリコメンドやターゲティングバナー設置のアルゴリズム実装、賃料の予測、投函チラシの配布エリア最適化など、 機械学習や統計モデリングをつかってサービスの磨きこみをしています。 今回は、SUUMOが持っている建築物の外観画像と内観画像を使って画像分析を行いました。Deep learningを用いた手法や、得られた結果について紹介します。 Deep Learningとは Computer Vision（CV）やAIなどの難易度が高い学習タスクに対して、深い構造*を使って処理する機械学習アルゴリズムセットです。 表
深層学習を読んでいったときのメモ (1. 順伝播型ネットワーク) - Qiita
今回の内容 順伝播型ネットワーク 深層学習が成り立つ仕組み、問題に対するアプローチについて簡単に触れます。 はじめに 最近、深層学習について興味があって、理解した内容を書いていこうと思います。 今回の教科書は深層学習という本で勉強します。教科書を丸っきり一緒のことは書かないです。 この本の内容は大きく分けて以下のものがあります。 順伝播型ネットワーク 確率的勾配降下法 誤差逆伝播法 自己符号化器 畳込みニューラルネット 再帰型ニューラルネット ボルツマンマシン 順番にメモを書いていきます。今回は順伝播型ネットワークをメモを書きます。 1. 順伝播型ネットワーク 1.1 順伝播型ネットワークについて 順伝播型ネットワークとは、情報が入力側から出力側に一方向にのみ伝搬させていくネットワークのことです。 (他の文献では多層パーセプトロンともいうみたいです。) 下の図は入力が4個あって、出力も4個
Understanding Consensus and Paxos in Distributed Systems
A distributed auction Take 1: Auction! Correctness properties Take 2: Auction! Take 3: Auction! Agreement: Why it works Termination: Why it doesn’t (always) work. FLP Ghost The Paxos Algorithm Phase 1- Prepare Phase Phase 2 - Accept Phase Computers can sometimes be unexpectedly tricky. Having them accomplish seemingly rudimentary tasks can be a lot more complicated than we would expect. One exampl
整数の公式でフィボナッチ数列を求める | POSTD
(注：2020/10/01、2017/6/10、いただいたフィードバックを元に翻訳を修正いたしました。) 次のコードを用いると、なんとフィボナッチ数列が生成できます。 def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) この記事では、その導き方と振る舞いを説明しましょう。 具体的な説明に入る前に、背景としてフィボナッチ数列の概要と計算方法を駆け足で紹介します。すでに数学の専門知識がある方は、導入部分はほとんど飛ばして、「母関数」のセクションをざっと読んでから、「整数の公式」に進んでいただいて構いません。 概要 フィボナッチ数列とは、言わずと知れた以下の数列です。 \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\] この数列の \(n\) 番目
Terrain-Adaptive Locomotion Skills Using Deep Reinforcement Learning
Terrain-Adaptive Locomotion Skills Using Deep Reinforcement Learning Transactions on Graphics (Proc. ACM SIGGRAPH 2016) (to appear) Xue Bin Peng Glen Berseth Michiel van de Panne University of British Columbia Reinforcement learning offers a promising methodology for developing skills for simulated characters, but typically requires working with sparse hand-crafted features. Building on re
Recommender Systems survey - Knowledge-Based Systems (2013) 読んだ (1/2) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 長いので2回に分ける ##概要と読む動機 2012年10月投稿，2013年4月採択の推薦システムのサーベイ論文 最新の技術動向の流れを確認したくて読むことにした 著者らもこのサーベイは過去のものと違い，有名な手法ではなく推薦システムのの進化に焦点を当てると述べているので期待がもてる ##推薦システムのサーベイ論文について イントロに書かれている内容の気になったところをメモ 近年の推薦システムの適用領域について http://dl.acm.org/citation.cfm?id=2181690 初期の推薦システムの方式について http:
Globally Normalized Transition-Based Neural Networks
We introduce a globally normalized transition-based neural network model that achieves state-of-the-art part-of-speech tagging, dependency parsing and sentence compression results. Our model is a simple feed-forward neural network that operates on a task-specific transition system, yet achieves comparable or better accuracies than recurrent models. We discuss the importance of global as opposed to
MNIST for ML Beginnersの数学的な意味合い - neuralnetな日記
Tensor flowの初めの一歩のチュートリアルであるMNIST For ML Beginners について、数学的な意味合いを書いてみようと思います。 (ブログに不慣れなもので、修正/継ぎ足しながら公開していくことをお許しください) まず、このチュートリアルで実行していることは、 入力がn次元の配列 (は実数)が複数個あった時 、個々の出力 ()を得る写像を用意して、出力が 個々のに対する解 (あるz=1以外はz=0) に近い結果を得れるように、Fを最適化することです。 ここで、の各要素 は実数と書きましたが、これは概念上の話であり、プログラムの実装上ではfloatになります。以後、集合（つまり配列）の要素は数学上は実数ですが、プログラム上はfloatであると考えて下さい。は、となるm個の(実数の)集合です。また任意の要素は0以上であり、したがって、は0から1までの値をとることになりま
A beginner's guide to Big O Notation - Rob Bell
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. Anyone who’s read Programming Pearls or any other Computer Science books and doesn’t have a grounding in Mathematics will hav
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Algorithm Visualizer
Consulはなめらかか？
なめらかなシステムのアイデアと設計概要 / namerakad-idea-design
30 分でわかるAdam
