Huber损失最小化学习法

Huber regression
In least square learning methods, we make use of $\ell_{2}$ loss to make sure that we get a suitable outcome. However, in the robust point of view, it is always better to make use of the least absolute as the main criterion, i.e.

$$\hat{\theta}_{LA}=\arg\min_{\theta}J_{LA}(\theta),\quad J_{LA}(\theta)=\sum_{i=1}^{n}|r_{i}|$$
where $r_{i}=f_{\theta}(x_{i})-y_{i}$ is the residual error. By doing so, it is possible to make the learning method more robust at the cost of accuracy.
In order to balance robustness and accuracy, Huber loss may be a good alternative:
$$\rho\mathrm{Huber}(r)=\left\{\ \begin{aligned}&r^{2}/2 \quad &(|r|\leq\eta)\\ &\eta|r|-\eta^{2}/2\quad&(|r|>\eta)\end{aligned} \right.$$
Then the optimization goal turns out to be:
$$\min_{\theta}J(\theta),\quad J(\theta)=\sum_{i=1}^{n}\rho\mathrm{Huber}(r_{i})$$
As usual, take the linear parameterized model as an example:
$$f_{\theta}(x)=\sum_{j=1}^{b}\theta_{j}\phi_{j}(x)=\theta^{T}\phi(x)$$
For simplicity, we omit the details and give the final outcome (more details needed? refer to $\ell_{1}$ constrained LS):
$$\hat{\theta}=\arg\min_{\theta}\tilde{J}(\theta),\quad \tilde{J}(\theta)=\frac{1}{2}\sum_{i=1}^{n}\tilde{\omega}_{i}r_{i}+C$$
where $\tilde{\omega}_{i}=\left\{ \begin{aligned} &1 &(|\tilde{r}_{i}|\leq \eta)\\ &\eta/|\tilde{r}_{i}| &(|\tilde{r}_{i}|> \eta)\end{aligned} \right.$ and $C=\sum_{i:|\tilde{r}_{i}|>\eta}(\eta|\tilde{r}_{i}|/2-\eta^{2}/2)$ are independent of $\theta$.
Therefore, the solution can be formulated as:
$$\hat{\theta}=(\Phi^{T}\tilde{W}\Phi)^{\dagger}\Phi^{T}\tilde{W}y$$ where $\tilde{W}=\mathrm{diag}(\tilde{\omega}_{1},\dots,\omega_{n})$.
By iteration, we can solve $\hat{\theta}$ as an estimation of $\theta$. The corresponding MATLAB codes are given below:

n=50; N=1000;
x=linspace(-3,3,n)'; X=linspace(-4,4,N)';
y=x+0.2*randn(n,1); y(n)=-4;

p(:,1)=ones(n,1); p(:,2)=x; t0=p\y; e=1;
for o=1:1000
    r=abs(p*t0-y); w=ones(n,1); w(r>e)=e./r(r>e);
    t=(p'*(repmat(w,1,2).*p))\(p'*(w.*y));
    if norm(t-t0)<0.001, break, end
    t0=t;
end
P(:,1)=ones(N,1); P(:,2)=X; F=P*t;

figure(1); clf; hold on; axis([-4,4,-4.5,3.5]);
plot(X,F,'g-'); plot(x,y,'bo');

Tukey regression
The Huber loss combined $\ell_{1}$ loss and $\ell_{2}$ loss to balance robustness and accuracy. Since $\ell_{1}$ loss is concerned, the outliers may have an enormous impact on the final outcome. To tackling that, Tukey may be a considerable alternative:

$$\rho\mathrm{Tukey}(r)=\left\{ \begin{aligned} &\left(1-[1-r^{2}/\eta^{2}]^{3}\right)\eta^{2}/6 & (|r|\leq \eta) \\ &\eta^{2}/6 \quad & (|r|>\eta) \end{aligned}\right.$$
Of course, the Tukey loss is not a convex funciton, that is to say, there may be serveral local optimal solution. In actual applications, we apply the following weights:
$$\omega=\left\{\begin{aligned}&(1-r^{2}/\eta^{2})^{2} & \quad (|r|\leq \eta)\\ &0 &(|r|> \eta) \end{aligned}\right.$$
Hence the outliers can no longer put any impact on our estimation.