SymSpell対BK木：100倍速い文字列のあいまい検索とスペルチェック | POSTD
注釈：500,000単語収録の辞書内における1,000単語の検索時間 X:最大編集距離 Y:検索時間/ms 従来、スペル修正や文字列のあいまい検索には、 BK木 が適していると言われてきました。しかし、これは本当でしょうか。 また、 スペル修正に関する私のブログ に寄せられたコメントには、BK木が、あいまい検索のためのデータ構造として優れていると言及されていました。 そのような経緯から、今回、BK木と他の選択肢のベンチマークを取って比較してみようと思い立ったわけです。 近似文字列検索アルゴリズム 近似文字列検索では、文字列リスト内の文字列を検索し、特定の 文字列メトリック に従って、それに近い文字列を返します。 文字列メトリックは多数あり、例えば レーベンシュタイン距離 、 Damerau-Levenshtein距離 、 ハミング距離 、 ジャロ・ウィンクラー距離 、 Strike a m
私たちはいかにして環状線で”悪さをする列車”を捕まえたか | プログラミング | POSTD
文：Daniel Sim 分析：Lee Shangqian、Daniel Sim、Clarence Ng ここ数ヶ月、シンガポールのMRT環状線では列車が何度も止まるものの、その原因が分からないため、通勤客の大きな混乱や心配の種となっていました。 私も多くの同僚と同じように環状線を使ってワンノースのオフィスに通っています。そのため、11月5日に列車が止まる原因を調査する依頼がチームに来た時は、ためらうことなく業務に携わることを志願しました。 鉄道運営会社SMRTと陸上交通庁（LTA）による事前調査から、いくつかの電車の信号を消失させる信号の干渉があり、それがインシデントを引き起こすことが既に分かっていました。信号が消失すると列車の安全機能である緊急ブレーキが作動するため、不規則に電車が止まる原因となります。 しかし8月に初めて発生した今回のインシデントは、不規則に起こっているように見えるた
H.264の秘密 | POSTD
(編注：2020/08/18、いただいたフィードバックをもとに記事を修正いたしました。) (2016/12/11、いただきましたフィードバックをもとに翻訳を修正いたしました。) H.264は、動画圧縮コーデックの標準規格です。ネット上の動画、Blu-ray、スマホ、セキュリティカメラ、ドローンなどなど、今やあらゆるところでH.264が使われています。 H.264は注目すべき技術のひとつです。たったひとつの目標、つまりフルモーションビデオの送信に要するネットワーク帯域を削減することを目指した30年以上の努力の結晶なのです。 技術的な面でも、H.264はとても興味深い規格です。この記事では、その一部について概要レベルでの知識を得られることでしょう。あまり複雑だと感じさせないようにするつもりです。今回おはなしする概念の多くは動画圧縮全般にあてはまるものであり、H.264に限ったものではありません
畳み込みニューラルネットワークの仕組み | POSTD
(編注：2016/11/17、記事を修正いたしました。) ディープラーニングの分野でテクノロジの進化が続いているということが話題になる場合、十中八九畳み込みニューラルネットワークが関係しています。畳み込みニューラルネットワークはCNN（Convolutional Neural Network）またはConvNetとも呼ばれ、ディープニューラルネットワークの分野の主力となっています。CNNは画像を複数のカテゴリに分類するよう学習しており、その分類能力は人間を上回ることもあります。大言壮語のうたい文句を実現している方法が本当にあるとすれば、それはCNNでしょう。 CNNの非常に大きな長所として、理解しやすいことが挙げられます。少なくとも幾つかの基本的な部分にブレークダウンして学べば、それを実感できるでしょう。というわけで、これから一通り説明します。また、画像処理についてこの記事よりも詳細に説明
ゲームをプレイするアルゴリズムを選択するためのアルゴリズム | POSTD
この記事は当初、私たちの論文を紹介する簡単な投稿のつもりだったのですが、最終的に膨れ上がってしまいました。結果として、十分な内容が詰まったものになったと思います。 ビデオゲームは、人工知能アルゴリズムをテストする最良の方法ではないでしょうか。 少なくとも私は以前に、このことについて（ある程度の分量で）持論を展開しました。 ビデオゲームでは可能で、例えばロボットにおける問題などでは不可能なものの1つとして、同じアルゴリズムをたくさんのゲームで素早く簡単にテストできるということが挙げられます。ちなみにそのことは、 他のゲームベースのAIテストベッドに対して一定の優位性 を持つ The General Video Game AI Competition （GVG-AI）の指針となる原則の1つでもあります。 GVG-AIフレームワークに実装された数種類のゲーム。 現時点では、実質的にすべての種類の
勾配降下法の最適化アルゴリズムを概観する | POSTD
(編注：2020/10/01、2016/07/29、いただいたフィードバックをもとに記事を修正いたしました。) 目次： さまざまな勾配降下法 バッチ勾配降下法 確率的勾配降下法 ミニバッチ勾配降下法 課題 勾配降下法を最適化するアルゴリズム Momentum(慣性) Nesterovの加速勾配降下法 Adagrad Adadelta RMSprop Adam アルゴリズムの可視化 どのオプティマイザを選ぶべき？ SGDの並列化と分散化 Hogwild! Downpour SGD SGDのための遅延耐性アルゴリズム TensorFlow Elastic Averaging SGD 最適化されたSGDに対する更なる戦略 シャッフル学習とカリキュラム学習 バッチ正規化 早期終了 勾配ノイズ 結論 参考文献 勾配降下法は、最適化のための最も知られたアルゴリズムの1つです。これまではニューラルネット
深層強化学習：ピクセルから『ポン』 – 前編 | POSTD
(訳注：2016/6/28、記事を修正いたしました。) 本記事は、もう随分と前から投稿したいと思っていた強化学習（RL）に関するものです。RLは盛り上がっています。皆さんも既にご存知のこととは思いますが、今やコンピュータは ATARI製ゲームのプレイ方法を自分で学習する ことができ（それも生のゲーム画像のピクセルから！）、 囲碁 の世界チャンピオンにも勝つことができます。シミュレーションの四肢動物は 走って飛び跳ねる ことを学習しますし、ロボットは明示的にプログラミングするのが難しいような 複雑な操作のタスク でも、その実行方法を学習してしまいます。こうした進歩はいずれも、RL研究が基となって実現しています。私自身も、ここ1年ほどでRLに興味を持つようになりました。これまで、 Richard Suttonの著書 で勉強し、 David Silverのコース を通読、 John Schulm
Blue. No! Yellow! : プログラミング言語の進歩史と生産性にまつわる問答 | POSTD
世界初のプログラム内蔵方式コンピュータに搭載された、最初のプログラムを書くのに使われた言語は何だったでしょうか？ もちろん、バイナリの機械語です。 なぜですか？ えー、当然ながら、シンボリックアセンブラがなかったからです。最初期のプログラムは、バイナリで書かなければなりませんでした。 バイナリの機械語と比較して、アセンブリ言語でプログラムを書くと、どのくらい簡単ですか？ ずっと 簡単です。 数字を言ってください。何倍ぐらい簡単ですか？ えー、まあ、アセンブラは、あなたの代わりに面倒な事務処理を全てしてくれますからね。つまり、全ての物理アドレスの計算です。全ての物理的な命令を構築するわけです。あなたが範囲外にアドレス指定するなど、物理的に不可能なことをしないよう確認します。そして、簡単にロードできるバイナリの出力を生成します。 それによって、軽減されたワークロードは、 膨大 です。 どのくら
手続き型のダンジョン生成アルゴリズム | プログラミング | POSTD
この投稿では、以前に TinyKeepDev が こちら で述べたランダムなダンジョンを生成する技法について説明しようと思います。元の投稿に比べて、もう少し具体的に話を進めるつもりです。まずは、以下に示したアルゴリズムの一般的な動作をご覧ください。 部屋の生成 はじめに、幅と高さを持つ部屋を円の中にランダムに配置しましょう。TKdevのアルゴリズムは、各部屋のサイズを生成するのに正規分布を用いています。これは一般的にとてもいいアイデアです。なぜかと言うと、これによってより多くのパラメータを扱うことができるようになるからです。幅/高さの平均と標準偏差間の異なる比率を選ぶと、通常は見た目の違うダンジョンとなります。 ここで実行すべき関数は getRandomPointInCircle です。 function getRandomPointInCircle(radius) local t = 2
プログラミングコンテストで、C++を使って全ての問題を解くのに必要なアルゴリズムは何ですか？ | POSTD
これが私の提案するリストです。必要とされるアルゴリズムや概念のほとんどが挙げられています。いくつかの要素はアルゴリズムではなかったり（フェイクや状態、関心事など）、重複していたりもします。 最後に1つ、アドバイスを。 知識を蓄える前に、まずは思考能力を鍛えることを重要視しましょう。これはコンテストのみならず、あなた自身の将来にも役立ちます。思考能力を鍛えるには、アルゴリズムではなく純粋な思考を必要とする、アドホックを使いこなせるようになりましょう。 topcoderのDiv2とCodeforcesのDiv2の2つに集中することも効果的だと思います。どちらも、低いレベルから問題に取り組んでいきましょう。例えば、Div2-250をマスターしてからDiv2-500に取り組む、などです。
眼鏡なしのコードレビュー | POSTD
例えば、あなたが驚くほど聡明な開発チームのメンバーで、コードレビューのみに一日の時間を確保しているとします。しかし作業を開始して2時間後、眼鏡を忘れてきてしまい、午前中はぼんやりとしたカラフルな表示を見つめていただけだったということに気づいたとします。さて、あなたはどうしますか? 家まで歩いて10分もかからないし、天気も良ければ、眼鏡を取りに帰るのが一番です。でも朝家を出るとき、攻撃的なスズメバチの群れが眼鏡の置いてある部屋に巣を作って、邪魔されたくない様子だったらどうしますか？ そういう時はもちろん、コンタクトレンズを付けてきたふりをして、恥ずかしい思いをしないようにするのがよいでしょう。実際に読むことなく膨大な量のファイルを見分けることができるということを覚えておいて下さい。 参考コード 1 不安の種は隔離するべきだということに誰も異論はないでしょう。そしてもちろん、あらゆるクラスは一
機械学習アルゴリズムへの招待 | POSTD
機械学習の問題 については以前に紹介したので、次はどんなデータを収集し、どんな機械学習アルゴリズムを使うことができるのかを見ていきましょう。本投稿では、現在よく使用されている代表的なアルゴリズムを紹介します。代表的なアルゴリズムを知ることで、どんな技法が使えるかという全体的なイメージもきっとつかめてくるはずですよ。 アルゴリズムには多くの種類があります。難しいのは、技法にも分類があり拡張性があるため、規範的なアルゴリズムを構成するものが何なのか判別するのが難しいということですね。ここでは、実際の現場でも目にする機会の多いアルゴリズムを例にとって、それらを検討して分類する2つの方法をご紹介したいと思います。 まず1つ目は、学習のスタイルによってアルゴリズムを分ける方法。そして2つ目は、形態や機能の類似性によって（例えば似た動物をまとめるように）分ける方法です。どちらのアプローチも非常に実用的
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
