はじめに しばらくブログを書いてなかったのでAHC参加ネタを投稿。 先日Atcoder Heuristic Contest 030（AHC030）に参加し最終56位という結果だったが、提出した基本方針に二乗誤差を最小化する焼きなましが含まれていた。この方法では二乗誤差の計算を何度…
これは数理最適化 Advent Calendar 2022 の 23 日目の記事です。 はじめに ディジタルフィルタとは、離散時間信号に対し所望の周波数帯域の成分だけを通過させて他は阻止する機能のことを言う。中でもIIR (Infinite Impulse Response) フィルタはフィードバ…
はじめに タイトルの通りカーネル関数の話。内積のことを考えるとカーネル関数から作られるグラム行列は正定値でないとダメな気がしたがそんなことはなくて半正定値であればよい、それは何故か？という話。 いくつかの書籍に書いてある話なのでわざわざ記事…
はじめに AtCoder上で開催されたフューチャー社主催のヒューリスティックコンテストHACK TO THE FUTURE2022（HTTF）に参加した*1。問題等詳細は以下を参照。 atcoder.jp この問題は大きく分けて各作業者のスキル推定と作業スケジューリングという2つの要素が…
はじめに 以下の書籍を読み関数解析のお気持ちを理解しつつあるので、今回は備忘録がてら超平面と点の距離を抽象ヒルベルト空間の観点で記述してみる。 なお話を簡単にするために、超平面は必ず原点を通るものとする。 機械学習のための関数解析入門: ヒルベ…
はじめに シリーズ第3弾で今回は制約付き非線形計画問題を解く主双対内点法を実装した*1。前回の準ニュートン法の記事はこちら。 yamagensakam.hatenablog.com 制約付き非線形計画問題を式で表すと、以下のような最適化問題になる。 なお今回取り上げる主双…
はじめに 以前、以下の単体法の記事を書いた。 yamagensakam.hatenablog.com 今回はこのシリーズ第2弾で、以下の制約なし非線形計画問題を準ニュートン法で解くプログラムを実装する。 手法 制約なし非線形計画問題の解き方 非線形計画問題を解く際よく行わ…
はじめに 数理最適化には興味があってこのブログでもいくつか記事を書いてきたが、つまみ食いばかりして理解があいまいな部分もあるので、もう少しちゃんと基本から学ぶため以下の書籍を読み進めている。 しっかり学ぶ数理最適化 モデルからアルゴリズムまで…
はじめに 異常検知などのタスクでは、あらかじめ取得した学習データにより形成される主部分空間にテストデータを射影し、元のテストデータと射影後のデータの距離を異常度とすることがしばしば行われる。これを再構成誤差という（詳細は下記書籍を参照）。 …
はじめに しばらくブログを更新してなかったので線形代数のネタを1つ。やりたいのは線形独立な個のベクトルが張る部分空間と線形独立な個のベクトルが張る部分空間の共通部分の基底を求めること。 以降、行列を、行列をとする。 方法1：零空間を使う方法 ま…
2020/2/2追記 ソースコードに大きな間違いを見つけたので修正した。2か所間違いがあってそれらが奇跡的に作用することでそれっぽい結果に見えていた。詳細は実装の節を参照。 はじめに 以下の記事の中で、ガウス過程と機械学習サポートページにあるサンプル…
はじめに 表題についてちょっと調べた＆やってみたのでメモ。 やりたいことは表題の通りなんだけど、少し数式で表現して整理。 今、学習データとしての個得られているとする。 入力と関数が与えられたとき、出力はに従うとする（ハイパーパラメータを持つ場…
表題の通り。この辺りややこしくていつもわからなくなるので、身につけるためにも自分なりの理解をまとめたメモを書く。 対数尤度と下限とKLダイバージェンス まず、既知の変数を、未知の変数（ここでは潜在変数か未知パラメータかは区別していない）をとす…
はじめに 以前、ベイズ推論による機械学習入門という書籍を読み、以下のような記事を公開しました。yamagensakam.hatenablog.comこの書籍には、多次元ガウス混合モデルによるクラスタリング手法が詳しく述べられていますが、多次元ガウス混合モデルによる教…
はじめに タイトルの通りです。以下の本を一通り読んだので、再度読む際の手助けになるようメモを残します。機械学習スタートアップシリーズ ベイズ推論による機械学習入門 (KS情報科学専門書)作者: 須山敦志,杉山将出版社/メーカー: 講談社発売日: 2017/10/…
はじめに アルゴリズムメモ第３段です。今回は二分探索法、２次元累積和、しゃくとり法と様々な問題に使える汎用的なアルゴリズムを書いていきます。 今回は勉強のため、アルゴリズムの本質的な部分を記述した抽象クラスと実際の問題を解く具象クラス（関数…
はじめに 以前の記事にて最短経路問題を解くアルゴリズムの実装を書きましたが、今回はその続きとしてグラフアルゴリズムの中でも幅優先探索、深さ優先探索、union-find、最小全域木問題を解くアルゴリズム2種について実装を書いていきます。 例によって、自…
はじめに 以前と同様、atcoderの400～500点問題穴埋め時のメモに加え、ABC109参加のメモです。 ARC088-D Wide Flip 区間[l - 1, r]を反転させた後、区間[l, r]を反転させると、l - 1番目の1文字のみ反転させることができる。同様に区間[l, r + 1]を反転させ…
はじめに 競プロの問題解いてて、解けなかった問題は何故解けなかったのか、何故その発想が出なかったのかを記していく自分用メモです。atcoderの400、500点くらいの問題なら、解けないなりにもボチボチ近いところまでは行けてるっていうパターンが多いので…
はじめに ここ１年くらい、ちまちまとatcoder中心に競技プログラミングに参加してたりします。ABCのD問題を解くのがやっとなのにAGCに突撃して爆死するってことを繰り返し続け、未だに緑コーダーです（パフォーマンスも1200前後がやっと）。こりゃまずいとい…
はじめに これまでの記事で近接勾配法と、それによるスパース解や低ランク解に導く正則化項を付随した最適化問題の解法、そしてその応用を見てきました。正則化項に変数間の絡みがなく各変数が独立に扱える場合は、正則化項のproximal operatorが解析的に求…
はじめに 前回の記事では、ベクトルデータの分類問題に対するスパースなロジスティック回帰を説明しましたが、今回はその拡張となる行列データに対するロジスティック回帰を見ていきます。この行列データ分類問題においても正則化項は重要な役割を持ちますが…
今回は前々回の記事で書いた近接勾配法の応用例第２段ということで、分類問題などで使われるロジスティック回帰の目的関数にL1ノルムの正則化項をつけて、スパースな解を導いてみます。スパースな解を導出するメリットとしては、クラス分類に寄与しない無駄…
はじめに 前回の記事で近接勾配法の基本と実装を見てきました。今回はこの近接勾配法を利用して、スパースコーディングの応用の１つである超解像技術を調べPythonで実装してみました*1。画像処理関係の実装はほぼ未経験だったので、その分野の人が見れば前処…
はじめに 前回、前々回とl1ノルム正則化項をつけた離散フーリエ変換により、スパースな解が得られること、そして基底ベクトルを並べた行列がユニタリ行列（直交行列）のため解析的に解けることを見てきました。それでは、が一般の行列の場合どうするか？今度…
はじめに 前回の記事では、離散フーリエ変換を係数をLasso回帰として求めスパースな解を得る方法を書きましたが、この際に複素数を取り扱いたくないため実数のみの問題に変換して、ソルバに解かせるということを行いました。今回は、複素数のまま問題を解く…
はじめに 離散フーリエ変換は離散化された時間軸の信号を周波数軸に写像する基底変換の一種で、周波数解析などによく使われます。この離散フーリエ変換の係数は、基底ベクトルの重み付き線形和で表したときの誤差の2乗和を最小にする重みと見なせます。つま…
このたび、本ブログをはてなダイアリーからはてなブログへ移行しました。旧はてなダイアリーの記事にアクセスすると、対応する本ブログの記事へのリダイレクトされるようなので、ブックマーク登録等の変更は不要です。 さて、この移行作業に当たって、元のダ…
お久しぶりです。2014年9月以来、実に3年ぶりの更新です。しばらく機械学習関連の勉強は滞っていたのですが、思うところがあって再開。とりあえず、昨年12月に開催されたNIPS2017のプロシーディングス中から面白そうな記事をピックアップして斜め読みしまし…
お久しぶりです。ちゃんと生きてます。色々と立て込んでたり何だりでモチベーションが低下していました。このまま、フェードアウトしていくのもよろしくないと思いつつもネタがない・・・なんて思っていたところ、PCのデータを整理してたら、以前作成したFFT…
