強化学習のアルゴリズムの中で，複雑な環境の探索のために内発的報酬を用いているアルゴリズムを紹介した資料です．未知の状態への探索を促していることから「好奇心」を用いた探索とも呼ばれます．元々は別の場所で公開していた資料でしたが，いくつかの修正を加えて，こちらに改めてアップしました．
ICPC国内予選F解説
強化学習のアルゴリズムの中で，複雑な環境の探索のために内発的報酬を用いているアルゴリズムを紹介した資料です．未知の状態への探索を促していることから「好奇心」を用いた探索とも呼ばれます．元々は別の場所で公開していた資料でしたが，いくつかの修正を加えて，こちらに改めてアップしました．
ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
How does Shazam work | Coding Geek
Have you ever wondered how Shazam works? I asked myself this question a few years ago and I read a research article written by Avery Li-Chun Wang, the confounder of Shazam, to understand the magic behind Shazam. The quick answer is audio fingerprinting, which leads to another question: what is audio fingerprinting? When I was student, I never took a course in signal processing. To really understan
Radix sort | Interesting
Ed’s discrimination package seemed very interesting to me. I was vaguely aware of sorting algorithms not based on comparison but I didn’t realize that you could achieve such impressive asymptotics with them. Radix sort seemed quite simple so I wanted to see how well it would perform. There’s no point in explaining the algorithm here because I doubt I would do a better job than other people on the
Fast Approximate Logarithms, Part III: The Formulas
Fast Approximate Logarithms, Part III: The Formulas In this post I finally get to the punch line and construct a set of approximations to (actually ) that cover a range of speeds and accuracies. As execution time decreases, so does the accuracy. You can choose an approximation with a tradeoff that meets your needs. When making a fast but approximate function, the design parameter is the form of th
クーポンコードの打ち間違えを防ぐために工夫した話 - クックパッド開発者ブログ
こんにちは。会員事業部ビジネス開発グループの高田です。 クックパッドは今年、株主優待制度として、プレミアムサービス一年間無料クーポンを贈呈しました。本エントリではクーポンコードを打ち間違えて、意図せず他の人のクーポンコードを使用するのを防ぐために工夫した話をご紹介します。 はじめに クーポンコードは入力のしやすさを優先して数字だけの文字列にしました。はじめは rand 関数を使って生成しようとしていたのですが、数字の打ち間違えや順序間違いで、意図せず誤使用してしまうのを防ぐためにチェックサムを加えるのがいい、と同僚から助言をもらいました。 いくつか調べて見たところ、Luhn アルゴリズムが上記を満たしていたので利用することにしました。 Luhn アルゴリズムの利用 Luhn アルゴリズムとは、誤り検出のためのチェックサム符号で、1 桁の間違いや隣接する数字の順序間違いを検出できるという特徴
FuzzyFinder - in 10 lines of Python
Introduction:FuzzyFinder is a popular feature available in decent editors to open files. The idea is to start typing partial strings from the full path and the list of suggestions will be narrowed down to match the desired file. Examples: Vim (Ctrl-P) This is an extremely useful feature and it's quite easy to implement. Problem Statement:We have a collection of strings (filenames). We're trying to
Levenshtein automata can be simple and fast
A few days ago somebody brought up an old blog post about Lucene’s fuzzy search. In this blog post Michael McCandless describes how they built Levenshtein automata based on the paper Fast String Correction with Levenshtein-Automata. This proved quite difficult: At first he built a simple prototype, explicitly unioning the separate DFAs that allow for up to N insertions, deletions and substitutions
JPS+: Over 100x Faster than A*
This is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726. You've been logged out of GDC Vault since the maximum users allowed for this account has been reached. To access Members Only content on GDC Vault, please log out of GDC Vault from
My Favorite Algorithm: Metropolis-Hastings
I’m writing this post because I feel like any computational scientist should have a favorite algorithm, and in my research I have run into this particular algorithm again and again and every time it impresses me. I am also writing this because I googled “What is your favorite algorithm” and was surprised to find that no one mentioned it in the top results. Few algorithms in computational physics h
Game of Life, hash tables and hash codes
Introduction: The Game of Life You can hardly find a programmer who heard about Conway’s Game of Life but has never tried to program it. Google programmers are no exception, otherwise they wouldn’t have included a Life interpreter into the respective search result page. I am no exception either. The first time I tried to do it was on one ancient computer, which you are unlikely to see even in a mu
Fast Approximate Logarithms, Part I: The Basics
Performance profiling of some of the eBay code base showed the logarithm (log) function to be consuming more CPU than expected. The implementation of log in modern math libraries is an ingenious wonder, efficiently computing a value that is correct down to the last bit. But for many applications, you’d be perfectly happy with an approximate logarithm, accurate to (say) 10 bits, especially if it we
Pointer-less Scapegoat Trees - Paul Khuong: some Lisp
I’m trying something new this week: gathering a small group after work for 90 minutes of short talks and discussions. We’ll also have one longer slot because not everything fits in a postcard, but my main goal is really to create opportunities for everyone to infect us with their excitement for and interest in an idea or a question. I successfully encouraged a couple people to present, although ma
Curtis Lassam - Hash Functions and You: Partners in Freedom - PyCon 2015
"Speaker: Curtis Lassam Our trusty friend, the hash function, is as crucial to programming as linked lists or recursion, but it doesn't always get the press that it deserves. We're going to talk about hash functions, some data structures involving hash functions, the stately bloom filter, and the security implications of password hashing. Slides can be found at: https://speakerdeck.com/pycon2
LCA and RMQ ~簡潔もあるよ！~
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
最小カットについて - よすぽの日記
わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、 なんかいい感じのグラフを作ったらなんかそれの最小カットが答え というのがあります 最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り分けるという問題を考えます。燃やすと埋めるでも大丈夫です 最小カットで解ける問題というのは、実は 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある 罰金の最小値は？ という問題だけです。 これの解法は、 「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る SからTに最大流 流せた量が答え 処理できる条件は「Xが赤で、Y
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability
Fast Approximate Logarithms, Part II: Rounding Error
Home
Ideal finger 001 — log erratique