甲斐性のない男が機械学習とか最適化とかを綴るブログ

うどんくらいしか食べる気がしない

競プロとかに使うアルゴリズム実装メモ(幅優先・深さ優先探索、union-find、最小全域木)

はじめに 以前の記事にて最短経路問題を解くアルゴリズムの実装を書きましたが、今回はその続きとしてグラフアルゴリズムの中でも幅優先探索、深さ優先探索、union-find、最小全域木問題を解くアルゴリズム2種について実装を書いていきます。 例によって、自…

競プロ関係の雑メモ 2018/9/9

はじめに 以前と同様、atcoderの400~500点問題穴埋め時のメモに加え、ABC109参加のメモです。 ARC088-D Wide Flip 区間[l - 1, r]を反転させた後、区間[l, r]を反転させると、l - 1番目の1文字のみ反転させることができる。同様に区間[l, r + 1]を反転させ…

競プロ関係の雑メモ 2018/9/1

はじめに 競プロの問題解いてて、解けなかった問題は何故解けなかったのか、何故その発想が出なかったのかを記していく自分用メモです。atcoderの400、500点くらいの問題なら、解けないなりにもボチボチ近いところまでは行けてるっていうパターンが多いので…

競プロとかに使うアルゴリズム実装メモ(最短経路探索系)

はじめに ここ1年くらい、ちまちまとatcoder中心に競技プログラミングに参加してたりします。ABCのD問題を解くのがやっとなのにAGCに突撃して爆死するってことを繰り返し続け、未だに緑コーダーです(パフォーマンスも1200前後がやっと)。こりゃまずいとい…

交互方向乗数法による最適化と画像ノイズ除去への応用

はじめに これまでの記事で近接勾配法と、それによるスパース解や低ランク解に導く正則化項を付随した最適化問題の解法、そしてその応用を見てきました。正則化項に変数間の絡みがなく各変数が独立に扱える場合は、正則化項のproximal operatorが解析的に求…

近接勾配法応用編その3~トレースノルム正則化項付きロジスティック回帰による行列データの分類~

はじめに 前回の記事では、ベクトルデータの分類問題に対するスパースなロジスティック回帰を説明しましたが、今回はその拡張となる行列データに対するロジスティック回帰を見ていきます。この行列データ分類問題においても正則化項は重要な役割を持ちますが…

近接勾配法応用編その2 ~L1ノルム正則化項によるスパースなロジスティック回帰~

今回は前々回の記事で書いた近接勾配法の応用例第2段ということで、分類問題などで使われるロジスティック回帰の目的関数にL1ノルムの正則化項をつけて、スパースな解を導いてみます。スパースな解を導出するメリットとしては、クラス分類に寄与しない無駄…

近接勾配法応用編その1 ~スパースコーディング、辞書学習からの超解像~

はじめに 前回の記事で近接勾配法の基本と実装を見てきました。今回はこの近接勾配法を利用して、スパースコーディングの応用の1つである超解像技術を調べPythonで実装してみました*1。画像処理関係の実装はほぼ未経験だったので、その分野の人が見れば前処…

近接勾配法とproximal operator

はじめに 前回、前々回とl1ノルム正則化項をつけた離散フーリエ変換により、スパースな解が得られること、そして基底ベクトルを並べた行列がユニタリ行列(直交行列)のため解析的に解けることを見てきました。それでは、が一般の行列の場合どうするか?今度…

l1ノルム正則化フーリエ変換を複素数のまま解く

はじめに 前回の記事では、離散フーリエ変換を係数をLasso回帰として求めスパースな解を得る方法を書きましたが、この際に複素数を取り扱いたくないため実数のみの問題に変換して、ソルバに解かせるということを行いました。今回は、複素数のまま問題を解く…

l1ノルム正則化でスパースな離散フーリエ変換

はじめに 離散フーリエ変換は離散化された時間軸の信号を周波数軸に写像する基底変換の一種で、周波数解析などによく使われます。この離散フーリエ変換の係数は、基底ベクトルの重み付き線形和で表したときの誤差の2乗和を最小にする重みと見なせます。つま…

はてなダイアリーからはてなブログへ移行

このたび、本ブログをはてなダイアリーからはてなブログへ移行しました。旧はてなダイアリーの記事にアクセスすると、対応する本ブログの記事へのリダイレクトされるようなので、ブックマーク登録等の変更は不要です。 さて、この移行作業に当たって、元のダ…

NIPS2017論文メモ

お久しぶりです。2014年9月以来、実に3年ぶりの更新です。しばらく機械学習関連の勉強は滞っていたのですが、思うところがあって再開。とりあえず、昨年12月に開催されたNIPS2017のプロシーディングス中から面白そうな記事をピックアップして斜め読みしまし…

【Python】生存報告がてら昔書いたFFTのコードを晒す

お久しぶりです。ちゃんと生きてます。色々と立て込んでたり何だりでモチベーションが低下していました。このまま、フェードアウトしていくのもよろしくないと思いつつもネタがない・・・なんて思っていたところ、PCのデータを整理してたら、以前作成したFFT…

マルチ○○学習まとめ

機械学習の分野では、マルチ○○学習という名付けられた枠組み・手法が色々提案されています。僕は、接頭辞が共通だと、すぐごっちゃになって何が何だか分からなくなってしまうので、ちょっと整理したいと思っていました。ということで、今回は「マルチカーネ…

動的計画法でテキストセグメンテーション

いやいや、お久しぶりです。 実に半年以上も更新が滞ってました。 ちゃんと生きてます。以前、動的計画法によるシーケンシャルデータのセグメンテーションという記事を書きましたが、 今回はそれを応用して、テキストセグメンテーションを行おうと思います。…

NIPS2012自棄読み その2

なんやかんやで前回から1ヶ月以上たってしまいました。 こりゃいかんということで、NIPS2012 part2いきます。 前回は機械学習の基礎的な手法を提案した論文を紹介しましたが、今回は応用よりの論文を2本取り上げてみました。 Learning Image Descriptors wit…

NIPS2012自棄読み その1

気が付いたら3月も中旬です。昨年末に27歳の誕生日を迎えたばかりだと思っていたら、もう3ヶ月経ってしまいました。このまま、あっという間に三十路を迎えるのでしょう。時の流れは早くて残酷です。生え際の後退もかなり進行してきました。悲しいです。昔の…

【Python】動的計画法によるシーケンシャルデータのセグメンテーション

学生の頃、表題のアルゴリズムを研究に応用しようとしていましたが、すっかり忘れているので、思い出すために改めてPythonで実装してみました。当時は、matlabでfor文を回して実現していましたが、今回は、勉強がてらラムダ式やら再帰呼び出しやらを駆使して…

ICML2012の論文をいくつか3行程度で紹介する

あけましておめでとうございます。 新年早々初詣にも行かず、4ヶ月滞ってたブログを更新するのが僕です。 ということで、今更ながらピックアップしてたICML2012の論文を読んでみました。 タイトルの通り3行で概要を書いていこうと思います。 Multiple Kernel…

【Python】Heat Kernel行列をfor文を使わずに求める

ふと、過去の記事を眺めていたら、ESFSの記事でこんな記述があるのを発見。 高速化のためには、for文で計算している部分を行列計算になおすなど、 繰り返し構文をなるべく使わない工夫が必要になります。 実際にどのように実装したかは、気が向いたら書こう…

エンベデッドシステムスペシャリスト試験合格発表

以前の記事でエンベを受験してきたことを報告しましたが、その合格発表が6月15日にありました。結果は合格ということで一安心。 ただ、午後1,2ともに、自己採点の点数より思いのほか低く、合格ラインぎりぎりだったので少し焦りました。 たぶん、自分が「模…

NIPS2011斜め読み part2

ICML2012もアクセプトされた論文のタイトルとアブストが公開され、 いよいよ盛り上がってまいりましたが、でも僕はNIPS2011! 懲りずに斜め読み第2弾いきます。 間違って理解している可能性も大いにあり得るので、 それを発見した際には、指摘していただけれ…

NIPS2011斜め読み

NIPSは毎年12月頃に開催される機械学習関連の国際会議です。 Proceedingsはweb上に公開されているので、 今回は昨年末に開催されたNIPS2011の中から、 興味を惹かれた論文を何本か適当にチョイスして読んでみました。 斜め読みした程度なので、かなり理解が…

エンベデッドシステムスペシャリスト試験

お久しぶりです。 4月15日、エンベデッドシステムスペシャリスト試験を受験してきました。 ブログの更新が滞ってたのは、これの試験勉強に励んでいたため・・・ というわけではないです。ただ単に面倒くさかっただけです。受験の理由ですが、仕事で工場設備…

BPRで遊んだよ!

前回の記事の実装編です。前回ちょっとだけ述べた、last.fmのデータがここに転がってたので、 こいつで、BPRアルゴリズムを試してみることにしました。 使用したのは、usersha1-artmbid-artname-plays.tsvファイルのデータのみです。 usersha1-profile.tsvは…

情報推薦の論文

明けましておめでとうございます。ブログ開設当初は、月1ペースの更新を目標にしてたんですが、 案の定、2ヶ月以上放置。 気がつけば年が明けてました・・・ こんな感じで、今年もテキトーにやっていこうと思うので、 よろしくお願いします。というわけで、…

Eigenvalue Sensitive Feature Selection

クラスタリングや分類などを行う際、なるべく冗長となる特徴量は取り除いてから 行った方が精度や実行時間の観点で有効だとされています。 この「冗長となる特徴量を取り除く」方法は特徴選択と呼ばれ、 これまでに多数の手法が提案されています。 というこ…

Principal Anglesの日本語訳って何?

と、タイトルからいきなり疑問形なわけですが・・・ 先日の記事で書いたGrassman Discriminant Analysisの論文内に このPrincipal Anglesについて記述されていたので疑問に思ったわけです。 線形代数をきちんと学んだ人にとっては常識なのかもしれませんが、…

Grassmann Discriminant Analysisの論文を読む

ときどき、学生のころ勉強していたこと(機械学習など)が懐かしくなって、 それに関連しそうな論文を探したり読んだりするんですが、 今日はその論文の1つを紹介しようかなと思います。J. Hamm and D. D. Lee. Grassmann Discriminant Analysis: a Unifying…