ICFPC 2016 参加記 - wataの日記
運悪く日程が被ったDCJ決勝は棄権し今年もいつものチームでICFPCに参加．メンバーと役割分担，問題概要はchokudaiの記事を参照．ソルバの実行結果ログなどから思い出したところによると，以下の様に３日間作業した． 一日目(Lightning) 公式Twitterの発言から関数型ゲーかと思いきや，折り紙の折り方を求める問題だった．foldつながり？各チームが解答と問題を両方提出し，他のチームの問題を沢山解けば解くほど，自分のチームの問題が解かれなければ解かれないほどスコアが高いという形式で，ICFPCに本気で挑むキッカケともなった2010年を思い出した．この形式はジャッジの好みに影響されない公平感があって好き．折り紙に関する理論研究が色々あることは有名な事実なので，とりあえず論文をググったりしたが，直接役に立ちそうな知見は得られなかった． 問題を読んでchokudai＆iwiらと相談しな
Batch Normalizationによる収束性能向上 - Qiita
概要 Neural Networkの収束性能を向上させる手法の一つであるBatch NormalizationをTensorFlowで実装し、効果を検証します。 実装 理論については他の方が丁寧に解説してくださっているので、いきなり実装から入ります。 注意点として、Convolutional Layerの扱いを以下の元論文の通りにします。 For convolutional layers, we additionally want the normalization to obey the convolutional property - so that different elements of the same feature map, at different locations, are normalized in the same way. To achieve this, we
第3回 オブジェクト検出してみよう | gihyo.jp
第1回、第2回と画像認識の基礎とOpenCVについて紹介してきました。第3回目の今回は、いよいよ本連載の目玉であるOpenCVを使ったオブジェクト検出に挑戦してみます。 オブジェクト検出の仕組み 基本原理のおさらい オブジェクト検出のプログラムを書き始める前に、そもそもどんな仕組みでオブジェクト検出を行っているのかを理解しましょう。 第1回では画像認識の原理として、学習フェーズと認識フェーズがあることを説明しましたが、OpenCVに実装されているオブジェクト検出プログラムもこの流れに従います。つまり、画像から特徴量を抽出し、学習アルゴリズムによってオブジェクトを学習します（詳しくは第1回を参照してください）。 図1 画像認識の流れ OpenCVに実装されているオブジェクト検出プログラムは、Paul Violaらのオブジェクト検出の研究［1］をベースに、Rainer Lienhartらが
スパムレビュア発見アルゴリズムの評価用データセット - Qiita
概要 スパムレビュア発見アルゴリズムの評価用に， 論文 A Bipartite Graph Model and Mutually Reinforcing Analysis for Review Sites にて作成した 人工データを公開しました．本記事では使い方をまとめます． また，Google Cloud Platform を使った並列評価についてもまとめます． インストール パッケージは PyPI に登録してあるので，pip コマンドでインストールできます． 人工グラフデータの読み込み rgmining-synthetic-datasetには，syntheticパッケージが含まれており， synthetic.load関数とsynthetic.ANOMALOUS_REVIEWER_SIZE定数をエクスポートします． synthetic.load関数は人工レビューグラフデータの読み込みを行
MIP(混合整数計画問題)ソルバーを作ろう！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 目次 第1章では、線形計画問題や整数計画問題についての簡単な説明を行います 第2章では、線形計画問題の代表的な解法であるシンプレックス法についての解説を行います 第3章では、整数計画問題の代表的な解法である分枝限定法についての解説を行います 第4章では、それらの記述のまとめと、おまけテキストについて記述します なお、今回制作したMIPソルバーは、次のURLに置いてあります。 SMIPS(The Smallest MIP Solver) 第1章 概要 何かを最適化したい、と思ったことはありませんか？ 『最短ルートを探したい』『物をうまく詰
FastBDTでの高速化 - Negative/Positive Thinking
はじめに 勾配ブースティング木の高速化はどうすればいいだろうと調べていたら、arxivで流れているのを見かけたのでメモ。 FastBDT: A speed-optimized and cache-friendly implementation of stochastic gradient-boosted decision trees for multivariate classification https://arxiv.org/abs/1609.06119 https://github.com/thomaskeck/FastBDT Stochastic Gradient Boosted Decision Tree(SGBDT) 勾配ブースティングの各イテレーションで、学習データから非復元抽出でサンプリングしたデータを用いる https://statweb.stanford.edu/~j
結託したスパムレビュアを発見するアルゴリズム - Qiita
はじめに オンラインショッピングやレストランレビューサイトにおいて， 結託してレビュー結果が不当に高くまたは低くなるようにダミーレビューを投稿する スパムレビュアーを発見したい． 今回は，2013年に AAAI Conference on Weblogs and Social Media という国際会議で発表された，Fraud Eagle アルゴリズムを実装した． レビューデータ Fraud Eagle では下の図のようなレビューグラフを考える． つまり，レビューを投稿した人（レビュア）とレビューの投稿先（商品）をそれぞれ頂点とし， レビュー関係を枝で表す．レビュー自体は文章でも星何個でも良いが， そのレビューがポジティブなのかネガティブなのか判断できる必要がある． 今回は，レビューは 0 から 1 までの間の数値を取ることにし，0.5 以上ならばポジティブ， そうでなければネガティブと判
KDD'16 論文採択：省メモリなグラフスケッチのデータ構造 - iwiwiの日記
国際学会 KDD 2016 に論文が採択されました．KDD はデータマイニング分野の最も有名な会議です．発表は 8 月にサンフランシスコです．オーラル発表有りの採択です． 今回の論文は "Compact and Scalable Graph Neighborhood Sketching" というタイトルで，私が主著であり，研究室で特任技術専門員としてお手伝いしてもらっていた矢野さんとの共著です．内容はグラフ向けデータ構造 All-Distances Sketches の実用上の問題点である空間使用量を大幅に削減するための新しいデータ構造の提案です．以前に「大規模グラフのコンパクトでスケーラブルな全距離スケッチ」というタイトルで人工知能学会の人工知能基本問題研究会にて議論させて頂いていたものです． 背景：All-Distances Sketches とは？ All-Distances Ske
焼きなまし法の真実 – システム工房コルン
はじめに 焼きなまし法はベター山登りなのか？ 探索空間は本当に高次元なのか？ 採択確率式の正当性 メトロポリス・ヘイスティングス法がうまくいく条件 メトロポリス・ヘイスティングス法と温度 おまけ1 … 遷移先候補をどう提案するか？ おまけ2 … 温度管理について 終わりに 謝辞 はじめに 著者は、TopCoder Marathon Matchesで世界大会決勝へとアメリカに3度招待された。 その3度ともが、予選では強文脈ゲームによる通過であり、焼きなまし法の使えない問題分類だった。 近年、文脈のない探索の出題が増えてきており、焼きなまし法が正解方針であることが多くなっている。 焼きなまし法へと苦手意識を持った著者であったが、出題の傾向がそうであるのなら避けて通れるものでもなく、焼きなまし法の出題であっても単純な殴り合いで1位をもぎ取れるまでになりたいと2年前に決意して、七転八倒を繰り返しな
Algorithm - JavaScript - 新兵の整列(Lining Up Recruits) | Kamimura's blog
Algorithm - JavaScript - 新兵の整列(Lining Up Recruits)
EMアルゴリズム - 画像処理とか機械学習とか
今回は、前回の混合ガウスモデルに引き続き、混合ガウスモデルのパラメータ推定の手法に使えるEMアルゴリズムについて紹介したいと思います。 混合ガウスモデルを例に挙げますので、混合ガウスモデルが分からない方は前回の記事を参照してください。 hiro2o2.hatenablog.jp なぜ最尤推定で解けないか？ 混合ガウスモデルは以下の式で表せました。 何か近似したい確率密度分布（真の分布）がある際に、混合ガウスモデルを使って近似する場合、最も真の分布に近づくような、パラメータが分かれば良いです。 このパラメータの学習に、通常のガウスモデルと同じように最尤推定を用い、対数尤度の最大化のアプローチで解けるでしょうか？ このように、正規分布の和のlogの部分で、微分して0とおく計算が難しくなります。 また、重みを足し合わせて1であるという条件と、共分散行列が正定値であるという条件のもと、を最大にする
混合ガウスモデルとEM - 人工知能に関する断創録
今回は、9.2の混合ガウス分布のところです。混合ガウス分布はK個のガウス分布の線形重ね合わせで表されます。 ここで、π_kを混合係数と言い、k番目のガウス分布を選択する確率を表します。π_kは確率の条件を満たし、すべてのkについて足し合わせると1になります。ここら辺は、2.3.9の混合ガウス分布でも出てきました。この章では、混合ガウス分布を潜在変数zを導入して再定式化しています。zはK次元ベクトルで、K個の要素のうちどれか1つだけ1を取り、他は0、つまり1-of-K表現です。zはデータxがどのガウス分布から生成されたかを表し、下のような分布になります。 そして、式（9.12）のようにこのｚを陽に用いた形でp(x)を求めてもやっぱり混合ガウス分布の式 (9.7) になります（演習9.3）。 つまり、混合ガウス分布を「潜在変数zを含む別の式」で表現できたってことですね。何でこんなことするのか不
EMアルゴリズムを使って多峰型分布をモデル化してみる - Qiita
#概要 標本から得られた分布が多峰型であったとき, 単純なガウス分布でモデル化するのは適切ではありません. 多峰型の分布は複数のガウス分布を組み合わせた混合ガウス分布を使ってモデル化することができます. この記事ではEMアルゴリズムを使って, 混合ガウス分布のパラメータを決定する例を紹介します. #まずは単峰型分布から ##最尤推定 標本を$x_n (n=1,…,N)$とします. ガウス分布の最尤推定によって, 平均と分散を以下の形で求めることができます. # -*- coding: utf-8 -*- import numpy as np import matplotlib.pyplot as plt import matplotlib.mlab as mlab import math #ヒストグラムをプロットする関数 def draw_hist(xs, bins): plt.hist(
リカレントニューラルネットワークの理不尽な効力（翻訳） - Qiita
上記は、普通の RNN の前進パスの仕様を決めます。そのための RNN のパラメータは、３つの行列 $W_{hh}, W_{xh}, W_{hy}$ です。隠れ状態 $self.h$ は、ゼロベクトルで初期化されます。$np.tanh$ 関数はアクティベーションを $[-1, 1]$ の範囲に押しつぶす、非線形性を実現します。どのように作用するのか簡単に述べると：tanh 内に２つの項があります：一方は前の隠れ状態に基づき、他方は現在の入力に基づきます。numpy の $np.dot$ は行列の掛け算です。２つの中間項は加算され、tanh により新たな状態ベクトルに押しつぶされます。数学の表記に慣れているなら、隠れ状態の更新は以下のように記述可能です。$h_t = \tanh ( W_{hh} h_{t-1} + W_{xh} x_t )$ 、ここで tanh は要素ごとに適用されます。
【ゲームAI】基本的な経路探索 - Qiita
#概要 ゲームAIに関して勉強し始めたので，その備忘録． 本記事では基本的な経路探索について記述する． 本記事では，以下の手法について取り上げる． ●ランダムムーブメント ●ブレッドクラム経路探索 ●ウェイポイントナビゲーション なお，本記事では連続的なゲームを想定したサンプルを示す． 離散的なゲームでの上記手法も，考え方は同じである． #参考書 ありきたりではあるが以下の書籍を用いた． ゲーム開発者のためのAI入門 (サンプル) #事前準備 ベクトル計算用の構造体，便利関数の準備と， 角度計算用のマクロの準備を行う． //角度計算用マクロ. #define L_PI (3.1415f) #define L_2PI (6.2830f) #define L_H_DEG (180.0000f) #define L_DEG (360.0000f) #define DEG2RAD(e) ((e)*
Kernel PCA (Principal Component Analysis) の導出 - めもめも
何の話かというと Python Machine Learning: Unlock deeper insights into Machine Leaning with this vital guide to cutting-edge predictive analytics (English Edition) 作者:Raschka, SebastianPackt PublishingAmazon この本のKernel PCAの説明が相当に計算を端折っていて、これは読者もつらいだろぅ。。。と思って途中の計算を端折らずになるべく正確に導出してみました。 ※実対称行列の固有値分解とLagrangeの未定乗数法は前提知識とします。 普通のPCA はじめに、Kernelを使わない普通のPCAを導出します。 データセット の分散共分散行列を とします。この時、 は正定値の実対称行列より、正（もしくは0）
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AdaGradが学習率のスケジューリングを上手く調整してくれる理由 - 理論編 - - Qiita
また巨大数の話
GMMとEMアルゴリズム | 一日一アルゴリズム « FiFiFactory
計算量のはなし（Redisを使うなら必読！O(logN)など）
