かみのメモ

コンピュータビジョン・プログラムな話題中心の勉強メモ(記事一覧は https://kamino.hatenablog.com/archive へ)

数理最適化の勉強メモ − 最急降下法 / ニュートン法の原理と特徴

数理最適化の勉強メモその2です。

前回の記事では数理最適化の基本的な事項として、解析的な解法、最適性条件、最適化がうまくいかない条件などについて考察しました。

kamino.hatenablog.com

今回の記事では具体的な数値最適化のアルゴリズムとして、直線探索法の一種である最急降下法/ニュートン法についてまとめてみます。

※ 2019/09/22 : 前回の記事が長くなりすぎたので後半部分をこちらの記事に分割しました。

もくじ

0. 前提条件の確認

今回の記事では、数理最適化の分野の中でも制約なし連続最適化問題(unconstrained continuous optimization)と呼ばれる以下のような問題の局所的最適解の1つを求めることを目標にします。 なぜなら制約あり最適化や大域的最適化を考えるときもこの問題の解法が基本となってくるからです。

$$ \mathbf{x}^* = \mathrm{minarg} _ {\mathbf{x}} \ f(\mathbf{x}) \\ \mathbf{x} \in \mathbb{R} ^ n, \ \ f : \mathbb{R} ^ n \rightarrow \mathbb{R} $$

またここで目的関数 $f(\mathbf{x})$ は2回連続微分可能であり、値が変化しない平らな領域(1階微分係数と2階微分係数が継続的に  0 になる領域)を持たないものとします。

このあたりの前提条件については前回の記事に詳しくまとめているので参照してみてください。

1. 直線探索法とは

今回紹介する最急降下法ニュートン法はどちらも反復法の中の直線探索法(line search method)に分類されるアルゴリズムです。

反復法は適当な初期解  \mathbf{x} _ 0 から  f(\mathbf{x}) の値が小さくなる方向に少しずつ解を動かしていき、これ以上小さくならなくなったら(勾配ベクトルが  0 になったら)停止する、というアルゴリズムです。

その中の直線探索法とは次のような手順で解  \mathbf{x} _ k を更新していく手法を指します。

  1. 値が減少するように探索方向  \mathbf{p} _ k を決める
  2.  \mathbf{p} _ k の方向に辿っていき、値が最も小さくなる距離  \alpha _ k を見つける
    • つまり  f(\mathbf{x} _ k + \alpha _ k \mathbf{p} _ k) が最も小さくなるような  \alpha _ k を見つける
  3.  \mathbf{x} _ {k+1} = \mathbf{x} _ k + \alpha _ k \mathbf{p} _ k と解を更新する

この作業を繰り返し、勾配ベクトル  \nabla f(\mathbf{x} _ k) がほぼ  0 になった場所を結果として返すわけです。ちなみに  \nabla f(\mathbf{x} _ k) \sim 0 を評価する代わりに  \mathbf{x} _ {k} - \mathbf{x} _ {k+1} \sim 0 を評価することもあるようです。

前の章の話に従えば、鞍点に収束することを避けるために  \nabla ^ 2 f(\mathbf{x} _ k) が正定値行列になっているかを確認すべきなのですが、実際のところ低い方向を辿っていく過程でピンポイントに鞍点に乗り上げてしまう可能性はかなり低いです。 そのため一般的には勾配ベクトルの大きさだけで収束判定を行います。

さて、ここで残された課題は以下の2つです。

  1. どのように探索方向  \mathbf{p} _ k を決めるか
    • 効率を上げるため、なるべく最適解がある方向を探索したい
  2. 更新幅  \alpha _ k をどうやって見つけるか
    • 関数のスケールがわからないので、雑に更新幅を決めると収束しなかったり見当違いの場所に飛んでいったりする

1の課題を解決するためのアルゴリズム最急降下法ニュートン法です。 2についてはArmijo条件やWolfe条件などを用いたアルゴリズムを使うのが一般的です。

解説の都合上、2の方から見ていきます。

2. 更新幅の決め方(Wolfe条件)

直線探索における更新幅の決め方にはいくつかバリエーションがあるのですが、ここではWolfe(ウルフ)条件を利用した更新幅の決め方についてまとめます。

Wolfe条件は関数値が確実に減少・収束することを保証するために更新幅に対して課せられる条件です。 つまり探索方向  \mathbf{p} _ k が決まっている状況下で、ステップ幅  \alpha _ k がどのような条件を満たすべきかについて議論したものです。

Wolfe条件はArmijo(アルミホ)条件曲率条件の2つから成ります。

2.1. Armijo条件

$$ f(\mathbf{x} _ k + \alpha _ k \mathbf{p} _ k) \leq f(\mathbf{x} _ k) + c _ 1 \alpha _ k \nabla f(\mathbf{x} _ k) ^ \mathrm{T} \mathbf{p} _ k \ \ \ (0 < c _ 1 < 1) $$

Armijo条件はざっくり言えば値を増加させないための条件です。 右辺の式は  c_ 1= 1 のときに  f(\mathbf{x} _ k) の接線の式となり、 c _ 1= 0 のときは  z = f(\mathbf{x} _ k ) の軸に平行な線となります。 つまりこの条件は  \alpha _ k を遠くに設定するほど  f(\mathbf{x} _ k + \alpha _ k \mathbf{p} _ k) がしっかり減少していなければならない、という条件であると言えます。 どの程度しっかり値が減少しなければいけないのかを決めるパラメータが  c _ 1 です。

2.2. 曲率条件

$$ c _ 2 \nabla f(\mathbf{x} _ k) ^ \mathrm{T} \mathbf{p} _ k \leq \nabla f(\mathbf{x} _ k + \alpha _ k \mathbf{p} _ k) ^ \mathrm{T} \mathbf{p} _ k \ \ \ (c _ 1 < c _ 2 < 1) $$

曲率条件はステップ幅をある程度大きく取るための条件です。 Armijo条件を確実に守るためには  \alpha _ k をどんどん小さく設定すればいいのですが、それでは解が全く更新されなくなってしまいます。 そこで直線探索法のそもそもの目的「勾配ベクトル  \nabla f(\mathbf{x}) 0 になる場所を探す」に当てはめて、今の場所の勾配より勾配が緩やかな場所でなければならない、という条件を課しているのが曲率条件です。 勾配がどれくらい緩やかでなければならないのかを決めるパラメータが  c _ 2 です。

以上のWolf条件を満たす  \alpha _ k を使用し続ける場合、1回連続微分可能かつ1階導関数がリプシッツ連続であるような目的関数(2回連続微分可能よりゆるい条件。詳しくは他の記事を参照)についての直線探索法は「どこからスタートしてもどこかに収束すること」(大域的収束性)が保証されます。

2.3. 更新幅を決めるアルゴリズム

このWolfe条件を満たすような  \alpha _ k の求め方についていくつか文献を漁ってみたのですが、ちゃんとした手順は紹介されていませんでした。

おそらくですが、事前に最大ステップ幅  \alpha _ {max} とステップ幅を縮小する係数  0 \lt \mu \lt 1 およびWolfe条件のパラメータ  0 \lt c _ 1 \lt c _ 2 \lt 1 を事前に与えておき、 \mu ^ a \alpha _ {max} がWolfe条件を満たすまで  a \geq 0 をインクリメントする、というようなアルゴリズムを使うのではないかと思います。

3. 最急降下法

連続最適化における最急降下法(steepest descent method)は直線探索法における探索方向の決めるアルゴリズムの一種です。

最急降下法では  \mathbf{x} _ k の周りで  f(\mathbf{x}) を1次多項式(直線・平面・超平面)に近似し、一番急な方向  -\nabla f(\mathbf{x} _ k) を探索方向として選びます。つまり「一番勾配が急な方向を探索する」という戦略です。

たとえば2章で使った目的関数について  (-5, -7) における近似平面と探索方向  -\nabla f(\mathbf{x} _ k) を可視化すると以下のようになります。

f:id:kamino-dev:20190917120218p:plain:w700
最急降下法の原理の可視化

3Dグラフはこちら : https://kamino410.github.io/cv-snippets/optmz_blog/steepest.html

ステップ幅を大きく取る場合、このまま  (5, -5) に収束しそうですね。 ステップ幅を小刻みに取る場合は  (-2, 2) の方に収束するかもしれません。

最急降下法は確実に値を減らしていくことができる堅実な手法ですが、1次収束であり、局所的最適解にたどり着くまでに必要な反復回数が多くなりやすいことが知られています。 たとえば上から見たときの等高線が楕円状であるような関数で最適化をするとき、ほとんどの場所で勾配ベクトルは楕円の中心とは違う方向を向きます。 この関数のように1次成分より高次成分が勝っているような関数では、最急降下法の収束は非常に遅くなります。

4. ニュートン法

最急降下法の収束性の悪さを改善するために提案されたのがニュートン法(Newton's method)です。ニュートン法最急降下法と同じく探索方向を決めるためのアルゴリズムの一種です。

ちなみに非線形方程式の解を求めるアルゴリズムであるところのニュートン法とまったく同じものです。非線形方程式の求解は  g(\mathbf{x}) = 0 を求める作業ですが、今回はそれを1階導関数のノルムの根  |\nabla f(\mathbf{x})| = 0 を求める作業に使っているというだけです。

最急降下法では勾配が最も急な方向を探索方向としていました。一方、ニュートン法では  \mathbf{x} _ k の周りで  f(\mathbf{x}) を2次多項式に近似し、その2次多項式の最適解がある方向を探索方向とします。つまり「近似式の最適解がある方向を探せば実際の最適解にも近づけるだろう」という戦略です。

 f(\mathbf{x}) は2次までのテイラー展開を考えることで、以下のような2次多項式に近似できます。

$$ f(\mathbf{x}) \simeq f(\mathbf{x _ k}) + \nabla f(\mathbf{x} _ k)^\mathrm{T} (\mathbf{x} - \mathbf{x} _ k) + \frac{1}{2} (\mathbf{x} - \mathbf{x} _ k) ^ \mathrm{T} \nabla ^ 2 f(\mathbf{x} _ k)(\mathbf{x} - \mathbf{x} _ k) $$

もし  \nabla ^ 2 f(\mathbf{x} _ k) が正定値行列なら近似式は凸関数である(つまり下向きにボウル状になっている)ので、最小解は一意に決定できます。最適解は勾配ベクトルが0となる点であることに注意すると  \mathbf{x} _ k -(\nabla ^ 2 f(\mathbf{x} _ k) ) ^ {-1} \nabla f(\mathbf{x} _ k) が停留点であることがわかります。そこでニュートン法では  -(\nabla ^ 2 f(\mathbf{x} _ k) ) ^ {-1} \nabla f(\mathbf{x} _ k) を探索方向として採用します。

先ほどと同じく2章で使った目的関数について  (-5, -7) における近似関数と探索方向  -\nabla f(\mathbf{x} _ k) を可視化すると以下のようになります。

f:id:kamino-dev:20190917133519p:plain:w700
ニュートン法の原理の可視化

3Dグラフはこちら : https://kamino410.github.io/cv-snippets/optmz_blog/newton1.html

最急降下法のときよりかなり高い精度で目的関数を近似できていることがわかります。  (-5, -7) における近似2次多項式の停留点は極小点  (-3.421...\ , 3.421...) であるため探索ベクトルはそちらの方向を向きます。 ほぼ間違いなく  (-2, 2) に収束しそうですね。

このようにニュートン法では目的関数を精度良く近似できるため収束が早いです(2次収束)。そのため最急降下法よりはるかに少ない反復回数で局所的最適解に辿り着けることが知られています。

一方、ニュートン法にはヘッセ行列  \nabla ^ 2 f(\mathbf{x} _ k) が正定値でない場合、近似された2次多項式が凸関数でなくなるため、求めた停留点が鞍点や極大点になってしまうという欠点があります。

たとえば  (2, 4) における近似2次方程式は鞍点  (-0.4, 0.4) を停留点とする非凸関数となります。よって、このまま計算を進めると鞍点  (0,0) に収束してしまいます。

f:id:kamino-dev:20190917135557p:plain:w700
ニュートン法が最小解に収束しないケース

3Dグラフはこちら : https://kamino410.github.io/cv-snippets/optmz_blog/newton2.html

また  \nabla ^ 2 f(\mathbf{x} _ k) 自体の計算と1次連立方程式  \nabla ^ 2 f(\mathbf{x} _ k) \mathbf{p} _ k = \nabla f(\mathbf{x} _ k) を解くための計算コストが高いこともニュートン法の課題です。ヘッセ行列は対称行列なので、パラメータ数  n に対して計算すべき要素の数は  (n ^ 2 + n)/2 ですし、1次連立方程式の計算もそれ以上にコストが高いです。つまりパラメータ数に対してどんどん処理が重くなります。

これらの課題を克服するためにヘッセ行列  \nabla ^ 2 f(\mathbf{x} _ k) をいいかんじの正定値行列  \mathbf{B} _ k で近似する準ニュートン法というアルゴリズム群が提案されています。 準ニュートン法についてはまた気が向いたときに勉強メモを公開できたらいいなと考えています。

5. 実装上の留意点

最後に直線探索法を実装する上で注意した方がよさそうな点をまとめておきます。

5.1. 最適性条件

まず最適性条件として利用する  \nabla f(\mathbf{x}) \lt \varepsilon \ (\sim 0) もしくは  \mathbf{x} _ {k} - \mathbf{x} _ {k+1} \lt \varepsilon \ (\sim 0) \varepsilon をどの程度小さくすればいいのかという問題です。

大きすぎれば真の最適解から離れた場所で収束判定されてしまいますが、小さすぎると数値計算上の誤差が閾値を上回り、いつまでたっても収束判定されないという事態が起こります。 理想的な閾値  \varepsilon \nabla f(\mathbf{x}) のスケールや関数の形に依存します。

具体的な  \varepsilon の決め方はちょっと勉強が追いついていないので書けないのですが、とりあえず適当に決めればいいというものではないわけです。 賢い最適化ライブラリは関数の様子を見ながら自動的に閾値を決めているかもしれません。

5.2. 数値微分

数値最適化を計算機に解かせるとき、勾配ベクトル  \nabla f(\mathbf{x}) やヘッセ行列  \nabla ^ 2 f(\mathbf{x}) をどうやって計算するのかという問題があります。 実用上、解析的に計算できるのはせいぜい勾配ベクトルまでです。 そもそもヘッセ行列の解析解がわかるなら解析的に最適解が求まるはずですよね。

そこで1階導関数や2階導関数微分の定義を利用して数値的に計算することになります。 実際には以下の式のいずれかを使います。

$$ f'(\mathbf{x} _ 0, \mathbf{p}) = \lim _ {h \rightarrow 0} \frac{f(\mathbf{x} _ 0 + h\mathbf{p}) - f(\mathbf{x} _ 0)}{h} $$

$$ f'(\mathbf{x} _ 0, \mathbf{p}) = \lim _ {h \rightarrow 0} \frac{f(\mathbf{x} _ 0) - f(\mathbf{x} _ 0 - h\mathbf{p})}{h} $$

$$ f'(\mathbf{x} _ 0, \mathbf{p}) = \lim _ {h \rightarrow 0} \frac{f(\mathbf{x} _ 0 + h\mathbf{p}) - f(\mathbf{x} _ 0 - h\mathbf{p})}{2h} $$

1つ目の式は前進差分、2つ目の式は後退差分、3つ目の式は中央差分と呼ばれます。 同じ  h に対して微分値を計算したときの精度は中央差分が一番高くなることが証明できるのですが、中央差分は  f(\mathbf{x} _ 0 + h\mathbf{p}) f(\mathbf{x} _ 0 - h\mathbf{p}) の2つを計算する必要があるので少し計算コストが高くなります(  f(\mathbf{x} _ 0)微分値の計算のほかにも使うので計算コストに見込まない)。 とはいえそこまで計算コストが高いものではないので中央差分を採用するのが安牌でしょう。

さて。 ここでも  h をどの程度まで小さくすればいいのかという問題が生じます。 あまり小さくしても数値計算上の誤差のせいで逆に精度が悪化していくからです。

参考文献の「数値計算の常識 第8章 数値微分法」によれば、 f(\mathbf{x}) を計算する上で見込まれる誤差を  \delta として、おおよそ  h ^ * = 2\sqrt{\delta \ / \ | f''(\mathbf{x})|} を満たすような  h ^ * を使うのが良いそうです。

適当に  | f''(\mathbf{x})| O(10 ^ 0) 程度と仮定して、double型の浮動小数点の仮数部が52ビットであることからこれまた適当に  \delta = 2 ^ {-52} と仮定すると、 h ^ * = 2 ^ {-25} \sim 10 ^ {-8} です。 結局、大雑把に有効桁数の半分程度を選べばいいようです。

5.3. 実用的な実装

このように、数値最適化のアルゴリズムを実装するためには意外と奥深い知識が要求されます。 また先ほど説明したように、実用的には今回紹介した最急降下法ニュートン法よりBFGS法などの準ニュートン法を使うことの方が多いでしょう。 もし目的関数が最小二乗の形になっているのであればLevenberg-Marquardt法やDogleg法が選択肢に入ってきます。

これらの手法の実装はかなり複雑になります。 勉強用ならともかく、実用的にはMATLAB/Eigen/Scipy/Ceres Solverなど既存のライブラリを活用するほうが懸命だと思います。

ライブラリに渡すパラメータの意味やライブラリ内部で行われている処理を理解する上でこの勉強メモが役に立てば幸いです。


以上、数値最適化について勉強したことをまとめてみました。

このメモを書くに当たって以下の文献にお世話になりました。 ありがとうございました。

数理最適化の勉強メモ − 解析的な解法 / 最適性条件 / 勾配法がうまくいかない条件

今回から何回かに分けて数理最適化の勉強メモを公開してみます。

初回である今回の記事では、数理最適化の基本である連続最適化問題を解析的に解く方法、最適性条件、勾配法による最適化がうまくいかない条件などについて考えたことをまとめています。

※ 2019/09/22 : あまりに長かったため2記事に分割しました。最急降下法ニュートン法の解説は以下の記事に移っています。

kamino.hatenablog.com

はじめに

コンピュータビジョンの分野の勉強をしていると色々な場面で数理最適化のお世話になります。 以前の記事で紹介したカメラキャリブレーションもそうですし、同様にBundle Adjustmentを利用するSLAM、高次元データを簡潔に記述する圧縮センシング、複雑なモデル関数で事象を表現しようと試みる深層学習など、様々な場面で数理最適化の概念が利用されています。

もちろんCV分野以外でもロケットの最適制御、ナビの経路選択、工場から店舗までの最大輸送問題、ネットワークの負荷分散などあちこちで最適化の概念は利用されています。

この記事では、そうした数理最適化の理論を理解する上で重要な解析的に解く方法最適性条件について勉強したことをまとめてみます。

なお筆者はコンピュータビジョンが専門で、数学や数値計算の専門家ではありません。 間違いがある可能性が割と高いので、お気づきの際には知らせていただけると幸いです。

もくじ

1. この記事で扱う最適化問題

今回の記事では数理最適化の分野の中でも制約なし連続最適化問題(unconstrained continuous optimization)と呼ばれる問題を解くことを目標とします。

数理最適化は、究極的には「ある関数  f(\mathbf{x}) \ : \ \mathbb{R} ^ n \rightarrow \mathbb{R} が最小(もしくは最大)になるような  \mathbf{x} を探すこと」を目的とした分野ですが、問題設定によって多くの派生分野が存在します。 以下はその一部です。

  • 離散最適化(組合せ最適化)
    •  \mathbf{x} x _ 1 = 0, 1, 2, \cdots のように離散値を取る状況で最適解を求める
  • 制約あり最適化
    •  \mathbf{x} = [x _ 1, x _ 2, \cdots] ^ \mathrm{T} に対して  x _ 1 > 0 ,  x _ 1 + x _ 2 = 5 などの条件を課した上で最適解を求める
  • 線形最適化(線形計画問題
  • 多目的最適化
    • 複数の目的関数  f _ 1(\mathbf{x}), \ f _ 2(\mathbf{x}), \ \cdots がある状況で最適な  \mathbf{x} を求める
  • 大域的最適化
    • 凹凸が激しい目的関数  f(\mathbf{x}) において最も値が低く(もしくは高く)なるような  \mathbf{x} を求める

それぞれの派生分野では、問題の性質に応じた異なるアプローチが研究されています。 特に離散最適化と連続最適化では根本にある考え方がガラリと変わるため、ほぼ別分野と言ってもいいほどです。


そんな中で今回は次のような問題に的を絞って考えます。

  1. 連続最適化
    • パラメータ  \mathbf{x} は連続値を取るベクトル
  2. 制約なし最適化
    •  \mathbf{x} に関する制約条件はなし
  3. 非線形最適化
  4. 多目的最適化ではない
    • 目的関数は1つだけ
  5. 局所的最適化
    • ある点の近くで最も  f(\mathbf{x}) が小さく(もしくは大きく)なる  \mathbf{x} を探す
    • (あらゆる  \mathbf{x} の中での最適解を求めることはとりあえず諦める)

1〜4の条件を満たす問題は一般に「制約なし連続最適化問題」などと呼ばれます。 これを数学っぽく定式化すると以下のようになります。

$$ \mathbf{x}^* = \mathrm{minarg} _ {\mathbf{x}} \ f(\mathbf{x}) \\ \mathbf{x} \in \mathbb{R} ^ n, \ \ f : \mathbb{R} ^ n \rightarrow \mathbb{R} $$

文にすれば「 n 次元のベクトル  \mathbf{x}スカラー関数  f(\mathbf{x}) が最小値を取るような  \mathbf{x}^* を求めよ」となります。 g(\mathbf{x}) の最大化は  -g(\mathbf{x}) の最小化と同じことなので、この分野ではすべて最小化問題として定式化することになっています。

また5の条件の通り、局所的最適解(local minimizer)を求めることに的を絞ります。

局所的最適解とは、パラメータ  \mathbf{x} に対する目的関数  f(\mathbf{x}) のグラフを描いたとき谷の底になっている部分、つまり目的関数の値が近傍よりも小さくなっている領域のことをいいます。 一方、対象領域の中で目的関数  f(\mathbf{x}) が最も小さい値を取る領域、つまり局所的最適解の中でも最も値が小さい解は大域的最適解(global minimizer)と呼ばれます。

制約なし連続最適化問題の局所的最適解を求めるアルゴリズムは、すべての連続最適化の手法の基礎となります。制約あり最適化や大域的最適化を考えるときもこの考え方から派生させていくことになるため、まずはこの解法をしっかり抑えるべきです。

2. 解析的な解法の例

コンピュータサイエンスを勉強している人にとっては「最適化問題=コンピュータに解かせるもの」というイメージが先行するかもしれませんが、簡単な形の目的関数が相手であれば解析的に最適解を求めることができます。

この章では最適解を解析的に求める方法をおさらいしておきます。 雰囲気としてはセンター数学Ⅱによく出題されていた最大値・最小値を求める問題を多変数関数に拡張したような感じです。

2.1. 問題設定

例として2変数関数  f(x, y) = x ^ 4 -4x ^ 3 -14x ^ 2 + 12xy + 6y ^ 2 について考えてみます。 知りたい最適解はこの関数の値が局所的に最も低くなっているような点です。

2.2. 1階導関数に関する条件

まず  f(\mathbf{x}) C ^ 2 級(2回連続微分可能)なので、1階微分と2階微分が定義できることがわかります(定義できないときの話は次の章で触れます)。

次に谷底の部分の性質を考えてみると  x 方向と  y 方向ともに傾きが軸と平行、つまり微分値が  0 であるはずだということに気付きます。 このように勾配が  0 になる点のことを停留点(stationary point)と呼びます。 最適解は停留点の性質を満たすはずです。

そこで目的関数の1階導関数(勾配ベクトル)を計算してみます。

$$ \begin{bmatrix} f' _ x \\ f' _ y\end{bmatrix} = \begin{bmatrix} 4x ^ 3-12x ^ 2-28x+12y \\ 12y + 12 x\end{bmatrix} $$

これがゼロベクトルになるような点を求めると  (x,y) = (0, 0), (5, -5), (-2, 2) の3組が停留点であるとわかります。

f:id:kamino-dev:20190917110255p:plain:w700
停留点をプロットした様子

3Dグラフはこちら : https://kamino410.github.io/cv-snippets/optmz_blog/stat_points.html

ところがグラフにプロットしてみると、目的の谷底の部分に当たるのは  (5, -5), (-2, 2) だけで、 (0,0) は求めている答えでないことがわかります。

実は単に停留点を求めた場合、そこには極小点の他に極大点鞍点(saddle point)が含まれます。

極大点は文字通り、目的関数を最大化するような点のことです。 鞍点は、馬の鞍の頂点のように、ある方向から見れば極大点、別の方向からみれば極小点になっているような点のことです。 今回の  (0, 0) は鞍点に相当します。

2.3. 2階導関数に関する条件

そこで今度は求めた停留点の中から極小点だけを選び出す方法について考えます。

極小点/極大点/鞍点を区別するための手立てとして2階微分の情報を利用する方法があります。グラフ上をある一定方向に辿ったとき、勾配がマイナス →  0 → プラスの順に変化していれば、つまり2階微分が正であるなら、(その方向に見たときには)その場所は谷になっているといえます。ということはあらゆる方向に2階微分を計算してそれが正になるなら、その場所はどの方向から見ても谷になっているとわかります。

あらゆる方向の2階微分が正であることは、ヘッセ行列  \mathrm{H} = \nabla ^ 2 f(\mathbf{x}) が正定値行列であることと同値であると証明できます。 またある行列が正定値行列であることは固有値がすべて正であることと同値です。 つまりヘッセ行列の固有値がすべて正であるような点は極小点であることがわかります。

そこで先ほど求めた3つの停留点それぞれのヘッセ行列とその固有値を計算してみます。 ヘッセ行列は

$$ \begin{bmatrix}12x ^ 2 - 24x-28 & 12 \\ 12 & 12 \end{bmatrix} $$

ですので、各停留点における特性方程式固有値

特性方程式 固有値
 (0, 0)  \lambda ^ 2+4\lambda-30 = 0  -2\pm\sqrt{34}
 (5, -5)  \lambda ^ 2-41\lambda+105  41/2 \pm \sqrt{1261}/2
 (-2, 2)  \lambda ^ 2-20\lambda+42  10 \pm \sqrt{58}

となります。

 (0,0) -2 - \sqrt{34} \lt 0 であるため正定値行列ではないことがわかります。 (5, -5), (-2, 2) の2つは両方の固有値が正なので極小点すなわち局所的最適解であることがわかります。  f(5, -5) = -375,  f(-2, 2) = -32 なので、目的関数  f(x,y) の大域的最適解は  (5, -5) です。

以上のように、

  1. 勾配ベクトルが  0 である
  2. ヘッセ行列が正定値行列である

という2つの条件を活用することで解析的に局所的最適解を求めることができました。

3. 最適性条件

前章では目的関数を解析的に見ていくことで局所的最適解を求めました。しかし実際に数値最適化で扱うような目的関数は解析的に解を求められない複雑な関数であることがほとんどです。そこでコンピュータに計算させることで近似的な最適解を求める方向へと話が進んでいくわけです。

先ほど紹介した「ある  \mathbf{x} が局所的最適解であるための条件」は計算機向けのアルゴリズムの中でも活用されています。 これらの条件は最適性条件と呼ばれています。

コンピュータ向けのアルゴリズムの話に入る前に、この章ではもう一度、数学的に厳密に最適性条件の内容を確認しておきます。

3.1. 局所的最適解の定義

まず局所的最適解の数学的定義を確認しておきます。 結局のところ「ある点の関数値が近傍の点の関数値以下である」というだけの定義ですが、数学的に書くと以下のようになります。

 \|\mathbf{p}\| \leq \varepsilon を満たす任意の  \mathbf{p} について  f(\mathbf{x} ^ *) \leq f(\mathbf{x} ^ *+\mathbf{p}) が成り立つような  \varepsilon > 0 が存在する
 \mathbf{x} ^ * は局所的最適解である


3.2. 1次の必要条件

さて、先ほどお話した「最適解は停留点の性質を満たすはずだ」という条件を厳密に記述すると以下のようになります。

 \mathbf{x} ^ * が制約なし最小化問題の局所的最適解かつ、目的関数  f(\mathbf{x}) \mathbf{x} ^ * の開近傍で連続微分可能である
⇒ 勾配ベクトルが  \nabla f(\mathbf{x} ^ *) = 0 となる


これはテイラーの定理を使えば証明できます。

ここで、この定理は局所的最適解であるための必要条件を示しているという点に注意しなければなりません。 つまり「勾配ベクトルが  0 になっても局所的最適解とは限らない(極大点や鞍点も含まれるから)」また「目的関数  f(\mathbf{x}) \mathbf{x} ^ * の開近傍で連続微分可能でないなら、 \nabla f(\mathbf{x} ^ *) = 0 でない点でも局所的最適解になりうる」という落とし穴があります。

前者については先ほど説明したとおり、2次の条件を使って極大点や鞍点を排除する方向で対処します。 一方、後者は目的関数が不連続な関数であるときや、1階導関数が不連続な関数であるときに問題になってきます。

たとえば以下の図の左の関数は  x=0 において開近傍が定義できないため  \nabla f(0) = 0 を満たしていませんが、明らかに  x = 0 が最適解です。 また右の関数も  x=0 において左微分係数と右微分係数が異なっている上、共に  \nabla f(\mathbf{x} ^ *) = 0 を満たしていませんが、 x = 0 が最適解です。

f:id:kamino-dev:20190917053603p:plain:w700
不連続関数 / 1階導関数が不連続な関数 の例

こうした特殊なケースで最適解を求めるためには  \nabla f(\mathbf{x}) = 0 を満たす点(停留点)を調べるだけでは不十分であり、不連続点も個別に調べる必要があります。

3.3. 2次の必要条件

次にヘッセ行列に関する定理を厳密に記述すると以下のようになります。

 \mathbf{x} ^ * が制約なし最小化問題の局所的最適解かつ、目的関数  f(\mathbf{x}) \mathbf{x} ^ * の開近傍で2回連続微分可能である
⇒ ヘッセ行列  \nabla ^ 2 f(\mathbf{x} ^ *) は半正定値行列になる


こちらもテイラーの定理を使えば証明できます。

この定理も局所的最適解であるための必要条件を示しているという点に注意しなければなりません。つまり「2回連続微分できない点でも局所的最適解である可能性がある」「局所的最適解でなくてもヘッセ行列は半正定値になりうる」という落とし穴があります。

また、条件が半正定値行列となっていることにも注意してください。 半正定値ということは固有値  0 が含まれていても良いということであり、ある方向の2階微分係数 0 であってもよい、すなわち目的関数  f(\mathbf{x}) の値が変化しない平らな領域の中に位置する点であっても良いということです。

例を示します。 たとえば以下の関数では1階導関数は連続で  x \in [0, 1] の閉区間が局所的最適解です。

f:id:kamino-dev:20190917054844p:plain:w500
幅を持つ局所的最適解の例

当然、 x \in [0,1] の閉区間は1次の条件(勾配ベクトルが  0)を満たしています。 そのうち開区間  x \in (0,1) は、2階導関数は0(=1次元のヘッセ行列が半正定値)であり、上の定理を満たしています。 また  x = 0, 1 も2階導関数が不連続になっているため2階微分係数(=1次元のヘッセ行列)が定義できませんが局所的最適解の一部です。

もうひとつ例を示します。 以下の関数では  x \in [0, 1] の閉区間は1次の条件(勾配ベクトルが  0)を満たしており、そのうちの開区間  x \in (0,1) はヘッセ行列が半正定値であるという条件も満たしていますがこれらは明らかに鞍点であり、実際の局所的最適解は  x=2 です。

f:id:kamino-dev:20190917101629p:plain:w500
幅を持つ鞍点の例

このように2階微分が定義できない点が局所的最適解になることもあるほか、関数の中に値が変化しない領域が含まれている場合は「勾配ベクトルが  0」「ヘッセ行列が半正定値である」という条件だけでは局所的最適解でないものがピックアップされてしまう可能性が残るわけです。

3.4. 2次の十分条件

前節で述べたようにヘッセ行列が半正定値であるかだけでは局所的最適解であるかの判別はできませんが、これが厳に正定値であったとすればその点は確実に局所的最適解であると言うことができます。 これを表現したのが以下の定理です。

目的関数  f(\mathbf{x}) \mathbf{x} ^ * の開近傍で2回連続微分可能であり、 \nabla f(\mathbf{x} ^ *) = 0 かつ  \nabla ^ 2 f(\mathbf{x} ^ *) が正定値行列
 \mathbf{x} ^ * は局所的最適解である


「勾配ベクトルが  0」「ヘッセ行列が正定値」という条件では、領域的に広がっている局所的最適解は取りこぼしてしまうのですが、この条件を満たした点は確実に局所的最適解であると断言できます。

3.5. 実際の解法で使われる最適性条件

ここまで見てきたように汎用的な最適性条件を考えることはとても難しい問題です。

しかし上の議論をよく眺めてみると目的関数が「2回連続微分可能であり値が変化しない領域(1階微分係数と2階微分係数が継続的に  0 になる領域)を持たない関数」であれば「勾配ベクトルが  0」「ヘッセ行列が正定値」の2条件で正確に局所的最適解を判別できる(つまり必要十分条件になっている)ことがわかります。 そして都合の良いことに工学分野で表れる多くの目的関数はこの条件を満たします。

よって最急降下法ニュートン法を含む多くの最適化手法では、上のような都合の良い関数を最適化することを前提として

  1. 勾配ベクトルが  0
  2. ヘッセ行列が正定値

の2条件を使って局所的最適解を探索することが多いです。

なお目的関数やその導関数に不連続点を含む関数を最適化したい場合は、不連続点の左右でそれぞれ最適解を求めてそれを比較する、もしくは連続関数で近似するといった工夫を施すことが多いです。ステップ関数をシグモイド関数で近似する話なんかは有名だと思います。

1階導関数や2階導関数が不連続な連続関数については最急降下法で無理やり最適解を求められるケースもありますが、場合によっては収束性が保証されなかったり、最適解でない答えが吐き出されたりします。

4. まとめ

ここまで局所的最適解を判別するための最適性条件について考察してきました。 最後に要点をまとめておきます。

  1. 目的関数は2回連続微分可能であり、値が変化しない平らな領域(1階微分係数と2階微分係数が継続的に  0 になる領域)を持たないのが理想的
  2. この条件を満たす関数なら、以下2つの基準を満たすことと局所的最適解であることは同値
    • 勾配ベクトルが  0 であること( \nabla f(\mathbf{x} ^ *) = 0
    • ヘッセ行列が正定値であること( \nabla ^ 2 f(\mathbf{x} ^ *)固有値がすべて正)
  3. 目的関数自体やその導関数に不連続点がある場合、不連続点は上の2つの基準を満たさなくても最適解になることがあるので個別に調べる必要あり
  4. 目的関数の値が変化しない領域が存在する場合、それが極小点/極大点/鞍点のどれの集まりであるのかを個別に調べる必要あり

以上、数値最適化について勉強したことをまとめてみました。

次の記事では具体的なアルゴリズムとして最急降下法ニュートン法について解説しているのでこちらも読んでいただけるとうれしいです。

kamino.hatenablog.com

今までの記事の中で一番誤植が心配な記事なのでマサカリお待ちしています。

このメモを書くに当たって以下の文献にお世話になりました。 ありがとうございました。

  • NOCEDAL, Jorge; WRIGHT, Stephen. Numerical optimization Second Edition. Springer Science & Business Media, 2006.
  • 矢部博. 工学基礎最適化とその応用. 数理工学社, 2006.

プロジェクタとカメラのキャリブレーションソフトを書いてみた

今回は、以前からGitHubで公開しているプロカムキャリブレーションのソフトウェアについて軽い紹介記事を書いてみます。

github.com

もくじ

余談

最近プロジェクタから画像を映す行為は「投影」ではなく「投写」と言う方が正しいのではないか、という議論を耳にしました。 どちらも英語にすると"projection"なので、文献調査のときはあまり気にしていなかったのですが、プロジェクタを作っている企業のページを見て回ると確かにどこも「投写」を使っているようです。

ということでこの記事では「投写」の方を使って書いていきます。 以前の記事で「投影」と書いてしまっている箇所もあると思いますが、そこは目をつむってください。

ちなみに「再投影誤差(re-projection error)」は意味合い的に「投影」で合っている気がするので、そのまま使っていくことにします。

1. プロカムシステムのキャリブレーションとは?

このソフトウェアはプロジェクタとカメラを使ったシステム(いわゆるプロカムシステム)において、プロジェクタとカメラの幾何較正を行うためのソフトウェアです。

プロジェクションマッピング(特に動的なオブジェクトに対するプロジェクションマッピング)や計測パターンを使った形状計測などでは、しばしばプロジェクタとカメラを併用するシステムを組むことがあります。 プロジェクタから何かしらのパターン画像を投写した様子をカメラから撮影し、画像処理にかけることで、オブジェクトの位置姿勢を追跡したり物体の精密な形状を計算したりということが可能になるからです。

そして、こうした処理を行うためにはプロジェクタの投写領域・カメラの画角・カメラの歪み・プロジェクタの歪み・プロジェクタとカメラの位置関係といった情報が必要になります。

今回のソフトウェアは事前にこれらのパラメータを較正しておくためのものです。

2. キャリブレーションの原理

2.1. 基本的な考え方

基本的な考え方はカメラキャリブレーションと全く同じです。 カメラキャリブレーションの原理については以前の記事で詳しく説明しているのでよければ読んでみてください。

kamino.hatenablog.com

まず前提として、使用するカメラはレンズ歪みを考慮したピンホールカメラモデルで表現できるものと仮定します。 つまりピンホールの一点に集まってきた光を平面上の撮像素子に写し込んでいるようなモデルであると考えます。

またプロジェクタも光の進行方向が逆であるカメラモデルとして表現できると仮定します。

するとプロカムシステムのキャリブレーションはステレオカメラのキャリブレーションと全く同じものであると考えることができます。 つまり「相対位置がわかっているマーカー群(チェッカーボードやドットパターン)を2台のカメラで撮影したときにどう写り込むのか」という情報をたくさん集めて、再投影誤差を最小にするようなカメラパラメータを求めればいいわけです。

2.2. 投写画像との対応点の取得

ここで問題になるのが、プロジェクタの方の「マーカーがどう写り込むのか」の情報をどうやって計算するのかという点です。 普通はチェッカーボードやドットパターンの板をカメラで撮影して画像処理にかけることで計算するわけですが、プロジェクタは画像を撮影する機器ではなく画像を投写する機器なのでそれができません。

そこでよく利用されるのがプロジェクタからパターン画像を投写する方法です。 結局は「相対位置がわかっているマーカー群と画像平面上の対応関係」がわかればいいので、パターン画像を投写したときにマーカー群の上にどのようにパターン画像が乗るのかを調べることで同等の情報が得られます。

今回のソフトウェアでは、チェッカーボードの上にグレイコードパターンを投写することで、チェッカーボードの各コーナーと投写画像の二次元座標の対応関係を取得しています。 グレイコードを使った空間コード化法については以前の記事で解説しているのでこちらを参照してください。

kamino.hatenablog.com

しかし、単にチェッカーボードのコーナーが含まれている画素のグレイコードをデコードしても、計算される二次元座標は整数値つまりピクセル精度になってしまいますし、細かいグレイコードパターンを投写したときはデコード自体に失敗する可能性もそこそこ高いです。

そこで今回は以下の論文に従ってローカルホモグラフィーを計算する方法を採用しました。

MORENO, Daniel; TAUBIN, Gabriel. Simple, accurate, and robust projector-camera calibration. In: 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT), 2012 Second International Conference on. IEEE, 2012. p. 464-471.

コーナー周辺の一定範囲の画素でグレイコードをデコードし、その狭い領域についてカメラ画像平面から投写画像へのホモグラフィーを計算することで、コーナーと対応する投写画像上の二次元座標を計算しています。

こうしておけば、コーナー周辺の一定数以上の画素でデコードに成功しさえすれば二次元座標をサブピクセル精度で推定できるので、そこそこロバストに機能するようになります。

2.3. 計測回数について

ちなみにもとの論文ではチェッカーボードの姿勢を変えずに1度だけグレイコードを投写することでキャリブレーションを行っています。 いわゆるone-shot系の手法です。

原理上、求めたいパラメータの数 < 取得された対応関係の数 × 2 であれば1度の撮影でキャリブレーションすることは可能なのです。

しかし、この手法ではカメラの画角とカメラの設置位置のトレードオフをホモグラフィーの歪み具合だけから推定することになるので精度が悪化します。 カメラの画角と設置位置をうまく推定できないということは、チェッカーボードを設置した場所以外の奥行きに物を置いたときに矛盾が生じてくるということです。

もとの論文は比較的小さなオブジェクトの形状計測を目標としているので、狭い領域で近似的に使えるパラメータさえ求まれば良いというモチベーションなのかもしれませんが、一般的なユースケースでは正確なパラメータを計算したいところです。 そこで、今回のソフトウェアではチェッカーボードの姿勢を変えながら複数回撮影することを前提に実装しています。

3. ソフトの使い方

使い方についてはREADME.mdを参照してください。 拙い英語ですが、割と丁寧に書いたので頑張れば読み取れるはずです笑。


以上、自前のプロカムキャリブレーションソフトについて解説してみました。

coreML学習済みネットワークをplaygroundで試してみた

coreMLを使えば簡単にiOSで学習済みネットワークが実行できる、という話を聞いたので勉強し始めてみました。

最終的にはiOSにデプロイするつもりなんですが、今回はcoreMLの挙動を検証するため、デバッグしやすいplaygroundで環境を組んでみました。

この記事では学習済みモデルをplaygroundからロードする方法と、coreMLで学習済みモデルを動かすための最小実装をメモとして残しておきます。

今回作成したplaygroundはこちらのリポジトリに置いています。

github.com

※ 容量と著作権の関係で学習済みモデルは置いていないので、READMEに従って各自ダウンロードしてください

もくじ

0. 開発環境

Xcode 10.3
Swift 5.0.1

1. 学習済みモデルと画像を用意する

coreMLでニューラルネットを動かすときは、TensorFlowやPyTorchなどのライブラリでネットワークを学習させてからcoreML用のファイルに変換するのが一般的な方法だと思いますが、今回は学習を回すのが面倒だったのでとりあえずAppleが配布している学習済みモデルを動かしてみました。

配布元:https://developer.apple.com/jp/machine-learning/models/

*.mlmodelという拡張子のファイルに諸々の情報が入っているらしく、これをそのまま利用します。

動作検証用の画像はGoogleが配布しているOpen Images Dataset v5から拝借しました。

配布元:https://storage.googleapis.com/openimages/web/index.html

2. playgroundを作成する

普段どおりにplaygroundを作成します。 Xcodeを起動してGet started with a playground、もしくは起動中のXcodeのメニューバーからFile > New > Playgroundです。

次に作成したplaygroundの中にResourcesフォルダを作成します。 Finderから見るとplaygroundは1つのファイルであるかのように見えますが、実際にはパッケージとして扱われているフォルダなので、中にファイルを追加することができます。

playgroundの上で右クリック > Show Package Contentsで中のファイル構造が表示されます。

f:id:kamino-dev:20190822152636p:plain:w400

ここにResourcesというフォルダを作成します。 このフォルダの中にファイルを置いておけば、playgroundのSwiftコードからそれらのファイルにアクセスできるようになります。

今回はResourcesの中に学習済みモデル*.mlmodelと動作検証用の画像を置いておきます。

f:id:kamino-dev:20190822153055p:plain:w450

3. coreMLを動かすための最小実装

あとはplaygroundでcoreMLを動かすためのコードを書くだけです。

import UIKit
import Vision

// 学習済みモデルを読み込む
// ビルド時にmlmodelをコンパイルしたmlmodelcが作られるのでそれをロードする
let modelURL = Bundle.main.url(forResource: "YOLOv3", withExtension: "mlmodelc")!
guard let model = try? VNCoreMLModel(for: MLModel(contentsOf: modelURL)) else {
    fatalError()
}

// ネットワーク実行のリクエストを発行するための関数
func createRequest(model: VNCoreMLModel) -> VNCoreMLRequest {
    return VNCoreMLRequest(model: model, completionHandler: { (request, error) in
        // ネットワーク実行完了後の処理を定義する
        DispatchQueue.main.async(execute: {
            // ネットワークによってrequest.resultsの型は違う
            // YOLOv3の場合は[VNRecognizedObjectObservation]型
            guard let results = request.results as? [VNRecognizedObjectObservation] else {
                fatalError("Error results")
            }
            for result in results {
                print("\(result.confidence) : \(result.boundingBox)")
                let len = result.labels.count > 5 ? 5 : result.labels.count
                for i in 0..<len{
                    print("\(result.labels[i].identifier), ", terminator: "")
                }
                print()
            }
            print()
        })
    })
}

// 検証用画像の読み込み
let img1 = UIImage(named: "sample1.jpg")!
let img2 = UIImage(named: "sample2.jpg")!

// 1枚目の画像の分析をリクエスト
let handler1 = VNImageRequestHandler(cgImage: img1.cgImage!, options: [:])
let request1 = createRequest(model: model)
try? handler1.perform([request1])

// 2枚目の画像の分析をリクエスト
let handler2 = VNImageRequestHandler(cgImage: img2.cgImage!, options: [:])
let request2 = createRequest(model: model)
try? handler2.perform([request2])

coreMLではネットワークの実行は非同期に実行されるようで、画像の情報を持つVNImageRequestHandlerと、モデルの情報および実行完了後の処理を持つVNCoreMLRequestを作成してからhandler.perform([request])を呼び出せばいいようです。

画像サイズ周りの細かい処理とか、モデル実行後にどのような結果が帰ってくるのかとかは全てmlmodelファイルの中で定義されているようですね。

このplaygroundを実行すると以下のように、結果の信頼性, 検出範囲, ラベルのリストがコンソールに表示されます。

f:id:kamino-dev:20190822155324p:plain
実行結果


ということで、思ったよりあっさり学習済みモデルを実行することができました。

試してみたところmlmodelファイルがかなり色々な情報を保持しているっぽいことがわかったので、今後はこのモデルファイルの作り方について調べていくつもりです。

iTerm2+NeoVimに定住するためにやったこと

最近ようやくターミナルでの開発環境がいいかんじにまとまってきたので、振り返りついでに記事を書いてみます。 ターミナル開発環境を整えるためのTips集として読んで頂けると幸いです。

こちらのGitHubリポジトリでdotfilesも公開しているので、記事の中で「この設定どうやってやるの?」という部分があれば参照してみてください。

github.com

あと「もっといいツールとかおすすめ設定あるよ!」というのがあればぜひ教えて下さい!!

開発環境の概要

この記事ではMacを使っていることを前提としています。 紹介する自分の開発環境の概要は以下のとおりです。

  • よく書くコード : コンピュータビジョン系, 画像処理系, 数値計算
  • メインの開発言語 : C++ (CMake), CUDA, Python
  • マシン : MacBookPro (US配列) + GPU搭載のUbuntuサーバー
  • ターミナル : iTerm2
  • Shell : zsh + bash

紹介する内容は全て2019年8月現在の最新リリースに従って書いています。

f:id:kamino-dev:20190812125041p:plain
大体こんな見た目

もくじ

1. Mac本体

1.1. 英字配列キーボードのMacBookを買う

実は日本国内で購入できるUS配列のノートパソコンはあまり多くないのですが、ありがたいことにMacBookは購入時にキーボード配列を指定できます。

個人的にはコーディングをするならJIS配列よりUS配列のほうが有利だと思っています。 US配列はJIS配列に比べて"が押しやすいこと、[, ]が横並びになっていること、右手小指からEnterまでの距離が近いことなどが理由です。

また次の項で説明しますが、Macではスペースの左右にあるcommandキーを日本語/英数入力の切り替えキーにカスタムできるので、US配列でも日本語入力時のストレスはほとんどありません。

私の場合はWindowsの外付けキーボードから徐々にUS配列に慣らしていき、MacBookを買い換えるタイミングでUS配列に完全移行しました。 US配列のキーボードはElecomが1000円くらいで販売していたりするので、気になる方は一度試してみるのがいいと思います。

1.2. キーボード配列をカスタマイズする

世のほとんどのプログラマcaps lockcontrol/commandを入れ替えて使っていることと思いますが(偏見)、私も多分にもれずcaps lock, control, commandを三つ巴で入れ替えています。

2019年現在、Macでキーボード配列をいじるならKarabiner-Elements一択だと思います。 公式サイトはこちら

Karabiner-Elementsでは、単純なキースワップを設定できるSimple Modificationsと、複雑な条件や複数キー入力に関する変換ルールを設定できるComplex Modificationsの2種類の設定があります。

私はComplex Modificationsを使って以下のような設定を組んでいます。

  1. ターミナルやVimキーバインドを利用するアプリ(Terminal, iTerm2, VSCodeなど)ではcaps lockcontrolを入れ替える
  2. それ以外のアプリではcaps lockキーをcommandに、両方のcommandキーをcontrolに、controlキーをcaps lockにする
  3. 右のcommandキーが単体で押されて放されたら日本語入力に、左のcommandキーが単体で押されて放されたら英数入力に(英字配列キーボード向けの設定)

Macでは主にcommandキーがWindowsでいうところのControlキーの役割を果たしているので、Aの左隣にはcommandを配置しています。

ただし、ターミナルのショートカットやVimコマンドで使うのはcontrolの方なので、ターミナルやVimキーバインドを有効にしたアプリを開いているときはcaps lockcontrolだけ入れ替えて、Aの左隣をcontrolにしています。

この設定だとコピー&ペーストやアクティブウィンドウの切り替えのときに

  • ターミナルソフト : スペースの隣のキー + c, v, tab
  • その他(ブラウザやFinder): Aの左隣のキー + c, v, tab

という使い分けが生じますが、慣れでカバーしています。 そもそもターミナル上ではVimのヤンク機能やpbcopyを使うのでコピペする機会はそんなに多くないですし、アクティブウィンドウの切り替えはMission Control(F3 or 3本指で上にスワップするやつ)から行っているので不便は感じていません。

2. shell関連

次にshellに関連する設定です。 自分が使っているのはzshですが、以下で紹介する設定についてはbashでもだいたい同じことができます。

2.1. shellのショートカットを覚える

shellにはカーソル移動などに使えるショートカットがあります。 このショートカットはEmacsがベースになっているのでVim派の人間としては覚えにくい代物なのですが、一度覚えればターミナル入力のストレスがかなり軽減されます。

自分がよく使うのは以下のショートカットです。

  • Ctrl + a : カーソルを先頭に
  • Ctrl + e : カーソルを行末に [End]
  • Ctrl + f : カーソルを1つ右に [Forward]
  • Ctrl + b : カーソルを1つ左に [Back]
  • Ctrl + c : コマンド入力を中断(打ちかけたコマンドを無視して改行)
  • Ctrl + h : Backspaceと同じ
  • Ctrl + d : カーソルが当たっている文字を消す [Delete]
    • 何も入力していない状態で押すとshellを終了する
  • Ctrl + p : コマンド履歴を戻る [Previous]
  • Ctrl + n : コマンド履歴を進む [Next]
  • Ctrl + r : 過去に実行したコマンドから検索する
    • デフォルトの検索機能は使いにくいので、後述のpeco+historyに置き換えるのがおすすめ
  • Ctrl + l : 現在の行が一番上に来るようにスクロール
  • Ctrl + u : 打ちかけたコマンドを切り取り
  • Ctrl + w : カーソル位置より前の単語を切り取り [Word]
  • Ctrl + k : カーソル位置より後を切り取り
  • Ctrl + y : 切り取った文字列を貼り付け [Yank]

一応これらのショートカットは~/.zshrc~/.bashrcで変更することもできますが、私は他の環境を触るときに混乱するのが嫌なのでデフォルトのまま使っています。

2.2. プロンプトをカスタマイズする

プロンプトとはシェルの入力前に表示されるuser@user-ubuntu:Documents$とかのことです。

zshでは設定ファイル~/.zshrcの中に以下のようなコマンドを追加することでプロンプトを変更できます。

PROMPT='%n@%m %d %?$ '

%nはログイン中のユーザー名、%mはホスト名、%dはカレントディレクトリのフルパス、%?は直前のコマンドの終了コードを意味します。上の設定ではuser@users-MacBook-Pro /Users/user 0$みたいなプロンプトが表示されるはずです。

個人的には%?で直前のコマンドの終了コードを表示しておくのがおすすめです。長々とメッセージが表示されるコマンドを実行したとき、結局成功したのか失敗したのかをひと目で判別できるというのはなかなか便利です。

他にもいくつかの特殊記号があるので、気になる方は公式ドキュメントを読んでみてください。

ちなみにbashの例はこちらです。

export PS1="\u@\h \w $"

詳細はbash公式ドキュメントを確認してください。 残念ながらbashでは特殊記号で終了コードを取ることができないので、表示させたい場合は特別に処理を書く必要があります。 こちらのstackoverflowの回答を参照してみてください。

2.3. ビープ音を消す

shellには無効なキー操作をしたときや何らかの通知を行うためにビープ音を鳴らす機能がありますが、邪魔なので無効にしています。 zshの場合は~/.zshrcに以下のコマンドを追加すればいいです。

setopt no_beep

bashの場合は~/.inputrcに以下のコマンドを追加すればいいです。

set bell-style none

2.4. peco+historyを構築する

先ほどCtrl + rはコマンド履歴の検索のショートカットだと書きましたが、デフォルトの検索機能は割と使いづらいです。

そこでpecoというツールを利用して独自に検索機能を作ります。 pecoはコマンドラインで検索・選択ができるようにするツールですが、これと履歴を表示するhistoryコマンドを組み合わせることで見栄えの良い履歴検索機能が作れます。

brewを使っているならpecoは以下のコマンドでインストールできます。 また公式リポジトリからビルド済みバイナリをインストールする方法もあります。

brew install peco

pecoをインストールした上で~/.zshrcに以下のコマンドを追加するとCtrl + rで履歴検索機能が起動するようになります。

function peco-history-selection() {
    BUFFER=`history -n 1 | tail -r  | awk '!a[$0]++' | peco`
    CURSOR=$#BUFFER
    zle reset-prompt
}

zle -N peco-history-selection
bindkey '^R' peco-history-selection

f:id:kamino-dev:20190812124611p:plain
peco+historyのコマンド履歴検索

コマンドの一部を打って検索、Ctrl + n, Ctrl + pで候補の中から選択、Enterで決定、Ctrl + cで中断できます。

bashの場合は以下のコマンドを~/.bashrcに追加しましょう。 こちらは拾い物なのでたぶん上のコマンドと若干挙動が違うのですが、私は気にせず使っています()。

peco-select-history() {
    declare l=$(HISTTIMEFORMAT= history | sort -k1,1nr | perl -ne 'BEGIN { my @lines = (); } s/^\s*\d+\s*//; $in=$_; if (!(grep {$in eq $_} @lines)) { push(@lines, $in); print $in; }' | peco --query "$READLINE_LINE")
    READLINE_LINE="$l"
    READLINE_POINT=${#l}
}
bind -x '"\C-r": peco-select-history'

またpecoはMac以外のOSでも動くので、リモートのLinuxサーバーでも同じ要領で履歴検索機能を組むことができます。

3. iTerm2関連

MacにはデフォルトでTerminalというターミナルソフトが入っていますが、それ以上にiTerm2というオープンソースのターミナルソフトがかなり優秀なのでこれを導入しています。 iTerm2はこちらの公式サイトからインストールできます。

3.1. iTerm2のショートカットを設定する

iTerm2のショートカットはPreferences > Keysからカスタマイズできます。私はほぼデフォルトのまま、Window/Tab/Pane関係のショートカットだけを以下のように変更しています。

f:id:kamino-dev:20190812122358p:plain
iTerm2のショートカット設定

よく使うショートカットは以下のとおりです。

  • Ctrl + n : 新しいwindowを作る
  • Ctrl + t : 新しいtabを作る
  • Ctrl + w : 今のtabを閉じる
  • Ctrl + Enter : フルスクリーンを切り替える
  • Ctrl + q : iTerm2を終了する
  • command + (Number) : tabを切り替える(ヘッダに番号が表示されているはず)
  • option + command + (Number) : windowを切り替える(ヘッダに番号が表示されているはず)

細かい画面分割はNeoVim側の役目と割り切っているので、iTerm2のPane機能は使っていません。

またoptionのdouble-tapでHotkey Windowが出てくるように設定しています。 Preferences > Keys > HotkeyからCreate a Dedicated Hotkey WindowでHotkey Windowのプロファイルを作成します。 以降の設定変更はPreferences > Profiles > Hotkey Windowから行えます。

この設定をしておけばoptionのdouble-tapでいつでもHotkey Windowが上から降りてくるようになります。

f:id:kamino-dev:20190812123159p:plain
Hotkey Window

このHotkey Windowはちょっとしたファイル操作やpingを打つときなどに使っています。

3.2. ビープ音を消す

zshで消音設定をしていても、sshでリモートのbashを起動したときなどはビープ音が鳴ってしまうので、これを消すためにiTerm2側でも消音設定をしています。 Preferences > Profiles > TerminalのSilence bellにチェックを入れればOKです。 音の代わりに視覚的に知らせてくれる機能としてFlash visual bellShow bell icon in tabsがありますが、私はどちらも必要ないのでOFFにしています。

3.3. Status Barの設定

Status BarはiTerm2 ver.3.3から追加された機能です。 tmuxには各種情報を表示できるStatus Barがあるのですが、これと同じ機能がiTerm2に移植されたものです。

Status Barの設定はPreferences > Profiles > Default > Session > Configure Status Barから変更できます。

私の場合はホスト名, カレントディレクトリのフルパス, Gitブランチ, CPU使用率, メモリ使用率の5つを表示させています。

f:id:kamino-dev:20190812123433p:plain
Status Bar

3.4. Shell Integrationを使いこなす

iTerm2 Shell Integrationは、iTerm2上のshellに拡張機能を追加することができるパッケージです。 手元のMacの他にも、sshログイン先のサーバーでも利用できます。

インストールは簡単で、iTerm2でインストール先のshellを開いた状態で画面左上のiTerm2 > Install Shell Integrationをクリックするとインストールコマンドを実行してくれます。 このときにUtilitiesもインストールするかどうか聞かれるので、一緒にインストールさせておきます。

Shell Integrationの機能の詳細は公式ドキュメントで紹介されています。

私がよく使っているのは以下の機能です。

  • 過去のコマンド入力の行を辿ってスクロールする
    • command + shift + Up/Down
  • コマンド終了時にデスクトップ通知を出す
    • option + command + a
  • 過去に実行したコマンドの終了コードや実行時間を確認する
    • プロンプトの左に出る矢印を右クリック
  • 動的にプロファイル(iTerm2の設定)を切り替える
  • リモートのホスト名, ユーザー名, カレントディレクトリの情報をiTerm2のStatus Barなどに反映させる

他にもコマンド履歴を表示したりディレクトリ履歴を表示したりできるのですが、先ほど紹介したpeco+historyの方が便利なのであまり使っていません。

一方、Shell Integration Utilitiesでは~/.iterm2以下にいくつかの便利なコマンドが追加されます。 各コマンドの機能の詳細はこちらの公式ドキュメントを参照してください。

自分がよく使うのは以下のコマンドです。

  • imgcat <filename> : ターミナル上に画像を表示する
  • imgls <filenames> : 指定されたファイルの一覧をサムネイル付きで表示する
  • it2copy : パイプで渡された情報をMacクリップボードにコピーする
    • つまりリモートでも使えるpbcopy
    • Preferences > General > Selection > Applications in terminal may access clipboardにチェックを入れておく必要がある
  • it2dl <filenames> : (リモートで実行)指定されたファイルをMacにダウンロードする
  • it2ul : (リモートで実行)Finderが開き、そこで指定されたファイルをアップロードする

f:id:kamino-dev:20190812123701p:plain
imgcat, it2dlを実行した様子

4. NeoVim関連

NeoVimは従来のVimの拡張性や使いやすさを向上させるために新たに開発されているエディタです。 公式ページはこちら

Vimを現役で使っている方もいるとは思うのですが、私はNeoVimでしか動かないプラグインを使ったり、後述のTerminal emulatorやneovim-remoteを使ったりする目的でNeoVimを選びました。

4.1. 基本設定を決める

Vimの設定ファイルは~/.vimrcですが、NeoVimの設定ファイルは~/.config/nvim/init.vimになります。 設定ファイルの文法はほとんど一緒ですが、細かい設定項目が変わっているので都度調べながら書いていく必要があります。

私が使っている基本的な設定は以下のとおりです。

" 行番号を表示する
set number
" タブはスペース4つ分の幅で表示
set tabstop=4
" 空白部分でtabキーやbackspaceを押したときにカーソル移動する幅
set softtabstop=4
" 自動インデントの幅
set shiftwidth=4
" タブを入力したときスペース×Nに置き換える
set expandtab
" 改行時に前の行のインデントを継承する
set autoindent
" C系の文法に従って自動インデント、{}とかに反応する
set smartindent
" tabと行末の余計な空白を可視化する
set list
set listchars=tab:»-,trail:-
" ビープ音を鳴らさない、可視化もしない
set visualbell
set t_vb=

4.2. キーバインドをカスタマイズする

次にVimキーバインドのカスタマイズです。 私はデフォルトからかけ離れた設定をするのも嫌なので、よく使うものだけ既存のコマンドを邪魔しないように置き換えています。

まずVimではノーマルモード:を打つとコマンドモードになるわけですが、英字配列キーボードでは:を入力するためにshiftを押す必要があります。 :wとか:qとか打つ度にshiftキーを押すのは面倒です。 そこで;でコマンドモードに入るようにしています。

" [ノーマルモード] ;でコマンド入力
noremap ; :

ノーマルモードf <letter>shift+f <letter>を入力すると、その行内で文字を検索してカーソルを移動させることができ、複数ヒットしたときは続けて,:を入力すれば左右に移動できます。 この左右移動は,.にしたほうが直観的にわかりやすいと思い、.;に置換しています。

" [ノーマルモード] .でfやFで検索を繰り返し
noremap . ;

そして上記の変更であぶれた.(直前の動作を繰り返す)の機能を;に割り当てています。

" [ノーマルモード] :で前の操作を繰り返し
noremap : .

次にNeoVim内部のタブを左右に移動するためのコマンドはgT, gtなのですが、この操作はよく使うのでCtrl + h, Ctrl + lでも移動できるようにしています。

" [ノーマルモード] Ctrl + hで左のタブに移動
nnoremap <C-h> gT
" [ノーマルモード] Ctrl + lで右のタブに移動
nnoremap <C-l> gt

また行頭, 行末に移動するためのコマンドは^, $ですが、これもshiftキーが必要な上、一番上の段のキーを押す必要があるので使いづらいです。 そこでspace, h, space, lでも移動できるようにしています。

" [ノーマルモード] space, hで行頭にカーソル移動
noremap <Space>h ^
" [ノーマルモード] space, lで行末にカーソル移動
noremap <Space>l $

NeoVimにはタブの中でshellを起動するTerminal emulatorが搭載されているのですが、新しいタブを開くには:tabnewを、そこでターミナルを起動するには:teを入力する必要があります。 これを一発で実行するためにspace, tを新しいターミナルタブを開くためのショートカットとして登録しています。

" [ノーマルモード] space, tで新しいターミナルタブを開く
noremap <Space>t :tabnew<CR>:te<CR>

最後に、ターミナルからノーマルモードに戻るときのコマンドはデフォルトではなぜかCtrl + \, Ctrl + nもしくはescapeになっているのですが、普段ノーマルモードに戻るときにCtrl + [を使っているので、これに合わせるための設定をしています。

" [ターミナルモード] Ctrl + [でノーマルモードに戻る
tnoremap <C-[> <C-\><C-n>

今のところは以上のキー設定でそこそこ平和に暮らせています。

4.3. Vimキーバインドを覚える

自分なりのキーバインドを決めたら、あとはひたすら使い込んで覚えていくだけだと思います。壁紙をチート表にしてみたりもしましたが結局見ることはなかったので、毎日Vimを使って少しずつ新しいコマンドにチャレンジするのがいいと思います。

自分の場合はなんとなく以下の順番で覚えていったような気がします。

  • i, I, a, A, s, S(インサートモードに)
  • escape, Ctrl + [ノーマルモードに)
  • k, j, h, l(上下左右) , gg, G(先頭・末尾) , <number>G(N行目へ移動)
  • 0, ^, $(行頭・インデントの行頭・行末)
  • Ctrl + u, Ctrl + d(半ページスクロール), Ctrl + e, Ctrl + y(1行スクロール)
  • x, dd, yy, p, P(1文字カット・カット・コピー・ペースト)
  • <number>j, d<number>jなど(複数行移動・複数行カット)
  • u, Ctrl + R(Undo, Redo
  • >>, <<(インデント操作)
  • v(範囲選択)からのd, y, s(カット・コピー・削除してインサートモードに)
  • Ctrl + v(矩形選択)からのd, y, I, A, s(複数行に同じ編集を施せる)
  • b, B, w, W, e, E(単語区切りでカーソル移動)
  • /<string>(文字列検索)からのn, N(検索結果を移動)
  • f<letter>, F<letter>(行内でその文字が見つかった場所へ移動)からの,, ;(さらに移動)
  • :%s/<before>/<after>/gl(文字列置換)
  • H, M, L(画面内の上段・中段・下段), zt, zz, zb(現在行が上段・中段・下段に来るようにスクロール)
  • q<letter>, @<letter>(マクロ)

4.4. プラグインを入れる

Vimの醍醐味と言えばプラグインですよね。 デフォルトのままでは色々と不便なのでプラグインを追加していきます。 Vimプラグイン関係の記事はたくさんあるので、この記事ではざっくりした説明だけしておきます。

Vimプラグインをインストールするための補助ツールにはいくつか種類がありますが、私はdein.vimを利用しています。 導入しているプラグインは以下のとおりです。

  • tomasr/molokai
  • vim-airline/vim-airline
  • myusuf3/numbers.vim
    • ノーマルモードで相対行番号、インサートモードではそのままの行番号を表示するプラグイン
    • 相対行番号の方がd<number>jとかが使いやすいので
  • scrooloose/nerdtree
  • jistr/vim-nerdtree-tabs
    • NERDTreeをタブ間で(擬似的に)単一のものにするためのプラグイン
  • Shougo/deoplete.nvim
  • autozimu/LanguageClient-neovim
    • Language Server Protocolに則った言語開発サポートを入れるためのフレームワーク
    • 使用する言語に応じたLanguage Serverの実行ファイル(C++clangdPythonpyls、Rustはrls)を指定すれば勝手に連動してくれる
  • rhysd/vim-clang-format
  • tell-k/vim-autopep8

まだ調整不足感はありますが、とりあえずこの構成で運用しています。

言語開発関係はLanguage Server Protocolを利用するのが鉄板だと思います。 Language Serverの実行ファイルをインストールしてLanguageClient-neovimに情報を登録しておけば、エラー表示・コード補完などをやってくれます。 ただしコードのリフォーマットはやってくれないものが多いので、言語別にフォーマッター用のプラグインを入れています。

以上のプラグインのうちvim起動時に必ずロードするものの情報を~/.config/dein/plugins.tomlに書いておき、指定した条件(on_fton_ifなど)を満たしたときに遅延ロードさせたいプラグインの情報は~/.config/dein/plugins_lazy.tomlに書いておきます。 プラグインファイルの文法の詳細は:help deinを読むか、他の記事を参照してください。 一応、私が使っているプラグインファイルはGitHubにアップロードしてあります(https://github.com/kamino410/dotfiles/tree/master/.config/dein)。

あとはinit.vimに以下のようなスクリプトを書いてからNeoVimを起動すれば、dein.vim自体のインストールの後に他のプラグインをインストールしてくれます。 以下のスクリプトではインストール先は~/.cache/dein/になっています。

let g:cache_home = empty($XDG_CACHE_HOME) ? expand('$HOME/.cache') : $XDG_CACHE_HOME
let g:config_home = empty($XDG_CONFIG_HOME) ? expand('$HOME/.config') : $XDG_CONFIG_HOME
let s:dein_cache_dir = g:cache_home . '/dein'

if &runtimepath !~# '/dein.vim'
    let s:dein_repo_dir = s:dein_cache_dir . '/repos/github.com/Shougo/dein.vim'
    if !isdirectory(s:dein_repo_dir)
        call system('git clone https://github.com/Shougo/dein.vim ' . shellescape(s:dein_repo_dir))
    endif
    execute 'set runtimepath^=' . s:dein_repo_dir
endif

let g:dein#install_max_processes = 16
let g:dein#install_progress_type = 'title'
let g:dein#enable_notification = 1

if dein#load_state(s:dein_cache_dir)
    call dein#begin(s:dein_cache_dir)
    let s:toml_dir = g:config_home . '/dein'
    call dein#load_toml(s:toml_dir . '/plugins.toml' , {'lazy': 0})
    call dein#load_toml(s:toml_dir . '/plugins_lazy.toml' , {'lazy': 1})
    call dein#end()
    call dein#save_state()
endif

if dein#check_install()
    call dein#install()
endif

4.5. neovim-remoteを入れる

NeoVim内でターミナルを開いてファイル操作をしていると、そこからファイルを開きたくなることがありますが、nvim <filename>と打ってしまうとNeoVim内で別のNeoVimが起動してしまいます。 そこでneovim-remoteというツールを使います(公式リポジトリ)。

neovim-remoteをインストールするとnvrというコマンドが使えるようになります。 これを打つとNeoVimが自動で立てているサーバーにリクエストが投げられ、それを受けたNeoVimが指定されたファイルを開いてくれます。

私は新しいタブで開くためにnvr --remote-tabと打つことが多いので、~/.zshrcエイリアスnvrrを登録しています。

alias nvrr='nvr --remote-tab'

またNeoVim内のターミナルからgit commitしたときにコミットメッセージを入力するウィンドウをpaneとして開かせるため、~/.config/nvim/init.vimに以下の設定も追加しています。

let $GIT_EDITOR = 'nvr -cc split --remote-wait'
autocmd FileType gitcommit set bufhidden=delete

4.6. インストール用スクリプトを作る

新しくサーバーを組んだときやDockerでコンテナを作成したときに毎回ShellやNeoVimの環境を構築するのは面倒です。 そこで、ある程度自分の納得できる設定が決まったら環境構築用のスクリプトを書いてしまうことをおすすめします。

私はUbuntu18.04用に以下のようなスクリプトを使っています。

cat <<EOF2 >> install.sh
apt update
apt install -y software-properties-common
add-apt-repository -y ppa:neovim-ppa/unstable
apt update
apt install -y python3 neovim python3-pip git clang clang-tools curl clang-format peco
python3 -m pip install pynvim neovim neovim-remote autopep8
mkdir -p ~/.config
mkdir -p ~/.config/dein
mkdir -p ~/.config/nvim
mkdir -p ~/.config/nvim/ftplugin
mkdir -p ~/github
cd ~/github
git clone https://github.com/kamino410/dotfiles.git
cd ./dotfiles
git pull
cp ./.config/nvim/init.vim ~/.config/nvim
cp ./.config/nvim/ftplugin/cpp.vim ~/.config/nvim/ftplugin
cp ./.config/dein/plugins.toml ~/.config/dein
cd ~
cat <<EOF >> ~/.bashrc
export LC_ALL=en_US.UTF-8
alias nvrr='nvr --remote-tab'
peco-select-history() {
 declare l=
 READLINE_LINE=""
 READLINE_POINT=0
}
bind -x '"\C-r": peco-select-history'
EOF
EOF2
sh install.sh

5. その他

5.1. Gitの設定

git statusはよく使うのでgit stエイリアスを登録しています。 またコミットログをネットワーク図で確認するためのコマンドをgit glogとして登録しています。 普通のターミナルからコミットするときのために、gitのエディタもNeoVimに変更してあります。

git config --global alias.st status
git config --global alias.glog "log --all --graph --date=short --decorate=short --pretty=format:'%Cgreen%h %Creset%cd %Cblue%cn %Creset%s'"
git config --global core.editor nvim

5.2. Dockerコンテナ内でCtrl+pを使えるようにする

Dockerではコンテナを離脱するためのショートカットとしてCtrl + p, Ctrl + qが設けられているのですが、これがshellのショートカットCtrl + pと一部重複しているせいで、Dockerコンテナ内のshellでCtrl + pがうまく動作しないという事態が起こります。

これを回避するためショートカットをCtrl + \に変更する設定を~/.docker/config.jsonに追加しています。 ちなみに設定の反映にはdockerデーモンの再起動が必要です。

{
  "auths" : {
    "https://index.docker.io/v1/" : {
    }
  },
  "detachKeys" : "ctrl-\\"
}

5.3. CMakeとclangdを連動させる

NeoVim上でC/C++を書くときはLanguageClient-neovimでclangdから情報を受け取るわけですが、clangdはそのままでは標準ライブラリの情報しか読み取らないのでライブラリのコードの補完などはできません。

そこで、CMakeがfind_packageで読み込んだライブラリの情報をclangdに読み込ませます。 LanguageClient-neovimにclangdの情報を登録するときに以下のようにオプションが追加されるようにしておきます。

let g:LanguageClient_serverCommands = {
    'cpp': ['clangd', '-compile-commands-dir=' . getcwd() . '/build']
}

その上でCMakeLists.txtを書くときに以下の行を追加するようにしています。

set(CMAKE_EXPORT_COMPILE_COMMANDS ON)

すると./build/compile_commands.jsonというファイルにコンパイルコマンドの情報が記録されます。これをclangdが勝手に読み取り、ライブラリの情報なども反映してくれるようになります。


以上、ただただ自分の環境について語るポエム記事をお届けしました。