シラバス参照

講義概要/Course Information
2024/05/03 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)		 データ解析最適化論
英文授業科目名
/Course title (English)		 Advanced Topics in Data Analysis Optimization
科目番号
/Code
開講年度
/Academic year		 2019年度 開講年次
/Year offered		 全学年
開講学期
/Semester(s) offered		 後学期 開講コース・課程
/Faculty offering the course		 博士前期課程、博士後期課程
授業の方法
/Teaching method		 講義 単位数
/Credits		 2
科目区分
/Category		 大学院専門教育科目 - 専門科目Ⅱ
開講類・専攻
/Cluster/Department		 情報・ネットワーク工学専攻
担当教員名
/Lecturer(s)		 ○笠井　裕之
居室
/Office		 東2-611
公開E-mail
/e-mail		 笠井<hiroyuki.kasai@waseda.jp>
授業関連Webページ
/Course website		 http://www.kasailab.com/
更新日
/Last update		 2019/10/07 07:38:24 更新状況
/Update status		 公開中
/now open to public
講義情報/Course Description
主題および
達成目標（2,000文字以内）
/Themes and goals（up to 2,000 letters）		 This lecture addresses the fundamentals and algorithms of optimization theory which is one of core technologies of machine learning. Especially, non-linear programming is focused. Note that the topics related with combinational optimization, non-differential optimization, discrete optimization and linear programing are not provided.

講義では，データ解析のための機械学習（データ最適化手法）に関する技術と理論について学習する．
前もって履修
しておくべき科目（1,000文字以内）
/Prerequisites（up to 1,000 letters）		 Linear algebra
線形代数
前もって履修しておくこ
とが望ましい科目（1,000文字以内）
/Recommended prerequisites and preparation（up to 1,000 letters）		 Linear algebra
線形代数
教科書等（1,000文字以内）
/Course textbooks and materials（up to 1,000 letters）		 Not special
特に無し
授業内容と
その進め方（2,000文字以内）
/Course outline and weekly schedule（up to 2,000 letters）		 以下の内容に従って講義を行うが，学生の理解度に合わせて適宜内容を調整する．

1：Introduction

- Big and high-dimensional data analysis and its issues
　ビッグデータ＆高次元データ解析とその問題
- Linear and logistic regression
　線形回帰＆ロジスティック回帰
- Optimization technique basis
　最適化技術の基礎

2: Mathematic preliminaries

- Space R^n and R^{mxn} space
　数ベクトル空間，行列空間
- Inner product and norms
　内積とノルム
- Eigenvalues and eigenvectors
　固有値と固有ベクトル
- Basic topological concepts
　位相の基礎
- Differentiability
　微分可能性
- Linear/quadratic approximation theorem
　一次＆二次近似定理

3: Optimality conditions for unconstrained optimization

- Global and local optima
　大域的＆局所領域の局値
- Classification of matrices
　様々な行列
- First/second order optimality conditions
　一次＆二次最適性条件
- Quadratic functions
　二次関数

4: Least squares

- Overdetermined systems
　優決定系のシステム
- Data fitting
　データフィッティング
- Regularized least squares
　正則項付き最小自乗法
- De-noising
　ノイズ除去問題
- Numerical demonstrations
　数値例デモ

5: Gradient method 1

- Descent direction
　降下方向
- Gradient method
　勾配法
- Condition number
　条件数
- Scaled gradient (Diagonal scaling)
　スケールド勾配法
- Numerical demonstrations
　数値例デモ

6: Gradient method 2

- Line search (Exact, Backtracking, Wolf conditions, etc.)
　直線探索
- Convergence analysis (Lipschitz continuity, the descent lemma, sub-linear convergence rate)
　最急降下法の収束解析

7: Newton's method

- Pure Newton's method
　ニュートン法
- Convergence analysis (Quadratic local convergence rate)
　ニュートン法の収束解析
- Damped Newton's method
　Damped ニュートン法
- Cholesky factorization based Newton's method
　コレスキー分解に基づくニュートン法
- Numerical demonstrations
　数値例デモ

8: Convex sets and functions

- Definition and examples of convex sets
　凸集合
- First/second order order characterizations of convex functions
　凸関数の特性

9: Convex optimization 1

- Stationarity
- Orthogonal projection
　直交射影
- Gradient projection method
　勾配射影法

10: Convex optimization 2

- Convergence analysis
　最急降下法の凸関数における収束解析

11: Optimality conditions for linearly constrained problems

- Separation and alternative theorems (Farkas' lemma)
　分離定理，二者択一定理
- KKT conditions
　KKT条件
- Orthogonal regression
　直交線形回帰

12: KKT conditions

- Fritz-John theorem
- KKT conditions for inequality/equality constrained problem
　不等式・等式制約問題のためのKKT条件
- KKT conditions for convex optimization problem
　凸問題のためのKKT条件

13: Duality

- Motivations
- Definition
- Weak/strong duality in convex case
　凸問題における弱・強双対定理
- Examples (LP, QP, Orthogonal projection, Chebyshev center,  Sum of norms, Denoising, etc.)

14: Advanced topics 1

- Stochastic optimization (SGD, SAG, SVRG, etc.)
　確率的勾配法等

15: Advanced topics 2

- Proximal (Stochastic) optimization methods
　近接勾配法
- ADMM
　交互方向乗数法
- Optimization on Riemannian manifolds
　多様体最適化法
実務経験を活かした
授業内容
(実務経験内容も含む)
/Course content utilizing practical experience
授業時間外の学習
（予習・復習等）（1,000文字以内）
/Preparation and review outside class（up to 1,000 letters）		 最適化理論に関わる書籍や論文などを理解する．
成績評価方法
および評価基準
（最低達成基準を含む）
（1,000文字以内）
/Evaluation and grading
（up to 1,000 letters）		 - Evaluation method
Middle term report：50%
Final term report：50%

- Evaluation metrics
How deeply students understand fundamentals and algorithms of optimization theory.
オフィスアワー：
授業相談（1,000文字以内）
/Office hours（up to 1,000 letters）		 10:40-11:20 on Monday
学生へのメッセージ（1,000文字以内）
/Message for students（up to 1,000 letters）		 The topics in the class are closely related with "big-data" analysis, signal processing and machine learning techniques.

大規模データの機械学習や信号処理，統計学習などの基盤技術です．
その他
/Others		 - Students who are interested in machine learning, pattern recognition, and big data analysis are welcome.
　機械学習，パターン認識，ビッグデータ解析に興味のある学生に適しています．
- It is recommended to contact the lecturer by e-mail if you have any questions.
　質問等があれば，教員にコンタクトしてください．
- The spoken language can be English if less-than one non-Japanese student attends.
　日本語の理解が難しい学生がいる場合には，英語で講義を行います．
- Black board is used.
　第１回以外は，黒板で講義を行います．
- MATLAB simulation tasks are provided to students for their deeper understandings.
　MATLABでの演習課題が出る場合があります．
キーワード
/Keywords		 Optimization problem, Non-linear programming, Gradient, Hessian, Convex set/function, optimality conditions, Iterative gradient descent fundamentals,  Line search methods (Back-tracking, Armijo condition), Steepest descent, Newton's method,  Scaled/Preconditioning descent methods, Stochastic gradient descent, KKT conditions, Duality

最適化問題，非線形問題，勾配，へシアン，凸集合/凸関数，最適性条件，反復勾配法，直線探索，最急降下法，前処理勾配法，確率的勾配法，KKT条件，双対定理