最小絕對偏差 (Least Absolute Deviations, LAD) 與最小二乘法（假設誤差服從高斯分布）類似：當假設線性回歸的誤差服從拉普拉斯分布時，最小絕對偏差回歸是對參數的最大似然估計。

問題描述

$$\underset{x}{\min }||Wx?y|{|}_1$$
等價于
$$\begin{array}{ll}\min & \nu \\ s.t.& \nu =||Wx?y|{|}_1\end{array}$$
等價于
$$\begin{array}{ll}\min & \nu \\ s.t.& ||Wx?y|{|}_1\le \nu \end{array}$$
等價于
$$\begin{array}{ll}\min & \nu \\ s.t.& Wx?y\le \nu ,\\ & ?Wx+y\le \nu ,\end{array}$$
即
$$\begin{array}{ll}\min & \nu \\ s.t.& Wx?\nu \le y,\\ & ?Wx?\nu \le ?y,\end{array}$$
即
$$\begin{array}{ll}\min & {\left[\begin{array}{ll}0& I\end{array}\right]}^{?}\left[\begin{array}{l}x\\ \nu \end{array}\right]\\ & \\ s.t.& \left[\begin{array}{cc}W& ?I\\ ?W& ?I\end{array}\right]\left[\begin{array}{c}x\\ \nu \end{array}\right]\le \left[\begin{array}{c}y\\ ?y\end{array}\right]\end{array}$$

可見，該問題可以轉化成標準的線性規劃問題！！！

cvxopt 求解器

#Sources: http://cvxopt.org/examples/mlbook/l1.html?highlight=l1from cvxopt import blas, lapack, solvers from cvxopt import matrix, spdiag, mul, div, sparse from cvxopt import spmatrix, sqrt, basedef l1(P, q):P,q = matrix(P), matrix(q)m, n = P.sizec = matrix(n*[0.0] + m*[1.0])h = matrix([q, -q])def Fi(x, y, alpha = 1.0, beta = 0.0, trans = 'N'): if trans == 'N':u = P*x[:n]y[:m] = alpha * ( u - x[n:]) + beta*y[:m]y[m:] = alpha * (-u - x[n:]) + beta*y[m:]else:y[:n] = alpha * P.T * (x[:m] - x[m:]) + beta*y[:n]y[n:] = -alpha * (x[:m] + x[m:]) + beta*y[n:]def Fkkt(W): d1, d2 = W['d'][:m], W['d'][m:]D = 4*(d1**2 + d2**2)**-1A = P.T * spdiag(D) * Plapack.potrf(A)def f(x, y, z):x[:n] += P.T * ( mul( div(d2**2 - d1**2, d1**2 + d2**2), x[n:]) + mul( .5*D, z[:m]-z[m:] ) )lapack.potrs(A, x)u = P*x[:n]x[n:] = div( x[n:] - div(z[:m], d1**2) - div(z[m:], d2**2) + mul(d1**-2 - d2**-2, u), d1**-2 + d2**-2 )z[:m] = div(u-x[n:]-z[:m], d1)z[m:] = div(-u-x[n:]-z[m:], d2)return fuls = +qlapack.gels(+P, uls)rls = P*uls[:n] - q x0 = matrix( [uls[:n], 1.1*abs(rls)] ) s0 = +hFi(x0, s0, alpha=-1, beta=1) if max(abs(rls)) > 1e-10: w = .9/max(abs(rls)) * rlselse: w = matrix(0.0, (m,1))z0 = matrix([.5*(1+w), .5*(1-w)])dims = {'l': 2*m, 'q': [], 's': []}s0 = np.array(s0)s0[s0<=0]=1e-8s0 = matrix(s0)sol = solvers.conelp(c, Fi, h, dims, kktsolver = Fkkt, primalstart={'x': x0, 's': s0}, dualstart={'z': z0})return sol['x'][:n]

測試

A = np.random.random((10,10)) x = np.random.randn((10)) y = A @ x n = np.random.laplace(0, 0.01, 10) y += nres = l1(A,y) res = np.squeeze(res)plt.subplot(1,2,1) plt.bar(np.arange(len(res)),res, alpha=0.5) plt.title('solution') plt.subplot(1,2,2) plt.bar(np.arange(len(x)),x, alpha=0.5) plt.title('ground truth')

總結

以上是生活随笔為你收集整理的最小绝对偏差（LAD）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。