PMA-60の電源不具合

Denonのプリメインアンプ「PMA-60」を購入したが、電源まわりに不具合があったためメモ。 Denonに問い合わせた結果、初期不良とのことで交換となった。交換後は正常に動作している。

まとめ

  • シャットダウン→再起動を繰り返す不具合がPMA-60に発生
  • 他機器(ドライヤーなど)に起因する電圧変動が原因の可能性有り
  • Denonに問い合わせたところ、初期不良とのことで交換となった。交換後は正常に動作中。

不具合内容

数時間に1回程度は急にPMA-60の電源が落ち、すぐに再起動がかかる。 その後、シャットダウン→再起動を数分の間に繰り返し、最後には電源OFFのままとなる。 こうなると電源ボタンを押しても電源が入らず、体感で20分程度放置しないと起動できなくなる。 電源ケーブルを抜き差ししても効果はなく、放置する必要あり。

補足

  • PMA-60にはスピーカーを接続しており、ヘッドホンは使用していない
  • シャットダウン・再起動時、保護回路動作表示用の赤LEDは点滅しない
  • オートスタンバイをOFFにしていても発生する
  • 音声を鳴らしている/いないにかかわらず発生する
  • USB、Optical、Bluetoothいずれからの入力でも発生する
  • 電源ケーブル以外を外した状態でも発生する
  • ドライヤーおよびPMA-60の電源ケーブルフェライトコアを入れたが体感できる効果なし

不具合の一部再現

ヘアドライヤー(パナソニック イオニティ EH-NE58、1200W)をONにすると上記の不具合が一部再現できたため、関係あるかは不明だが、詳細を以下に記す。

ヘアドライヤー(PMA-60とは別の壁コンセントにさしている)の出力を最大にしている間PMA-60がシャットダウンし、ドライヤーを消すとPMA-60が再起動する。 PMA-60と同じ電源タップに差しているPC、ディスプレイなどには影響がないため、電源容量の問題ではない。 なお、ドライヤー使用による再現性は100%ではなく、かつ、不具合内容で述べたものとは違って再起動は一度きりである。

もしこれが上記不具合と関係ある場合、PMA-60の電圧変動(電圧降下 or ノイズ)への耐性の弱さが不具合原因と考えられる。 もちろん、単なる電源回路の不具合(初期不良)の可能性もあるが。→初期不良だった。電源関連が死んでたのかも。

類似事例

差分更新によるmatplotlibのアニメーションの高速化

業務で、シミュレーション結果をmatplotlibによりリアルタイム描画する必要に迫られた。 最初はグラフ全体を毎ステップ再描画していたが、差分更新に変えたら動作がめっちゃ速くなって感動したのでメモ。

まとめ

グラフの軸などを再利用し、データだけ更新するには以下のメソッドを呼べばよい。

  • plot -> set_data
  • scatter -> set_offsets
  • patches.Circle -> center (正確にはこれだけインスタンス変数だが)
  • pcolorfast -> set_data

qiita.com stackoverflow.com qiita.com

なお、プロットを消す場合にはremoveすればよいらしい。 keisanbutsuriya.hateblo.jp

プログラム例

以下はブラウン運動を100ステップだけシミュレーションするコード。 実行時間を測定したところ、毎回全て再描画:10.27秒、差分だけ再描画:3.66秒と約2.81倍の差がついた。

f:id:estshorter:20190210095522p:plain
シミュレーション結果

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import time

def step(x, sigma):
    cov = np.diag(sigma)
    dt = 0.1
    x = x + dt * np.random.multivariate_normal([0, 0], cov, 20)
    return x

def draw(t):
    plt.clf()
    plt.suptitle(f"t={t}")
    ax = plt.gca()
    ax.scatter(x[:10,0], x[:10,1], c="black", s = 10)
    ax.plot(x[10:20,0], x[10:20,1], "r^")
    for i in range(10):
        c = patches.Circle(xy=x[i], radius=0.05, fc='grey', alpha=0.1)
        ax.add_patch(c)
        c = patches.Circle(xy=x[i+10], radius=0.05, fc='pink', alpha=0.2)
        ax.add_patch(c)

    ax.set_xlim(-1, 1)
    ax.set_ylim(-1, 1)
    ax.set_aspect('equal')
    plt.pause(0.01)

def draw_initial(fig, ax, t):
    text = fig.suptitle(f"t={t}")
    scat = ax.scatter(x[:10,0], x[:10,1], c="black", s = 10)
    line, = ax.plot(x[10:20,0], x[10:20,1], "r^")
    cs = []
    for i in range(10):
        c = patches.Circle(xy=x[i], radius=0.05, fc='grey', alpha=0.1)
        ax.add_patch(c)
        cs.append(c)
    for i in range(10):
        c = patches.Circle(xy=x[i+10], radius=0.05, fc='pink', alpha=0.2)
        ax.add_patch(c)
        cs.append(c)

    ax.set_xlim(-1, 1)
    ax.set_ylim(-1, 1)
    ax.set_aspect('equal')

    return text, scat, line, cs
 
def draw_succesive(text, scat, line, cs, t):
    text.set_text(f"t={t}")
    scat.set_offsets(x[:10,:])
    line.set_data(x[10:20,0], x[10:20,1])
    for i in range(20):
        cs[i].center = x[i]
    plt.pause(0.01)


if __name__ == '__main__':
    n_iter = 100
    sigma = np.full(2, 0.1 / 3)

    x = np.zeros((20,2))
    fig, ax = plt.subplots()
    
    start = time.time()
    for t in range(n_iter):
        x = step(x,sigma)
        draw(t) 
    elapsed_time1 = time.time() - start
    plt.close()

    fig, ax = plt.subplots()
    x = np.zeros((20,2))
    text, scat, line, cs = draw_initial(fig, ax, t)    
    start2 = time.time()
    for t in range(n_iter):
        x = step(x,sigma)
        draw_succesive(text, scat, line, cs, t)
    elapsed_time2 = time.time() - start2
    print(f"rewrite_all: {elapsed_time1}, rewrite_diff: {elapsed_time2}")

その他参考にしたサイト

qiita.com qiita.com

分布推定アルゴリズムあるいは確率モデル遺伝的アルゴリズム

分布推定アルゴリズム(estimation of distribution algorithm: EDA)、あるいは確率モデル遺伝的アルゴリズム(probabilistic model-building genetic algorithm: PMBGA)と呼ばれる、ヒューリスティックな最適化アルゴリズムについて調べる機会があったのでメモ。

遺伝的アルゴリズムは、個体同士を交叉・突然変異させることで最適解をヒューリスティックに探索する最適化アルゴリズムであり、個体の生成モデルは陽に示されない。 一方でEDAは、個体が生成される確率モデルを陽に定義し、それを逐次修正していくものである。 英語版Wikipediaの図を見るとわかりやすい(ブログの背景が黒いせいで見づらくなっているが)。 探索中に得られた最小値(注:真の最小値とは限らない)の近傍で確率が高くなるように確率密度関数を修正していく。 確率が低い裾野の部分が、遺伝的アルゴリズムでいうところの「突然変異」に相当するのだろうと理解している。

Eda mono-variant gauss iterations.svg
By Johann Dréo (User:Nojhan) - Own work, CC BY-SA 3.0, Link

上記図は、以下ページより引用。 en.wikipedia.org

同様のアイデア(モデルの更新方法は違うっぽいが)でより広く知られているのは、 CMA-ES (covariance matrix adaptation evolution strategy)だろう。 個体の生成モデルは多変量正規分布であり、良い個体に対する尤度が最大になるよう平均と分散が更新される(英語版Wikipedia斜め読みしただけなので違うかも)。

Concept of directional optimization in CMA-ES algorithm.png
By Sentewolf (talk) (Uploads) - Transferred from en.wikipedia to Commons., Public Domain, Link

上記図は、以下ページより引用。 en.wikipedia.org

「StanとRでベイズ統計モデリング」のメモ

確率的プログラミングとは

随所で「確率的プログラミング」という言葉を見かけ、気になっていたので本書を読んだ。そのときのメモ。 最初、この単語は確率論を考慮したプログラミングを指すのか?と思っていたがそうではなく、ベイズ統計モデリングをするための言語とのことだった。

数理最適化計算のためのモデリング言語でAMPLというのがあるが、それの確率モデリング版と考えるのがしっくりきた。「確率的プログラミング」でなく「ベイズ統計モデリング言語」と呼んだ方が誤解がない気もする。その意味で、本書のタイトルは的を射ている。

既存の確率的プログラミング言語の例は以下の通り。

何がうれしい?

確率的プログラミング言語の良いところは、使用者がモデリングに集中できるところ。従来だと式の導出などが手間だったらしいが、それをうまく隠蔽できている。

深層学習用のライブラリが、誤差逆伝播時の自動微分を隠蔽しているようなものと理解した。

本書の主張

本書で一番主張したいことは、「ベイズ統計モデリングは以下の手順で実施すると大抵うまくいく。」ということだと理解した(もちろんRやStanといったツールは何でもよいが)。

  1. 解析目的の定義
  2. データの分布の確認
  3. データ生成原理の想像
  4. モデル式の記述
  5. Rでのモデル式のシミュレーション
  6. Stanでモデルを実装
  7. 推定結果の解釈
  8. 図によるモデルの妥当性確認

この手順に沿ったベイズ統計モデリングの例が、本書には数多く掲載されている。 理論というよりも実践寄り。 ベイズ統計の理論面は、以下のウェブサイトで紹介されている本を読めば理解できそう(須山ベイズベイズ推論による機械学習入門 、渡辺ベイズベイズ統計の理論と方法)。

www.hellocybernetics.tech

階層モデル

グループ差や個人差(グループ、個人に由来する差異)をうまく扱うための手法の一つ。 「グループ差を表すパラメータはグループ内で類似しており、特定の分布(正規分布)などから生成される」という仮定を置いてモデリングする。 これにより、たとえ特定グループのデータが少なかったとしても精度の高いモデリングが可能となる。 グラフィカルモデルで見ると、説明変数/決定変数間の関係が階層化されているため、階層モデルと呼ばれる。

伝統的な統計論とベイズ統計との違い

思想

伝統的な統計論(頻度論)と、ベイズ統計との思想の違いは以下のページが詳しい。 前者は真のパラメータはひとつだけ存在するという思想であり、後者は、確率的にパラメータが決まるというものである。したがって、前者ではp(\theta | Y)というような表記はしない(これをやった場合、パラメータを確率変数としてみなすことになるため)。

www.hellocybernetics.tech

to-kei.net

ベイズ推定、最尤法、最小二乗法の違いは、以下のページがよくまとまっている。 一般性が高い順に並べると以下の通り。

ベイズ推定>最尤法>最小二乗法

つまり、最尤法はベイズ推定で、ある仮定を置いた特別な場合に相当する。 以下引用。

最尤推定 = 事前分布が一様であるBayes推定

最小二乗法 = 誤差に平均0の正規分布を仮定した場合の最尤推定

funatsu-lab.github.io

信頼区間

本書でも言及があるが、信頼区間の意味は直観的でない。 「サンプルをとる→パラメータの推定区間作成」というのを繰り返したとき、真のパラメータが推定区間内に含まれる確率が95%という意味。 以下のサイトの図を見ると理解が進む。

19-3. 95%信頼区間のもつ意味 | 統計学の時間 | 統計WEB

対して、ベイズ信頼区間は以下のように定義される。

事後分布の両端からα/2%の面積を切り取って、残った中央部の(1-α)%に対応する区間を(1-α)%ベイズ信頼区間と呼ぶ。

その他メモ

尤度と事後分布

事後分布と尤度がごっちゃになったのでメモ。

文字の定義

  • \theta:パラメータ
  • Y:得られたデータ

尤度と事後分布

  • p(Y | \theta):尤度。パラメータの候補に対し、それがデータにどれだけフィットするかを表す。最尤推定で使う指標。和が1でないので確率ではない。
  • p(\theta | Y):事後分布。データが与えられたもとで、パラメータはどういう分布を取るかの確率密度を表す。

ベイズの定理よりp(\theta | Y) \propto (Y | \theta) p(\theta) なので、事後確率最大推定値(MAP推定値)は、パラメータに関しての情報がないとき、最尤推定の結果と一致する。

機械学習のための連続最適化 まとめ

書籍「機械学習のための連続最適化」を読んでいる途中ですが、自分用にまとめます。 1、3、9、10章は個人的に目新しさがなかったので省略。 随時追記予定。

2019/2/10: 2章を加筆、11、12章を追記しました。

機械学習のための連続最適化 (機械学習プロフェッショナルシリーズ)

機械学習のための連続最適化 (機械学習プロフェッショナルシリーズ)

2章:基礎事項

リプシッツ連続

関数fがリプシッツ連続であるとは、


|f(\boldsymbol{x}) - f(\boldsymbol{y}) | \leq L || \boldsymbol{x}- \boldsymbol{y}||

が成り立つこと。

一階微分の絶対値が有限とみなすと覚えやすい。

γ平滑

勾配\nabla fがリプシッツ連続性


|\nabla f(\boldsymbol{x}) - \nabla f(\boldsymbol{y}) | \leq \gamma || \boldsymbol{x}- \boldsymbol{y}||

を満たすとき、f\gamma-平滑関数という。

二階微分が有限。

アフィン包

集合Sを包むような超平面で次元が最小になるもの

例えば、集合Sが二次元でもy=xのように一次元的に点が並んでいれば、その直線がアフィン包になる。

相対的内点

集合Sの相対的内点は\text{ri}(S)などと書かれる。 内点と比較して考えるとわかりやすい。

内点:ε近傍(中心がxで半径εの円)がSに含まれるようなε近傍が存在するとき、点x \in Sを内点という。

相対的内点:アフィン包とε近傍との共通集合が、Sに含まれるようなε近傍が存在するとき、点x \in Sを相対的内点という。

相対的内点ではアフィン包との共通集合をとっているために、相対的内点ではあるが内点ではない点というのが存在する。 例えば、S \in \mathbb{R}^ 3だが、z=0の制限が有り、点がxy平面に拘束される場合を考える。この場合、z方向にz=0から少し(たとえεでも)ずれると、そこはSに属さないため、内点は存在しない。 だが、アフィン包(この場合はxy平面)とε近傍との共通集合である相対的内点は存在する。

以下の記事は例が豊富でとてもわかりやすい。 seetheworld1992.hatenablog.com

相対的内部の扱いどころは、Wikipedia大先生が詳しい。

相対的内部は(中略)高次元空間内の低次元集合を扱う際にしばしば有用となる

相対的内部 - Wikipedia

エピグラフ

関数 fエピグラフは以下のように定義される、「ある関数の上側の領域」。


\text{epi}(f) = \{(x,t) \in \mathbb{R}^n \times \mathbb{R} | f(x)\leq t\}

凸関数 fエピグラフ空集合でないとき、 fを真凸関数という。 真凸関数であることは、 f(x)\neq + \inftyとなる xが存在することと同値。

Epigraph convex.svg
By Eli Osherovich - 投稿者自身による作品, CC 表示-継承 3.0, Link

上図はエピグラフ (数学) - Wikipedia)より引用。

エピグラフ閉集合の時、 fを閉凸関数という。 閉凸関数であることは、凸関数 fが下半連続であることと同値。

下半連続

下半連続の概念は、Wikipediaの説明と図が理解しやすい。

半連続性(英: semi-continuity)とは、拡張実数値関数(値として[tex] \pm \infty]を取り得る)に対して定義される「連続性」よりも弱い性質である。

Lower semi.svg
By Mktyscn - 投稿者自身による作品, パブリック・ドメイン, Link

上図は、 x_0で下半連続である関数を示している。半連続 - Wikipediaより引用。

 f x_0で下半連続であることは、数式では次のように書ける。


 f(x_0) \leq \liminf_{x\to x_0} f(x)

定義域の全ての点で下半連続となる関数を、下半連続関数という。

共役関数

真凸関数 fに対して次式で定義される関数のこと。


f^*(y) = \sup  \{y^T x - f(x)| x \in \mathbb{R}^n\}

 f(x)接平面の情報を保持している。 双対上昇法で出てくる。

微分

勾配の概念を拡張したもの。微分可能とは限らない凸関数にも微分を定義できる。 凸関数が微分可能なら劣微分はその勾配に一致するが、そうでない場合は、劣微分は一般に集合となる。

4章:勾配法の基礎

直線探索

1変数関数\phi(\alpha) = f(\boldsymbol{x}+\alpha \boldsymbol{d})の最小値を見つけるための計算法を直線探索法という。

関数値が十分に減少したかを判定するための条件がいくつか提案されている。

  • アルミホ条件
  • ウルフ条件
  • 強ウルフ条件
  • ゴールドシュタイン条件

アルミホ条件を用いて直線探索を行う方法の一つが、バックトラッキング法。

ゾーテンダイク条件

この条件が成り立つ関数を最小化する場合、最適化アルゴリズムが設定する降下方向と、目的関数の勾配方向が直交しなければ(\liminf_{k\to \infty} (\cos\theta_k)^2 > 0ならば)、初期解\boldsymbol{x}_0に依存せずに、目的関数の勾配がゼロベクトルに収束(大域的収束)する。

したがって、最適化アルゴリズムの収束性を議論する際には以下の条件を示すことが多い。


\liminf_{k\to \infty} (\cos\theta_k)^2 > 0

座標降下法

目的関数を、各座標軸に沿って最適化していく手法。

最急降下法

関数を一次近似したときに、関数値が最も減少する方向である -\nabla f(\boldsymbol{x})の方向を探索する。

5章:ニュートン法

ニュートン法

おなじみニュートン法。関数を二次近似したときに、関数値が最も減少する方向\boldsymbol{d}_kを探索する。


\boldsymbol{d}_k  = -  \nabla^2 f(\boldsymbol{x})^{-1}   \nabla f(\boldsymbol{x})

ただし、ヘッセ行列 \nabla^2 f(\boldsymbol{x})が正定値でない場合、関数が減少しない。

修正ニュートン法

ヘッセ行列を修正し、確実に目的関数を減少できるようにした方法。


\boldsymbol{d}_k  = -  (\nabla^2 f(\boldsymbol{x}) + \mu \boldsymbol{I})^{-1}   \nabla f(\boldsymbol{x})

\nabla^2 f(\boldsymbol{x})の最小固有値\lambda_1のとき、\mu\max(0,-\lambda_1)より大きくとれば、正定値性が保証される。

ガウスニュートン法

目的関数が次のように二乗の形で表されるときに使える。 目的関数を一次近似したときの線形最小二乗解の方向へ探索する。 Introduction to Applied Linear Algebraの説明の方がわかりやすい。


f(\boldsymbol{x}) = \frac{1}{2} \Sigma^{m}_{i=1} (l_i(\boldsymbol{x}))^2

waregawa-log.hatenablog.com

レーベンバーグ・マーカート法

ガウスニュートン法とレーベンバーグ・マーカート法の関係は、 ニュートン法に対する修正ニュートン法の関係と同じで、 正定値性を保証する修正を加えたもの。 Introduction to Applied Linear Algebraでは、 別の解釈が紹介されている。 すなわち、ガウスニュートン法で解く線形最小二乗問題の目的関数に、 \boldsymbol{x}_{k+1}\boldsymbol{x}_{k}の距離を小さくするという評価項を加えたものだと説明されている。

自然勾配法

距離構造が、ユークリッド距離でなくヘリンジャー距離で表される場合に用いる最適化手法。 機械学習屋さんは使うんですかね。。

6章:共役勾配法

目的関数が楕円のような形状をしている場合、最急降下法では効率的に最適化できない。 共役勾配法では、座標変換により楕円を真円に補正することで、この課題を解決している。

7章:準ニュートン法

ニュートン法の実行にはヘッセ行列を計算する必要があり、計算コストがかかる。 これを回避するために考えられた、ヘッセ行列を低計算量で模擬する方法が準ニュートン法である。 近似ヘッセ行列(正確にはその逆行列)は、漸化式の形で毎ステップ計算できる。

BFGS法、DFP

目的関数の勾配:\nabla f(\boldsymbol{x}_k)\boldsymbol{x}_{k+1}まわりで1次近似した式を、近似ヘッセ行列が満たすべき拘束条件として扱う。 →セカント条件:式(7.2)

セカント条件を満たす正定値行列のなかで、今の近似行列に最も「近い」ものを次ステップの近似行列とする。

  • 定式化:式(7.6)
  • 本書では、主にKLダイバージェンスを使って「近さ」を定式化する
  • 距離の公理を満たす基準を用いた場合→7.2.3節

距離基準としてKLダイバージェンスを採用した場合の解\boldsymbol{B}:BFGS公式、DFP公式:式(7.3), (7.4)

  • ダイバージェンスをとる順番で、得られる公式がBFGSかDFPか決まる:式(7.8), (7.9)
  • 図示:図(7.1)
  • BFGSとDFPは相補的な関係:\boldsymbol{B}をBFGSで更新したとき、\boldsymbol{H}=\boldsymbol{B}^{-1}DFPで更新されている。したがって、\boldsymbol{B}を計算した後にその逆行列\boldsymbol{H}を求める、といった回り道はせず、直に欲しい値:\boldsymbol{H}を公式で計算すればよい
  • 行列の更新則は、座標変換に関して共変的(座標変換してから更新しても、その逆順でも、得られる\boldsymbol{x}_{k+1}は同じ)

L-BFGS法

BFGS:O(n^2)の計算量に加え、n\times n行列を記憶できるだけのメモリ容量が必要だが、nが大きくなったとき、これらは現実的でない。 そこで計算量、必要なメモリ量がともにO(mn)なL-BFGS法が提案されている。 2mが記憶しておくべきベクトルの本数。 次元nが数千の問題に対しては、m=10程度で良好な結果が得られるとのこと。

8章:信頼領域法

信頼領域法ではまず、目的関数をモデル関数m_k(\boldsymbol{p})(通常、二次関数)で近似する。 次に、この近似が妥当な範囲||\boldsymbol{p}|| \leq \Delta_k(信頼領域)内でモデル関数を最適化する。 すなわち、次の2次関数の制約付き最適化問題を逐次解いていく形になる。


\min_{\boldsymbol{p}\in \mathbb{R}^n} m_k (\boldsymbol{p}) \quad \text{s.t.} \quad ||\boldsymbol{p}|| \leq \Delta_k

信頼領域\Delta_kは繰り返し計算中で一定ではなく、モデル関数が目的関数をよく近似できるようであれば大きくし、そうでないようであれば小さくする。

11章:主問題に対する最適化法

有効制約法

まず、有効制約式について説明する。 有効制約式とは、不等式制約( g_i(x)\leq 0)ありの最適化問題の実行可能解  xに対して、 g_i(x) = 0を満たす制約式の集合 I(x)をいう。 実行可能解  xで等式 g_i(x) = 0が成り立っていない制約は xの近傍では考慮する必要がないため、このような区別は有用である。

それでは、有効制約法の実行手順について説明する。テキストの図11.1を見ると理解が進む。なお、制約は線形不等式制約を仮定する。

  1. 有効制約 I(x)を一定に保ったまま(有効な制約の直線上を滑らせ)、目的関数がこれ以上小さくならない点まで解を更新する。
  2. 有効制約のうちの幾つかを外し、 g_i(x) \lt 0の方向へ解を更新することで目的関数を小さくすることができるのであれば、そのように解を更新する。無理ならそこで終了。
  3. 手順2で更新する場合、別の制約に引っかかるか、あるいは fの最小値を見つけるかするまで解を更新する。別の制約に引っかかった場合は、それを有効制約に加え、1へ戻る。 fの最小値が見つかったらもちろん終了。

ペナルティ法

目的関数を修正し、制約なし最適化問題として扱う手法。 具体的には、ペナルティ関数 P(x)と呼ばれる非負値連続関数を目的関数 f(x)に次のように加える。


f(x) + cP(x)

等式制約に対してよく用いられるペナルティ関数は制約 g_i(x)の二乗和。 ペナルティ関数を絶対値の和とした手法は正確なペナルティ関数法と呼ばれる。 通常のペナルティ法では、 cを徐々に大きくして最適化問題を繰り返し解く。 だが、 cを十分に大きくしないと元の問題の最適化問題の解が求まらない一方で、 cが大きいと最適化が困難になるというジレンマが存在する。 正確なペナルティ関数法では、ある程度大きなパラメータ cに対して1回だけ最適化を行えば、元の問題の局所解を得ることができる

バリア関数法

方針はペナルティ法と同じ。  g_i(x) = 0となる境界の点で無限大に発散する罰則項(バリア関数)を目的関数に加える点が異なる。 こちらも最適化問題を繰り返し解くが、ペナルティ法とは違い、途中でイテレーションを止めてもそれまでで最も良い実行可能解が得られるとのこと。つまり、繰り返しは必要ないと思われる。テキスト上に記載はないが。

12章:ラグランジュ関数を用いる最適化法

双対上昇法

主問題を変換し、双対問題を解くことに帰着させた最適化手法。 繰り返し計算の中で、主変数 xと双対変数(ラグランジュ変数) yが交互に更新される。このような手法は主双対法と呼ばれる。

以下のように目的関数が和の形で表される場合、 x_jをそれぞれ独立して動かして最適化すること(双対分解)が可能なため、本手法の有用性が高い。


\min \sum_{j=1}^m f_j(x_j) \quad \text{s.t.} \quad \sum_{j=1}^m A_j x_j = b

conda-forgeからのPythonパッケージインストール

conda-forgeからPythonパッケージをインストールする際、conda install -c conda-forge hogehogeとしたら要らないパッケージまでインストールされそうになったのでメモ。

まとめ

  • conda config --append channels conda-forge してからconda install hogehogeする
  • 最初のコマンドは、初めてconda-forgeからインストールするときに必要。2回目以降は不要。

解決法

conda install -c conda-forge hogehogeとするとconda-forgeチャンネルの優先度がデフォルトチャンネルよりも高くなってしまうことが原因ではないかと考えている。そこで、

conda config --append channels conda-forge

とコマンドを打ち、conda-forgeを低優先度でチャンネル追加したのちに

conda install hogehoge

とパッケージをインストールすればよい。 チャンネル追加は一度やれば十分なので、次からはinstallコマンドを打つだけでよい。

実行例

不要なパッケージがインストールされそうになる例

PS C:\Users\USER> conda install -c conda-forge tensorboardx
Solving environment: done

## Package Plan ##

  environment location: C:\Users\USER\Miniconda3

  added / updated specs:
    - tensorboardx


The following packages will be downloaded:

    package                    |            build
    ---------------------------|-----------------
    certifi-2018.11.29         |        py37_1000         144 KB  conda-forge
    python-3.7.1               |    hc182675_1000        20.9 MB  conda-forge
    tensorboardx-1.6           |             py_0          63 KB  conda-forge
    cryptography-2.3.1         |py37h74b6da3_1000         506 KB  conda-forge
    openssl-1.0.2p             |    hfa6e2cd_1002         5.4 MB  conda-forge
    qt-5.9.6                   |   vc14h1e9a669_2        93.9 MB
    protobuf-3.6.1             |py37he025d50_1001         515 KB  conda-forge
    conda-4.5.12               |        py37_1000         660 KB  conda-forge
    ca-certificates-2018.11.29 |       ha4d7672_0         179 KB  conda-forge
    libprotobuf-3.6.1          |    h1a1b453_1000         2.0 MB  conda-forge
    ------------------------------------------------------------
                                           Total:       124.2 MB

The following NEW packages will be INSTALLED:

    libprotobuf:     3.6.1-h1a1b453_1000     conda-forge
    protobuf:        3.6.1-py37he025d50_1001 conda-forge
    tensorboardx:    1.6-py_0                conda-forge

The following packages will be UPDATED:

    ca-certificates: 2018.03.07-0                        --> 2018.11.29-ha4d7672_0   conda-forge
    certifi:         2018.11.29-py37_0                   --> 2018.11.29-py37_1000    conda-forge
    conda:           4.5.12-py37_0                       --> 4.5.12-py37_1000        conda-forge

The following packages will be DOWNGRADED:

    cryptography:    2.4.2-py37h7a1dbc1_0                --> 2.3.1-py37h74b6da3_1000 conda-forge
    openssl:         1.1.1a-he774522_0                   --> 1.0.2p-hfa6e2cd_1002    conda-forge
    python:          3.7.2-h8c8aaf0_0                    --> 3.7.1-hc182675_1000     conda-forge
    qt:              5.9.7-vc14h73c81de_0                --> 5.9.6-vc14h1e9a669_2

Proceed ([y]/n)? n

以下のやりかただと、最小限のインストールで済む

PS C:\Users\USER> conda config --append channels conda-forge
>>
PS C:\Users\USER> conda install tensorboardx
Solving environment: done

## Package Plan ##

  environment location: C:\Users\USER\Miniconda3

  added / updated specs:
    - tensorboardx


The following packages will be downloaded:

    package                    |            build
    ---------------------------|-----------------
    tensorboardx-1.6           |             py_0          63 KB  conda-forge
    libprotobuf-3.6.1          |       h7bd577a_0         1.9 MB
    protobuf-3.6.1             |   py37h33f27b4_0         514 KB
    ------------------------------------------------------------
                                           Total:         2.5 MB

The following NEW packages will be INSTALLED:

    libprotobuf:  3.6.1-h7bd577a_0
    protobuf:     3.6.1-py37h33f27b4_0
    tensorboardx: 1.6-py_0             conda-forge

Proceed ([y]/n)?

参考

以下のページがよくまとまっている。 devlights.hatenablog.com

Introduction to Applied Linear Algebra まとめ

My Enigmaさんに触発されてIntroduction to Applied Linear Algebraを読んだのでそのメモ。 ベクトル、行列のあたりは知っていることが多かったので、最小二乗法だけまとめます。

本の内容はPDFファイルで公開されているので、興味のある人は以下のURLから見てください。 http://web.stanford.edu/~boyd/vmls/vmls.pdf

Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares

Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares

線形最小二乗法

最適化すべき変数をxとして、以下の問題を考える。


\min_x ||Ax-b||^2

この問題の解は、変分法によって以下のように求められる。


\hat{x} = (A^TA)^{-1} A^Tb

ここで(A^ T A)^ {-1} A^ TA の擬似逆行列である。

等式拘束条件がある場合も、線形最小二乗法なら結局のところ擬似逆行列を使う方法に帰着できるので、擬似逆行列が線形最小二乗法のキモと言える。

非線形最小二乗法

以下の問題を扱う。


\min ||f(x)||^2 \quad  \text{s.t.} \quad  g(x)=0

 f(x), g(x)はともに非線形関数である。 このような場合、線形最小二乗法の場合とは違い、繰り返し計算で解を求めていくしかない。

拘束条件がない場合に、非線形関数の二乗値を最小化する手法として、Gauss-Newton 法とLevenberg-Marquardt 法が紹介されている。 これらは非線形関数を逐次的に一次近似して、線形最小二乗法で求めた解で状態変数を更新していく手法である。 Gauss-Newton 法に計算を安定させるための工夫を施したのがLevenberg-Marquardt 法という位置づけ。

ちなみに、本書では、変数\lambdaラグランジュ乗数ではない)の導入は、現在のステップの解と次のステップの解の差を小さくするためのものと位置付けられている一方で、書籍「機械学習のための連続最適化」では、正定値性を保証するものとして紹介されている。

また、Newton法は、目的関数のヤコビアンが正方行列のとき、すなわち目的関数の入出力次元が一致するときのGauss-Newton法の特別な形としてみなせるとして紹介されている。

等式拘束条件がある場合のアルゴリズムとしては、ペナルティ法と拡張ラグランジュ法が紹介されている。 前者は、拘束条件を評価関数の中に組み込み、拘束条件なしとして問題を解く手法である。 後者では、通常のラグランジュ関数ではなく、拡張ラグランジュ関数を最小化する問題を解く。 制約なしとみなして次ステップの状態変数を決定するという点はペナルティ法と似ているが、拡張ラグランジュ法では、最適性条件を満たすようにラグランジュ乗数を決定する点が異なる。 拡張ラグランジュ法の方がよりよい結果を得られるとのこと。

正直、僕の説明よりも以下の金森先生の資料の方がわかりやすい。 3ページ目の3. 乗数法 の項に記載がある。

数理情報学演習 I 第 10 回 等式制約あり最適化問題の解法 – 拡張ラグランジュ関数と乗数法 –

雑記

  • 作成したモデルに過学習が起きているかどうかを調べるには、データを訓練データとテストデータに分けるとよい。両者の誤差に乖離(訓練データの誤差の方が小さい)があれば、過学習が起きている。
    • 機械学習でデータを訓練用&テスト用に分けていた意味がようやくわかった。。
  • 非線形最小二乗法でMNISTを分類すると、人間と同じくらいの性能(誤答率2%)が出る
  • 19.4節の車の非線形制御問題の運動方程式の導出: https://www.springer.com/cda/content/document/cda_downloaddocument/9783319247274-c2.pdf?SGWID=0-0-45-1532785-p177708750のp.12、2.1.4節参照
    • 後輪速度s、かつ後輪周りの角速度\dot{\theta}で走行している車の前輪速度はどうなるか?を考えると理解しやすい
    • 前輪速度もsでは?と勘違いしていたので理解に時間がかかった

参考

myenigma.hatenablog.com