-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/
2015 Vol.3 ( 2015 年 5 月 22 日 発行 )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
数理システム 最適化メールマガジンでは，数理計画法パッケージ
数理システム Numerical Optimizer をはじめとして，最適化に関する様々
な情報やご案内を提供していきます．
++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++
■ <トピック> 整数計画問題の解法の進展
■ <トピック> 出展のご報告
■ <セミナー> Numerical Optimizer セミナーのご案内
■ < tips > 数理計画問題の豆知識（第 19 回）
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
******************************************************************
■ <トピック> 整数計画問題の解法の進展
******************************************************************
数理計画問題の中でも整数計画問題がビジネスで広く使われていることは
よく知られています．マーケティング，エネルギー問題，シフトスケジュー
リング等あらゆる分野で顔を出す問題で，数理計画問題の中でも「最も取
り扱われている問題クラス」といっても過言ではないかと思います．
Numerical Optimizer V17 ではこの整数計画問題に対する求解速度を大幅
に向上させることに成功しました．改良のポイントはいくつかありますが，
以下にそのうちの一部を挙げます．
- 整数計画問題に対する前処理の強化
- WCSP タブーサーチの分枝限定法への組み込み
- 単体法の改善
前処理の強化では implied cut と呼ばれる変数の関係性（例えば，変数 x
が 0 になったら変数 z が 0 になるという関係）から導かれる切除平面（
人工的な制約式）の生成方法を改善しました．
また，行強化（strengthen rows）という技術で制約式に非ゼロ要素を追加
することによって下界を上昇させ，分枝限定法の探索木をより縮小するこ
とで，求解時間が短くなりました．
WCSP タブーサーチは従来整数変数のみの問題にたいして適用できる独立し
たアルゴリズムでしたが，これを連続変数も扱えるように拡張し，分枝限
定法内部に組み込みました．これにより，より早い段階で実行可能解を見
つけられるようになっただけではなく，従来は見つけられなかったいくつ
かの問題でまた見つけられるようになりました．
単体法の改善では，基底解から基底解に移動する際の，基底解を選択する
ルールに改良を加えることにより，より少ない反復で線形緩和問題を解く
ことができるようになりました．これにより分枝限定法の速度も向上させ
ることができました．
もちろん我々の改善は V17 でとどまるわけではありません．整数計画の
アルゴリズムは日進月歩であり，我々も国内・海外の最新研究結果を調査
しながら独自の成果を入れ込むべく日夜改善に励んでおります．
現在 Numerical Optimizer V18 では以下のような改良を予定しております．
- ヒューリスティクスアルゴリズムの強化
- WCSP タブーサーチアルゴリズムの改善
- 単体法の改善
皆様のお手元の問題がより速く解けるよう，開発者一同これからも改良に
邁進いたします．またより確実な性能検証のため，我々は広くベンチマー
クとなるべく問題を募集しております．
もしお持ちの整数計画問題で「もっと早く解けたら良いのに！」とお困り
の問題などありましたら，是非お知らせください．
（藤井 浩一）
******************************************************************
■ <トピック> 出展のご報告
******************************************************************
5 月 13 日 ～ 15 日に東京ビッグサイトで開催されました第 20 回ビッグ
データ活用展（春）に出展致しました．連日ブース内に沢山の方にお立ち
寄り頂きまして，誠にありがとうございました．データ分析・最適化に対
し，世の中の高まる期待を感じました．今後も皆様のお役に立てるよう，
努力を続けてまいります．
5 月 14 日 ～ 15 日に山梨県甲府市で開催されました日本計算機統計学会
第 29 回 大会にて出展・ソフトウェアデモセッションにて発表させて頂き
ました．統計が中心の学会ですので，Visual R Platform と統計ツール R
からシームレスにコール可能な RNUOPT についてご紹介させて頂きました．
（佐藤 誠）
******************************************************************
■ <セミナー> Numerical Optimizer セミナーのご案内
******************************************************************
---- [ 速報 : スマートグリッドソリューションセミナー開催決定 ] ---
エネルギー事業における統計解析・最適化・シミュレーションの適用に
ついて取り上げるセミナーです．電力需要予測や運転計画など，スマート
グリッドに対する NTT データ数理システムのソリューションをご紹介し
ます．
・スマートグリッドソリューションセミナー
7 月 16 日 (木) 午後
時間・セミナー内容など，詳細が決まり次第 Web ページ
http://www.msi.co.jp/nuopt/
を更新しますので，ご注目ください！
------------------------------------------------------------------
---- [ 開催決定 : スケジューリングソリューションセミナー ] -------
シフトスケジューリングや配送計画など，スケジューリングにまつわる
最適化ソリューションを幅広くご紹介いたします．機械学習を応用した
最新ヒューリスティクスについても取り扱う予定です．
・スケジューリングソリューションセミナー
6 月 17 日 (水) 15:00 ～ 17:00
こちらについても，詳細が決まり次第 Web ページを更新します！
------------------------------------------------------------------
---- [ 大阪セミナーを開催いたします ] ----------------------------
6 月 23 日から 26 日までの 4 日間にわたり，大阪で弊社の様々な
ソリューションをご紹介するセミナーを開催いたします．最適化セミナー
の他，ビッグデータ，シミュレーションに関するセミナーもございます．
・最適化セミナー（Numerical Optimizer 体験・事例紹介）
6 月 23 日 (火) 10:00 ～ 12:00
その他のセミナーについては
スケジュール一覧 http://www.msi.co.jp/event/
カレンダー形式 http://www.msi.co.jp/event/seminar_201504_06.pdf
をご覧ください．
会場 :
AP 梅田大阪
（大阪市北区曽根崎新地 2-3-21 ax ビル 4F）
アクセスマップ
------------------------------------------------------------------
---- [ Numerical Optimizer 定例セミナー開催日程 ] ----------------
その他定例セミナーは以下の通りです．
皆様の参加申し込みをお待ちしております．
・ 5 月 28 日 (木) 13:30 ～ 16:30 最適化セミナー(体験・事例紹介)
・ 6 月 16 日 (火) 13:30 ～ 17:00 スキルアップセミナー・実践編
・ 7 月 17 日 (金) 13:30 ～ 16:30 最適化セミナー(体験・事例紹介)
会場 :
(株) NTT データ数理システム セミナールーム
（東京都新宿区信濃町 35 信濃町煉瓦館 1F）
アクセスマップ
http://www.msi.co.jp/msi/location.html
------------------------------------------------------------------
お申込み・詳細は下記のページをご覧ください．
http://www.msi.co.jp/event/index_nuopt.html
（中野 雄介）
******************************************************************
■ < tips > 数理計画問題の豆知識（第 19 回）
******************************************************************
今回は機械学習と最適化について取り上げます．まず機械学習について，
その中でも教師有り学習を簡単に説明した後，現状，どのような最適化手
法が必要とされ，そして研究されているのか紹介します．
機械学習の目的は
”与えられたデータ（訓練データ）から，未知のデータにも通用する
ような規則やパターンを発見する”
ことです．
教師有り学習の場合はラベル付けされたデータを訓練データとして，デー
タからラベル集合への写像の獲得を目的とします．すると，ラベルが不明
なデータに対しても，獲得した写像からラベルの予測が出来るようになり
ます．
例えば，以下のような訓練データがあれば，メールのスパム判定や，画像
の被写対象を予測する画像認識，音声を文字列に起こす音声認識等が実現
されます．
1. メールのスパム判定
データ：メール文面
ラベル：スパムか否か
2. 画像認識
データ：画像
ラベル：対象物の名称
3. 音声認識
データ：音声
ラベル：文字列
次に，実際にこの様な写像を構成する方法を説明します．
まずは，データとラベルを何かしらの手段で実数ベクトルあるいはスカラー
表現し，実数空間上の写像に限定します．しかし，広い写像空間を探索す
ることは不可能ですので，有限次元空間でパラメトライズされた写像族へ
制限します．以降，この写像族をモデル空間と呼ぶことにします．
このモデル空間内で訓練データに適合する写像を探す訳ですが，その探索
指針（目的関数）には損失関数を使います．損失関数は，一つのデータに
対して予測されたラベルと，実際のラベルとの乖離度を与えます．線形回
帰における二乗誤差関数等がその代表例です．
そして訓練データについての損失関数値の平均（経験損失）を，写像と訓
練データの適合度として，これを最小化します．
この様にして，教師有り機械学習が最適化問題へと帰着されます．
あとは，この最適化問題を厳密に解けば良いように思いますが，常にそう
とは限りません．状況によっては，そこそこの解で厳密な解と同等に十分
な場合があります．
というのは，この最適化誤差の他に，以下のような近似誤差，推定誤差が
あり [1]，これら 3 種の誤差を同時に小さくして，はじめて良い写像が
得られるからです．
近似誤差：
モデル空間が真の写像を含まないことで発生する誤差で，真の写像と
モデル空間内での最適な写像とのギャップです．
※ 訓練データのみから定まる経験損失に対して，全データ，即ちデータ
の分布による平均で定められる関数を期待損失（汎化誤差）と呼び，
この期待損失を最小化する写像を真の写像と呼ぶことにします．
推定誤差：
訓練データに適合させたことで発生する誤差．
モデル空間内における期待損失最小化と経験損失最小化のギャップです．
最適化誤差：
経験損失最小化問題の最適写像と，実際に得られた写像とのギャップ
です．
真の写像と実際に計算して得られる写像の差は，上記 3 種の誤差の和で
抑えられるので，これら全てを小さくすることが目標となります．
どのようにしてそれを実現するのか，近似誤差，推定誤差と計算コストに
ついてのトレードオフ [1] に着目して考えてみます．
モデル空間の大きさ（複雑さ），データ量，最適化誤差を増加させた際の
誤差・計算コストの挙動は以下のようになります．
モデル空間を大きく --->
近似誤差 ：減少
推定誤差 ：増加
計算コスト：増大
データ量を増加 --->
推定誤差 ：減少
計算コスト：増加
最適化誤差を増加 --->
計算コスト：減少
ですので，モデル空間を大きく複雑にし，同時にデータ量を増すことで，
近似誤差および推定誤差は小さくなります．しかし，近似解を得るための
計算コストは増加するので，ここで，複雑かつ大規模な経験損失最小化問
題に耐えうる良い最適化手法が必要となってきます．
現在のような大規模ストレージや高速な計算環境が無かった時代は，推定
誤差を小さくすることは，そもそも現実的ではありませんでした．そのた
め，上記の誤差の観点から，複雑なモデル空間の考慮や精緻な最適化は必
要とされなかったわけです．
反面，パワフルなマシンがある現在は，推定誤差の減少が可能となり，こ
れに伴い複雑なモデルも注目されるようになりました．ディープラーニン
グで用いられる深いニューラルネットワークが代表的で，実験的にもあら
ゆるタスクで過去の結果を塗り替える高パフォーマンスを発揮しています．
以上を踏まえ，機械学習で有効とされる最適化手法を紹介します．
経験損失最小化問題においては，厳密な勾配を用いる再急降下法よりも，
ランダム抽出した一つあるいは少量のデータで定まる確率的勾配も用いる
確率的勾配降下法が好まれます．その理由は以下の 2 点です．
(i) 少量データの場合，推定誤差が大きいので，厳密な解が必要とされず，
計算の軽い確率的勾配降下法が有用．
(ii) 収束率としては，確率的勾配降下法は遅いが，大規模データの場合，
各反復あたりの計算コストの差から，指定された最適誤差の解を得る
ための総計算コストは確率的勾配降下法の方が小さい．
従って，データ量に依存しない確率的な手法が有用とされています．
更に，確率的勾配降下法と同等に反復あたりの計算コストを小さく保ちつ
つも，より分散が小さな勾配の推定量を探索方向として最急降下法と同じ
収束率（線形収束）を達成するアルゴリズムも近年提案されてきています．
凸な経験損失最小化問題では，これらアルゴリズムあるいは座標降下法に
基く手法が最も有用と考えられます．
詳しくは [2-7] および，以下のページをご参照ください．
- "確率的勾配降下法", 数理計画用語集
http://www.msi.co.jp/nuopt/glossary/
term_da265770bed70e5f0a764f3d20c0ce3d242e6467.html
次に一次と二次の確率的な微分を使う最適化手法を比較してみます．
厳密なヘッセ行列あるいは良い近似行列を用いた場合は，二次収束や超一
次収束といった高速な収束率を達成します．しかし，ヘッセ行列を単純に
サンプリングされた少量データから推定した場合，その収束率は著しく損
なわれ，結果的に単純な確率的勾配降下法と同等程度の収束率になってし
まい，反復あたりの計算コストを増加させるだけになってしまいます．
より分散を抑える推定方法が発見されない限り，凸な問題においては一次
の方法に分があると言えます．
一方で，ディープラーニングのような非凸で複雑な関数形を対象とした場
合は，話が少し変わります．
一次の勾配を用いた最適化手法は，方向に依り曲率が大きく異なる関数の
最適化を苦手とします．その為，何かしら曲率を考慮した確率的な最適化
手法が有効となってきます．いくつかの研究方針がありますが，ここでは
2 通りのアプローチを紹介します．
一つは，ニュートン法のような二次の最適化手法のアイディアをうまく取
り入れることです．一次の方法と違い，二次の最適化手法は方向による曲
率の違いを無視せず，曲率の大きな方向へは大きく，曲率が小さい方向へ
は小さく計るメトリックを採用するため，関数の複雑さからの影響を軽減
させます．
しかし，大規模データかつディープラーニングのように高次元な問題の場
合は，ヘッセ行列あるいはその逆行列を陽に持つことは現実的ではありま
せん．CG 法のようにヘッセ行列とベクトルの積のみを扱うアルゴリズムも
研究されていはいますが，やはり計算コストの観点から，まだ十分なもの
が提案されているとは言いづらく，コストを如何に抑えるかという点でも
未だ研究されている最中です．
この方向性の研究は [8-14] 等を参照ください．
もう一つは，ニューラルネットワークで古くから使われているモーメンタ
ム法に関連するものです．モーメンタム法は，現在の反復点までに得られ
た確率的勾配の平均を探索方向とします．こうすることで，曲率の大きな
方向へははじめの内は振動するのですが徐々に振動がキャンセルされてい
きます．一方，曲率の小さな方向へは徐々に大きなステップとなっていき，
結果的に，収束の加速が期待されます．
モーメンタム法は Nesterov の加速法 [15] の類似アルゴリズムとしても
知られています．Nesterov の加速法も関数の形状からの影響を一次の勾配
法より軽減出来ることが知られていますが，二次の方法程ではないにしろ，
その効果を発揮するにはより分散の小さい確率的勾配が必要であることが
理論的に分かっています．
そこで，上述した，分散を軽減させたステップと加速法を組み合わせたア
ルゴリズム [16] も提案されており，私も興味を持って取り組んでいるア
プローチです．
以上，二通りのアプローチを紹介しましたが，いずれもまだ改善の余地が
あると考えおり，今後，どのような手法が提案されスタンダードになって
いくか，楽しみにしているところです．
以上で，機械学習と最適化についての紹介とさせて頂きます．
参考文献：
[1] L.Bottou and O.Bousquet, The Tradeoffs of Large Scale Learning,
2008.
[2] N. Le Roux, M. Schmidt, and F. Bach, A Stochastic Gradient
Method with an Exponential Convergence Rate for Strongly-Convex
Optimization with Finite Training Sets, 2012.
[3] S. Shalev-Shwartz and T. Zhang, Proximal Stochastic Dual
Coordinate Ascent, 2012.
[4] R. Johnson and T. Zhang, Accelerating Stochastic Gradient
Descent using Predictive Variance Reduction, 2013.
[5] A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: A Fast
Incremental Gradient Method with Support for Non-Strongly Convex
Composite Objectives, 2014.
[7] J. Konecny and P. Richtarik, S2GD: Semi-Stochastic Gradient
Descent Methods, 2013.
[8] S. Amari, Natural Gradient works Efficiently in Learning, 1998.
[9] J. Martens, Deep Learning via Hessian-free Optimization, 2010.
[10] R.H. Byrd, G.M. Chin, J. Nocedal, and Y.Wu, Sample size
selection in optimization methods for machine learning, 2012.
[11] R.H. Byrd, G.M. Chin, W. Neveitt, and J. Nocedal, On the use of
stochastic Hessian information in unconstrained optimization,
2013.
[12] Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and
Y. Bengio, Identifying and attacking the saddle point problem
in high-dimensional non-convex optimization, 2014.
[13] R. Pascanu, Y. Dauphin, S. Ganguli, and Y. Bengio, On the
saddle point problem for non-convex optimization, 2014.
[14] J. Martens and R. Grosse, Optimizing Neural Networks with
Kronecker-factored Approximate Curvature. 2015.
[15] Y. Nesterov, Introductory Lectures on Convex Optimization:
A Basic Course, 2004.
[16] A. Nitanda, Stochastic Proximal Gradient Descent with
Acceleration Techniques, 2014.
（二反田 篤史）
==================================================================
※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に
数理システム Numerical Optimizer に関するお問い合わせを頂いたこ
とのある方，および本メールマガジンの配信を希望された方にお送り
しています．
※ バックナンバーはこちらから御覧頂けます．
http://www.msi.co.jp/nuopt/mailmagazine/index.html
※ 本メールマガジンは等幅フォントでお読みになることを推奨します．
※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール
マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp
にお送りください．なお，反映作業の都合上，数日間は旧情報にてメー
ルが届く場合がございます．なにとぞご容赦ください．
発行：株式会社 NTT データ数理システム
<< 数理システム Numerical Optimizer >> 担当
東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階
tel : 03-3358-6681
e-mail : nuopt-info@ml.msi.co.jp
==================================================================
