Numerical Optimization

梯度：

不仅仅是f(x)在某一点变化最快的方向，而且是上升最快的方向.

梯度下降法：

逆着梯度，下降最快，又叫最速下降法.
迭代公式：
\mathbf{b} = \mathbf{a}-\gamma\nabla F(\mathbf{a})
r是步长。

牛顿法：

牛顿法最初用于求解方程根 f(x) = 0。
首先得到一个初始解 x0，
一阶展开：f(x) ≈ f(x0)+(x－x0)f'(x0)
令 f(x0)+(x－x0)f'(x0) = 0 
求解得到x，相比于x0，f(x)<f(x0)

最优化问题中,牛顿法首先则是将问题转化为求 f‘(x) = 0 这个方程的根。
首先得到一个初始解 x0，
一阶展开：f ’(x) ≈ f ‘(x0)+(x－x0)f '’(x0)
令 f ‘(x0)+(x－x0)f '’(x0) = 0 
求解得到x，相比于x0，f ‘(x)<f ’(x0)
最小化f（x）之高维情况：
\mathbf{x}_{n+1} = \mathbf{x}_n - \gamma[H f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n).
梯度 代替了低维情况中的一阶导
Hessian矩阵代替了二阶导
求逆 代替了除法

梯度下降法（红色）总是沿着当前点最快下降的方向（几乎垂直于等高线），相当于贪心算法。
牛顿法利用了曲面本身的信息，能够更直接，更快的收敛。

高斯牛顿法：
高斯牛顿法实际上是牛顿法的在求解非线性最小二乘问题时的一个特例。
目标函数：
S(\boldsymbol \beta)= \sum_{i=1}^m r_i^2(\boldsymbol \beta).
迭代公式：
\boldsymbol\beta^{(s+1)} = \boldsymbol\beta^{(s)} - \mathbf H^{-1} \mathbf g \,
和牛顿法中的最优化问题高维迭代公式一样

目标函数可以简写：
 S = \sum_{i=1}^m r_i^2,

梯度向量在方向上的分量：

g_j=2\sum_{i=1}^m r_i\frac{\partial r_i}{\partial \beta_j}.                  （1）

Hessian 矩阵的元素则直接在梯度向量的基础上求导：
H_{jk}=2\sum_{i=1}^m \left(\frac{\partial r_i}{\partial \beta_j}\frac{\partial r_i}{\partial \beta_k}+r_i\frac{\partial^2 r_i}{\partial \beta_j \partial \beta_k} \right).
高斯牛顿法的一个小技巧是，将二次偏导省略，于是：
H_{jk}\approx 2\sum_{i=1}^m J_{ij}J_{ik}（2）
将(1)(2)改写成 矩阵相乘形式：
\mathbf g=2\mathbf{J_r}^\top \mathbf{r}, \quad \mathbf{H} \approx 2 \mathbf{J_r}^\top \mathbf{J_r}.\,
其中 Jr 是雅克比矩阵,r是 ri 组成的列向量。
代入牛顿法高维迭代方程的基本形式，得到高斯牛顿法迭代方程：
\boldsymbol{\beta}^{(s+1)} = \boldsymbol\beta^{(s)}+\Delta;\quad \Delta = -\left( \mathbf{J_r}^\top \mathbf{J_r} \right)^{-1} \mathbf{J_r}^\top \mathbf{r}.
即
\boldsymbol \beta^{(s+1)} = \boldsymbol \beta^{(s)} - \left(\mathbf{J_r}^\top \mathbf{J_r} \right)^{-1} \mathbf{ J_r} ^\top \mathbf{r}(\boldsymbol \beta^{(s)})，\mathbf{J_r} = \frac{\partial r_i (\boldsymbol \beta^{(s)})}{\partial \beta_j}

高斯牛顿法只能用于最小化平方和问题，但是优点是，不需要计算二阶导数

Comments

Post a Comment

Popular posts from this blog

Reading CLIP

Learning directly from raw text about images is promising which leverages a much broader source of supervision. Task: predicting which caption goes with which image is an efficient and scalable way to learn SOTA image representations from scratch on a dataset of pairs. After pre-training, natural language is used to is used to reference learned visual concepts enabling zero-shot transfer of the model to downstream tasks.   [Paper Source]  https://cdn.openai.com/papers/Learning_Transferable_Visual_Models_From_Natural_Language.pdf Radford, A., Kim, J.W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J. and Krueger, G., 2021. Learning transferable visual models from natural language supervision.  arXiv preprint arXiv:2103.00020 .
Read more

Reading CutPaste

 CutPaste: a simple data augmentation strategy that cuts an image patch and pastes at a random location of a large image. Dataset: MVTec anomaly detection dataset Aim: detect various types of real-world defects [ Code ] Paper Source:  https://openaccess.thecvf.com/content/CVPR2021/papers/Li_CutPaste_Self-Supervised_Learning_for_Anomaly_Detection_and_Localization_CVPR_2021_paper.pdf
Read more

OOD-related papers

Deep One-Class Classification, ICLR 2021 [ Paper ] [ Code ] Google AI [ Blog ] [ Code ] Learning from Failure: Training Debiased Classifier from Biased Classifier [ Paper ] [ Code ] NeurIPS 2020 Learning Debiased Representation via Disentangled Feature Augmentation [ Paper ] [ Code ] NeurIPS 2021 Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization [ Paper ] Explainable Deep One-class Classification [ Paper ] GAN Ensemble for Anomaly Detection [ Paper ] Neural Transformation Learning for Deep Anomaly Detection Beyond Images [ Paper ] Learning Semantic Context from Normal Samples for Unsupervised Anomaly Detection Dual Compositional Learning in Interactive Image Retrieval [*] SSL  Drop, Swap, and Generate: A Self-Supervised Approach for Generating Neural Activity [ Paper ] [ Code ] NeurIPS 2021 Unsupervised Learning of Discriminative Attributes and Visual Representations [ Paper ] CVPR2016 Common Visual Pattern Dis...
Read more