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
AtCoder Beginner Contest 037に挑戦した話 - Qiita
きっかけ 就職して、スキルアップのためにと思いプログラミングコンテストに参加しています。今回はその１つである「AtCoder Beginner Contest (ABC) 037」に参加してみました。 自分の肌で感じた難易度としては |問題|難易度| |:--:|:--:|:--:| |A|易| |B|やや易| |C|やや難| |D|難| という感じでした。Dは時間内に終えることができませんでした。。。しかしなんとか終了後１時間ほどで正解できました。ちかれた。。。。 一応手元の環境で動くものができても、TLE(実行時間制限超過)などへの対処を考えるのが難しかったです。 なお、使用言語はC++です。 自分の解法 [ABC#037 コンテストページ]http://abc037.contest.atcoder.jp/ 問題はこちら。問題概要はこのページの問題の要約です。 A問題 問題概要 １個A
kisa12012の日記
こんにちは．Machine Learning Advent Calendar (MLAC) 2013の14日目を担当します，[twitter:@kisa12012]です．普段は博士学生として，各地を放浪しながら機械学習の研究をしてます．今回の記事はボストンで執筆しています．現地時間(EST)での締切は守ったのでセーフ…ですよね？ 本日は機械学習の技術的な内容の話ではなく，筆者が実践している機械学習関連の情報収集方法について纏めます*1．大きく分けて，学会情報の管理・論文情報の収集・その他の三種について述べたいと思います．今回のトピックの多くは他の分野にも通用する話になっているかと思います．他の分野の方がどのように情報収集されているのかも気になるところです． 学会情報の管理 まずは学会情報の管理についてです．機械学習に関連するカンファレンスは（特に近年乱立気味で）非常に沢山あります．全てをチ
僕はもう、そんなにナイーブじゃないんだ - Qiita
Machine Learning Advent Calendarの20日目です。 はじめに Naive Bayes(NB)とその改良版のTransformed Weight-normalized Complement Naive Bayes(TWCNB)、Averaged One-Dependence Estimators（AODE）という手法について解説と実装を書きます。 Naive Bayes NBはベイズの定理と特徴変数間の独立性仮定を用いた分類器です。文書のカテゴリ分類等でよく利用されます。 NBは、事例$X$に対し$P(y|X)$が最大となるクラス$y$を分類結果として返します。$P(y|X)$は、ベイズの定理を用いて、以下のように展開が可能です。
Complement NaiveBayesを実装したよ - kisa12012の日記
レッドブルとカレーが美味しい季節になりました． 前回，ナイーブベイズを実装した後， 「どうせならComplement NaiveBayesも実装してしまいなよ．」 という天からの声が聞こえた気がしたので，実装してみました． Complement NaiveBayesとはなんぞや，という方は，以下の記事で非常に丁寧に解説されているので，そちらを参照ください． こちらでも簡単に説明すると，Complement NaiveBayesはそのクラスに「属しない」記事を用いて，文書に対する尤度を計算します．そして，尤度が一番「低い」クラスを予測結果として出す手法です．NaiveBayesと反対ですね．その性質上，2クラスの場合はNaiveBayesとComplement NaiveBayesは結果が一致します． 新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ
最大マージン kNN と SVM の関係: kNN も最近はがんばっています - 武蔵野日記
先日書いた機械学習における距離学習の続き。 kNN (k-nearest neighbour: k 近傍法)は Wikipedia のエントリにも書いてある通り、教師あり学習の一つで、あるインスタンスのラベルを周辺 k 個のラベルから推定する手法。memory-based learning と呼ばれることもある。単純に多数決を取る場合もあれば(同点を解決する必要があるが)、近いインスタンスの重みを大きくする場合もあるのだが、いずれにせよかなり実装は単純なので、他の機械学習との比較(ベースライン)として使われることも多い。 簡単なアルゴリズムではあるが、1-NN の場合このアルゴリズムの誤り率はベイズ誤り率(達成可能な最小誤り率)の2倍以下となることが示されたり、理論的にもそれなりにクリアになってきているのではないかと思う。また、多クラス分類がちょっと一手間な SVM (pairwise に
Factorization Machines (ICDM 2010) 読んだ - 糞糞糞ネット弁慶
Factorization Machines (pdf) Factorization Machines with libFM (TOIS, pdf) CriteoやAvazuの Click-through rate コンペでも良い成績を残している (GitHub - guestwalk/kaggle-2014-criteo, GitHub - guestwalk/kaggle-avazu) Field-aware Factorization Machinesを知る前にまずは Factorization Machnes (以下FM) の論文を読む事にした． FMの紹介は他の人(Factorization Machinesについて調べてみた，Matrix Factorizationとは)も既に書いているが，それらを読んでもどうにも自分にはピンとこなかった．具体的には， 交互作用を考えようとする
Sublime Textの「あいまい一致」をリバースエンジニアリング | POSTD
Sublime Text は、私のお気に入りのプログラミング用テキストエディタです。 Sublime Textで気に入っている特徴の1つは、あいまい検索アルゴリズムです。ファイルや関数の検索が超高速なのです。これまで多くの人が、インターネット上で、この仕組みについて質問していましたが、満足の行く回答はありませんでした。そこで、私が自らこれを解明することにしました。 全部読むのが面倒な方へ 本文を読まずに最終結果だけ知りたいですか？ 了解！ 私は、あなたを責めたりしませんよ。 インタラクティブなデモ： こちらをクリック ソースコード： C++ 、 JavaScript Sublime Textの仕組み Sublime Textのあいまい一致とは何でしょうか。そして、なぜそれはそんなに賢いのでしょうか。聞いてくれてうれしいです。 Sublime Textには、2つの非常に便利なナビゲーション関
コンピュータサイエンティストはソートアルゴリズムの中身を知るべきか
講義でソートアルゴリズムを教えることになったので，改めてソートアルゴリズムの勉強をしなおした．僕がソートアルゴリズムをちゃんと勉強したのは1990年代前半で，教科書はニクラウス・ヴィルト「アルゴリズムとデータ構造」（第2版）だった．サンプルコードがModula-2で書かれているアレだ． N. ヴィルト「アルゴリズムとデータ構造」C++ STL の解説を読むなどしてソートアルゴリズムの改良が進んでいるのは知っていたが，再勉強してはじめて，未だに新発明があることを知った．例えば図書館ソートなど，恥ずかしながら名前さえ知らなかった．勉強は大事だ． とは言え，そもそもソートアルゴリズムの中身をどのぐらいまで知っておけば，コンピュータサイエンティストとして十分なのだろう，あるいはエンジニアとして十分なのだろうという疑問は残る． 例えば，超優秀なC++プログラマでもGNUの std::sort の中身
確率的勾配降下法+α の話をしました - kisa12012の日記
先日PFIセミナーにて，「SGD+α: 確率的勾配降下法の現在と未来」というタイトルで発表をしました！発表の機会を設定して頂いたPFIの皆様，ありがとうございます．スライドは以下になります． SGD+α: 確率的勾配降下法の現在と未来 from Hidekazu Oiwa 確率的勾配降下法(SGD)はシンプルで大規模データから”そこそこの”解を得るには非常に有効なアルゴリズムです．一度自分で実装してSGDを回してみたことのある人も多いと思います． 一方で 結局ステップ幅の設定が大変 正規化とか前処理しないとそれほど上手く動いてくれない などなどSGDには欠点も多く，たくさんの人が使う際に苦しめられてきた現実もあるのではないでしょうか． 今回の発表では，SGDの欠点を克服するため，およびさらなる長所を加えるための，最新の+α拡張研究について紹介しました． 内容は， ステップ幅設定に今後悩まさ
クラスタリングの不可能性定理について - Qiita
背景 機械学習の手法のひとつであるクラスタリングは、データの特徴により分類を行います。クラスタリングには様々な手法がありますが、その多くは距離関数を利用して有限個の点を分類します。 昨今、IT業界で機械学習がブームになっていますが、クラスタリング手法の能力について、理論的な視点からあまり言及されていないのではないかと思います(あくまでも、IT業界内の話)。利用している手法で「できること」だけでなく、「できないこと」をハッキリさせるのも重要なことだと思います。実際、Kleinbergさんの論文1などで、クラスタリングの能力・定式化について研究されています。 Kleinbergさんの論文1では、クラスタリングの特徴の中からスケール不変性、豊富性、一貫性を取り上げ、3種すべてを満たすクラスタリングは存在しない、という定理が示されています。これを**クラスタリングの不可能性定理(Impossibi
Pythonで2変数関数に対してニュートン法を用いる - minus9d's diary
前回、Pythonで2変数関数に対して最急勾配法を用いる - minus9d's diaryにて、2変数関数に対する最急勾配法を Pythonで実装しました。 今回は、最急勾配法よりも収束が早いと言われるニュートン法を実装してみます。私の理解が正しければ、ニュートン法では、初期点が与えられたとき、その点の近くにあるStationary point(停留点)、すなわち微分が0になる点を探します。微分が0になる点なので、必ずしも極値に収束するとは限らず、鞍点に収束する可能性もあります。 ニュートン法の更新式は以下の通りです。 ここでは学習率、はヘッセ行列です。変数名は教科書「言語処理のための機械学習入門 (自然言語処理シリーズ) 」に従っていますが、この教科書は版によってはニュートン法の式が誤っているので注意。 目的関数は前回と同じくです。の極小値の一つを求めるのが目的です。 実装コード Py
Import APIとFuzzy Hashingでマルウエアを分類する ～impfuzzy～(2016-05-09) - JPCERT/CC Eyes
Top > “マルウェア”の一覧 > Import APIとFuzzy Hashingでマルウエアを分類する ～impfuzzy～(2016-05-09) 一般に、マルウエア検体の調査は、既知のマルウエアかどうかを判別することから始めます。データベース化された多数の既知のマルウエアと調査検体との比較を高速に実行するために、ハッシュ関数をマルウエア検体に施して得られたハッシュ値が利用されます。 ハッシュ関数の中でも、MD5やSHA1などの伝統的なハッシュ関数の場合には、入力データが1ビットでも異なれば、まったく異なるハッシュ値になりますので、完全に同じではないが類似した既知の検体があれば、既知のマルウエアと判定したい場合には役に立ちません。 現在では、カスタマイズされた上で攻撃に使われるマルウエアがほとんどであるため、カスタマイズされた検体を類似していると判断できるようなハッシュ関数が望まれ
bit vector + popcntでバイナリ素性のk-NN分類器を高速化する - シリコンの谷のゾンビ
こんばんは @sleepy_yoshi です．Machine Learning Advent Calendar 2012 の11日目を担当します．サモア時間ではまだ12月11日なので間に合いましたね．今日はバイナリ素性ベクトルの内積計算にSSE4.2のpopcnt命令を用いて高速化することでk-NN分類器を高速化する話について書きます． このブログでは普段である調で書いていますが，今日はなんとなくですます調で書きます． k-NN (k Nearest Neighbor) 分類器はラベルを予測したい事例に対して，訓練データとして与えられたラベル付き事例集合の中からk近傍の事例のラベルを用いて予測する，という分類器です．k近傍を求めるために，訓練データに含まれる事例全てに対する類似度を計算する必要があります．類似度には様々な尺度が利用されますが，ここでは内積とします．そのためk個の近傍を発見す
x86x64 SSE4.2 POPCNT
“Symbolic bounds analysis of pointers, array indices, and accessed memory reg...
popcount
ちょっとわけあってpopcountを調べてた。 以前から、ビットを数える・探すアルゴリズムを参考に int numofbits5(long bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff); } とかやってたわけです。この計算の意味は、 1行目で、2ビットずつを足しこみ2ビット単位で1
Binary Hacks と 64bit popCount 問題 | TAKESAKO @ Yet another Cybozu Labs
高林さん、オライリーさん、ありがとうございます。 ちなみにetoさん情報によると、明日11/10は「いいバイナリの日」らしいです。 11 → いい 10 → バイナリ Binary Hacks の発売日は 11/11 で、ビットが全部立っている非常に縁起の良い日です。 縁起を担ぐためにも、いいバイナリの日に Binary Hacks を注文して、発売日に書店に行って本を見かけたら 11 冊買いましょう。 x86 パフォーマンスチューニング さて、最後の HACK #100「文献案内」でマイクロプロセッサアーキテクチャマニュアルが紹介されていましたが、 x86のパフォーマンスチューニングつながりということで、 ちょうど今日ラボの社内掲示板で盛り上がった話題をこちらでも共有したいと思います。 * popCount 問題 64bitの数値の中で1になっているビット数を数える popCount64
GoのGCを追う
Go1.5とGo1.6でGoのGCのレイテンシが大きく改善された．この変更について「ちゃんと」理解するため，アルゴリズムレベルでGoのGCについて追ってみた． まずGoのGCの現状をパフォーマンス（レイテンシ）の観点からまとめる．次に具体的なアルゴリズムについて，そして最後に実際の現場でのチューニングはどうすれば良いのかについて解説する． GoのGCの今 最初にGoのGCの最近の流れ（2016年5月まで）をまとめる． Go1.4までは単純なStop The World（STW）GCが実装されていたがGo1.5からは新たなGCアルゴリズムが導入された．導入の際に設定された数値目標は大きなヒープサイズにおいてもレイテンシを10ms以下に抑えることであった．Go1.5で新たなアルゴリムが実装されGo1.6で最適化が行われた． 以下は公開されているベンチマーク．まずはGo1.5を見る． Gophe
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
機械学習と深層学習の数理
意外と深い「平均」の世界
