Базовые знания, необходимые для прочтения этой статьи: алгоритм линейной регрессии, немного знаний в области программирования.
Введение
В предыдущем разделе мы узнали, что одним из способов решения мультиколлинеарности является регуляризация функции стоимости.Один из алгоритмов регуляризации называется алгоритмом регрессии Риджа. Теперь давайте изучим другой алгоритм регуляризации —Алгоритм регрессии Лассо1(Алгоритм регрессии Лассо), полное название LASSO — алгоритм оператора наименьшей абсолютной усадки и выбора (оператор наименьшей абсолютной усадки и выбора).
2. Введение в модель
Давайте сначала рассмотрим функцию стоимости гребневой регрессии, добавив квадрат L2-нормы вектора w с коэффициентом штрафа λ к исходной стандартной функции стоимости линейной регрессии:
Алгоритм регрессии Лассо также добавляет обычный член, как регрессия гребня, но он изменен, чтобы добавить L1-норму вектора w со штрафным коэффициентом λ в качестве штрафного члена (значение L1-нормы состоит в том, что каждый элемент вектор w является абсолютно значимым), поэтому эту регуляризацию также называют L1-регуляризацией.
также заключается в том, чтобы найти размер w при минимизации функции стоимости:
Поскольку L1-норма вектора добавочная, а в ней есть абсолютное значение, функция стоимости не везде выводима, поэтому нет возможности напрямую получить аналитическое решение w путем прямого вывода. Ниже описаны два метода решения весового коэффициента w:Координатный метод спуска2(координатный спуск),регрессия наименьшего угла3(Регрессия по наименьшему углу, LARS)
3. Шаги алгоритма
Координатный метод спуска:
Суть метода координатного спуска такая же, как и его название, заключающееся в постепенном приближении к оптимальному решению путем итеративного обновления значения весового коэффициента вдоль определенного направления координатной оси.
Конкретные шаги:
(1) Инициализируйте весовой коэффициент w, такой как нулевой вектор.
(2) Перебрать все весовые коэффициенты, взять один из весовых коэффициентов в качестве переменной по очереди, а остальные весовые коэффициенты в результате предыдущего вычисления зафиксировать как константу и найти оптимальное решение в случае только одного веса коэффициент переменный в текущих условиях.
В k-й итерации способ обновления весового коэффициента следующий:
(3) Шаг (2) является полной итерацией, когда все весовые коэффициенты меняются незначительно или достигают максимального числа итераций, итерация завершается.
By Nicoguaro - Own workКак показано на рисунке выше, другие весовые коэффициенты фиксируются на каждой итерации, обновляются только в направлении одной из осей координат, и, наконец, достигается оптимальное решение.
Регрессия наименьшего угла:
Метод регрессии с наименьшим углом — это метод выбора признаков, который вычисляет корреляцию каждого признака и постепенно вычисляет оптимальное решение с помощью математических формул.
Конкретные шаги:
(1) Инициализируйте весовой коэффициент w, такой как нулевой вектор.
(2) Инициализируйте остаточный вектор остатка как целевой вектор метки y - Xw, Поскольку w является нулевым вектором в это время, остаточный вектор равен целевому вектору метки y
(3) Выберите собственный вектор x_i с наибольшей корреляцией с вектором невязки, найдите набор весовых коэффициентов w вдоль направления собственного вектора xi, и другой собственный вектор x_j с наибольшей корреляцией с вектором невязки создаст новую невязку. корреляция между остатком вектора и двумя собственными векторами равна (то есть вектор остатка равен биссектрисе угла двух собственных векторов), и вектор остатка пересчитывается.
(4) Повторите шаг (3), продолжайте находить набор весовых коэффициентов w, чтобы третий собственный вектор x_k с наибольшей корреляцией с вектором невязки делал новый вектор невязки остаточным, а три собственных вектора имели одинаковую корреляцию (т.е. , остаточный вектор равен изометрическому вектору этих трех собственных векторов) и так далее.
(5) Когда остаточная невязка вектора достаточно мала или все векторы признаков были выбраны, завершите итерацию.
На приведенном выше рисунке показана ситуация, когда собственных векторов всего два: начальный вектор невязки равен y_2, где корреляция между вектором x_1 и вектором невязки наибольшая (угол между векторами наименьший), а θ_11 находится чтобы сделать новый остаточный вектор y_2 - x_1 * θ_11 биссектриса угла x_1 и x_2 (u_2 на рисунке), в это время w1 = θ_11, w2 = 0. Наконец, набор θ_21 и θ_22 находится таким образом, что новый вектор невязки y_2 - x_1 * θ_11 - (x_1 * θ_21 + x_2 * θ_22) был как можно меньше, в это время w1 = θ_11 + θ_21, w2 = θ_22. Все собственные векторы были выбраны, поэтому завершите итерацию.
Метод координатного спуска относительно легче понять, чем метод регрессии по наименьшему углу, и одновременно необходимо учитывать только один весовой коэффициент. Правило регрессии наименьшего угла уменьшает количество итераций с помощью некоторых умных математических формул, делая его вычислительную сложность в наихудшем случае похожей на метод наименьших квадратов.
4. Доказательство принципа
Функция стоимости регрессии Лассо выпукла
также необходимо доказать:
Левая часть неравенства :
Правая часть неравенства :
(1) Первая половина обеих частей неравенства согласуется со стандартной линейной регрессией, и необходимо только доказать, что оставшаяся разность больше или равна нулю
(2) В силу положительной однородности векторной нормы коэффициент при постоянном члене можно умножить в
(3) Поместите λ вне круглых скобок
(4) Согласно определению векторной нормы, выполнение неравенства треугольника должно быть больше или равно нулю
Размер λ искусственно контролируется, и окончательный результат должен быть больше или равен нулю в диапазоне действительных чисел, и доказательство завершено.
Математическая формула метода наименьшей регрессии
Найдите биссектрису единичного угла:
(1) Пусть вектор биссектрисы единичного угла равен u_A, который можно рассматривать как линейную комбинацию выбранных векторов признаков, а нижний индекс A представляет набор порядковых номеров выбранных признаков.
(2) Поскольку угол между каждым выбранным собственным вектором и вектором биссектрисы угла одинаков, каждый элемент вектора после скалярного произведения собственного вектора и вектора биссектрисы угла должен быть одинаковым, 1_A - это вектор, все элементы которого равны 1 , а z постоянно
(3) По формуле (2) вектор коэффициентов ω_A линейной комбинации может быть выражен
(1) Вектор биссектрисы угла u_A является единичным вектором, поэтому его длина равна 1
(2) Переписать его в виде вектора
(3) Вектор коэффициентов ω_A линейной комбинации, приведенной на предыдущем шаге
(4) По свойству транспонирования скобки первого слагаемого можно упростить, а константу z предложить
(5) Матрица умножается на свою обратную матрицу как на единичную матрицу, поэтому ее можно упростить
(6) Окончательно решается выражение для константы z
(1) Умножьте транспонированный собственный вектор на собственный вектор и обозначьте его G_A
(2) Введите G_A, чтобы получить выражение z
(3) Введите G_A, чтобы получить выражение ω_A
Умножьте X_A на ω_A, чтобы получить выражение биссектрисы угла u_A, чтобы можно было получить вектор биссектрисы единичного угла. Более подробное доказательство см.Диссертация Брэдли Эфрона4.
Найдите длину вектора биссектрисы угла:
(1) μ_A представляет текущее прогнозируемое значение, а длина γ обновляется в направлении вектора биссектрисы угла
(2) C представляет корреляцию между собственным вектором и вектором невязки, который является скалярным произведением двух векторов, и подводится к формуле (1), чтобы получить обновленное выражение корреляции
(3) Когда собственный вектор является выбранным собственным вектором, поскольку произведение каждого собственного вектора и вектора биссектрисы угла одинаково, оно равно z
(4) Вычислить произведение каждого собственного вектора и вектора биссектрисы угла
(5) Если собственный вектор не является выбранным собственным вектором, используйте a для ввода (2)
(6) Чтобы добавить следующий вектор признаков, абсолютные значения (3) и (5) должны быть равны, чтобы гарантировать, что корреляция после следующего обновления также будет такой же.
(7) Решить выражение для γ
Это дает выражение для γ, которое представляет собой длину вектора биссектрисы угла. Более подробное доказательство см.Диссертация Брэдли Эфрона4.
Пять, реализация кода
Используйте Python для реализации алгоритма регрессии Лассо (метод координатного спуска):
def lassoUseCd(X, y, lambdas=0.1, max_iter=1000, tol=1e-4):
"""
Lasso回归,使用坐标下降法(coordinate descent)
args:
X - 训练数据集
y - 目标标签值
lambdas - 惩罚项系数
max_iter - 最大迭代次数
tol - 变化量容忍值
return:
w - 权重系数
"""
# 初始化 w 为零向量
w = np.zeros(X.shape[1])
for it in range(max_iter):
done = True
# 遍历所有自变量
for i in range(0, len(w)):
# 记录上一轮系数
weight = w[i]
# 求出当前条件下的最佳系数
w[i] = down(X, y, w, i, lambdas)
# 当其中一个系数变化量未到达其容忍值,继续循环
if (np.abs(weight - w[i]) > tol):
done = False
# 所有系数都变化不大时,结束循环
if (done):
break
return w
def down(X, y, w, index, lambdas=0.1):
"""
cost(w) = (x1 * w1 + x2 * w2 + ... - y)^2 + ... + λ(|w1| + |w2| + ...)
假设 w1 是变量,这时其他的值均为常数,带入上式后,其代价函数是关于 w1 的一元二次函数,可以写成下式:
cost(w1) = (a * w1 + b)^2 + ... + λ|w1| + c (a,b,c,λ 均为常数)
=> 展开后
cost(w1) = aa * w1^2 + 2ab * w1 + λ|w1| + c (aa,ab,c,λ 均为常数)
"""
# 展开后的二次项的系数之和
aa = 0
# 展开后的一次项的系数之和
ab = 0
for i in range(X.shape[0]):
# 括号内一次项的系数
a = X[i][index]
# 括号内常数项的系数
b = X[i][:].dot(w) - a * w[index] - y[i]
# 可以很容易的得到展开后的二次项的系数为括号内一次项的系数平方的和
aa = aa + a * a
# 可以很容易的得到展开后的一次项的系数为括号内一次项的系数乘以括号内常数项的和
ab = ab + a * b
# 由于是一元二次函数,当导数为零时,函数值最小值,只需要关注二次项系数、一次项系数和 λ
return det(aa, ab, lambdas)
def det(aa, ab, lambdas=0.1):
"""
通过代价函数的导数求 w,当 w = 0 时,不可导
det(w) = 2aa * w + 2ab + λ = 0 (w > 0)
=> w = - (2 * ab + λ) / (2 * aa)
det(w) = 2aa * w + 2ab - λ = 0 (w < 0)
=> w = - (2 * ab - λ) / (2 * aa)
det(w) = NaN (w = 0)
=> w = 0
"""
w = - (2 * ab + lambdas) / (2 * aa)
if w < 0:
w = - (2 * ab - lambdas) / (2 * aa)
if w > 0:
w = 0
return w
Используйте Python для реализации алгоритма регрессии Лассо (регрессия по наименьшему углу):
def lassoUseLars(X, y, lambdas=0.1, max_iter=1000):
"""
Lasso回归,使用最小角回归法(Least Angle Regression)
论文:https://web.stanford.edu/~hastie/Papers/LARS/LeastAngle_2002.pdf
args:
X - 训练数据集
y - 目标标签值
lambdas - 惩罚项系数
max_iter - 最大迭代次数
return:
w - 权重系数
"""
n, m = X.shape
# 已被选择的特征下标
active_set = set()
# 当前预测向量
cur_pred = np.zeros((n,), dtype=np.float32)
# 残差向量
residual = y - cur_pred
# 特征向量与残差向量的点积,即相关性
cur_corr = X.T.dot(residual)
# 选取相关性最大的下标
j = np.argmax(np.abs(cur_corr), 0)
# 将下标添加至已被选择的特征下标集合
active_set.add(j)
# 初始化权重系数
w = np.zeros((m,), dtype=np.float32)
# 记录上一次的权重系数
prev_w = np.zeros((m,), dtype=np.float32)
# 记录特征更新方向
sign = np.zeros((m,), dtype=np.int32)
sign[j] = 1
# 平均相关性
lambda_hat = None
# 记录上一次平均相关性
prev_lambda_hat = None
for it in range(max_iter):
# 计算残差向量
residual = y - cur_pred
# 特征向量与残差向量的点积
cur_corr = X.T.dot(residual)
# 当前相关性最大值
largest_abs_correlation = np.abs(cur_corr).max()
# 计算当前平均相关性
lambda_hat = largest_abs_correlation / n
# 当平均相关性小于λ时,提前结束迭代
# https://github.com/scikit-learn/scikit-learn/blob/2beed55847ee70d363bdbfe14ee4401438fba057/sklearn/linear_model/_least_angle.py#L542
if lambda_hat <= lambdas:
if (it > 0 and lambda_hat != lambdas):
ss = ((prev_lambda_hat - lambdas) / (prev_lambda_hat - lambda_hat))
# 重新计算权重系数
w[:] = prev_w + ss * (w - prev_w)
break
# 更新上一次平均相关性
prev_lambda_hat = lambda_hat
# 当全部特征都被选择,结束迭代
if len(active_set) > m:
break
# 选中的特征向量
X_a = X[:, list(active_set)]
# 论文中 X_a 的计算公式 - (2.4)
X_a *= sign[list(active_set)]
# 论文中 G_a 的计算公式 - (2.5)
G_a = X_a.T.dot(X_a)
G_a_inv = np.linalg.inv(G_a)
G_a_inv_red_cols = np.sum(G_a_inv, 1)
# 论文中 A_a 的计算公式 - (2.5)
A_a = 1 / np.sqrt(np.sum(G_a_inv_red_cols))
# 论文中 ω 的计算公式 - (2.6)
omega = A_a * G_a_inv_red_cols
# 论文中角平分向量的计算公式 - (2.6)
equiangular = X_a.dot(omega)
# 论文中 a 的计算公式 - (2.11)
cos_angle = X.T.dot(equiangular)
# 论文中的 γ
gamma = None
# 下一个选择的特征下标
next_j = None
# 下一个特征的方向
next_sign = 0
for j in range(m):
if j in active_set:
continue
# 论文中 γ 的计算方法 - (2.13)
v0 = (largest_abs_correlation - cur_corr[j]) / (A_a - cos_angle[j]).item()
v1 = (largest_abs_correlation + cur_corr[j]) / (A_a + cos_angle[j]).item()
if v0 > 0 and (gamma is None or v0 < gamma):
gamma = v0
next_j = j
next_sign = 1
if v1 > 0 and (gamma is None or v1 < gamma):
gamma = v1
next_j = j
next_sign = -1
if gamma is None:
# 论文中 γ 的计算方法 - (2.21)
gamma = largest_abs_correlation / A_a
# 选中的特征向量
sa = X_a
# 角平分向量
sb = equiangular * gamma
# 解线性方程(sa * sx = sb)
sx = np.linalg.lstsq(sa, sb)
# 记录上一次的权重系数
prev_w = w.copy()
d_hat = np.zeros((m,), dtype=np.int32)
for i, j in enumerate(active_set):
# 更新当前的权重系数
w[j] += sx[0][i] * sign[j]
# 论文中 d_hat 的计算方法 - (3.3)
d_hat[j] = omega[i] * sign[j]
# 论文中 γ_j 的计算方法 - (3.4)
gamma_hat = -w / d_hat
# 论文中 γ_hat 的计算方法 - (3.5)
gamma_hat_min = float("+inf")
# 论文中 γ_hat 的下标
gamma_hat_min_idx = None
for i, j in enumerate(gamma_hat):
if j <= 0:
continue
if gamma_hat_min > j:
gamma_hat_min = j
gamma_hat_min_idx = i
if gamma_hat_min < gamma:
# 更新当前预测向量 - (3.6)
cur_pred = cur_pred + gamma_hat_min * equiangular
# 将下标移除至已被选择的特征下标集合
active_set.remove(gamma_hat_min_idx)
# 更新特征更新方向集合
sign[gamma_hat_min_idx] = 0
else:
# 更新当前预测向量
cur_pred = X.dot(w)
# 将下标添加至已被选择的特征下标集合
active_set.add(next_j)
# 更新特征更新方向集合
sign[next_j] = next_sign
return w
6. Реализация сторонней библиотеки
scikit-learn6Реализация (метод координатного спуска):
from sklearn.linear_model import Lasso
# 初始化Lasso回归器,默认使用坐标下降法
reg = Lasso(alpha=0.1, fit_intercept=False)
# 拟合线性模型
reg.fit(X, y)
# 权重系数
w = reg.coef_
scikit-learn7Реализация (метод регрессии наименьшего угла):
from sklearn.linear_model import LassoLars
# 初始化Lasso回归器,使用最小角回归法
reg = LassoLars(alpha=0.1, fit_intercept=False)
# 拟合线性模型
reg.fit(X, y)
# 权重系数
w = reg.coef_
Семь, демонстрация анимации
Следующая анимация показывает пример рабочих лет и среднемесячной заработной платы в предыдущем разделе.Весовой коэффициент изменяется только в одном направлении этой координатной оси за раз, и процесс постепенного приближения к оптимальному решению.
Координатный метод спускаСледующая анимация показывает влияние λ на весовой коэффициент каждой независимой переменной, Горизонтальная ось — это штрафной коэффициент λ, вертикальная ось — весовой коэффициент, а каждый цвет представляет весовой коэффициент независимой переменной (данные обучения поступают из наборов данных о диабете sklearn):
Влияние λ на весовой коэффициентВидно, что когда λ постепенно увеличивается (λ движется влево), весовой коэффициент некоторых признаков быстро станет равным нулю.Это свойство показывает, что регрессия Лассо может использоваться для выбора признаков, а размер λ контролируется для выбора ключевые особенности. .
Восемь, интеллект-карта
9. Ссылки
- En. Wikipedia.org/wiki/lasso_…
- En.wikipedia.org/wiki/co или низкая…
- En. Wikipedia.org/wiki/least-…
- Web.Stanford.Amount/~Hastie/pap…
- zhuanlan.zhihu.com/p/46999826
- SCI kit-learn.org/stable/Modu…
- SCI kit-learn.org/stable/Modu…
Нажмите для полной демонстрацииздесь
Примечание. Эта статья стремится быть точной и легкой для понимания, но поскольку автор также новичок и имеет ограниченный уровень, если в тексте есть ошибки или упущения, я призываю читателей критиковать и исправлять их, оставляя сообщение.
Эта статья была впервые опубликована на -карта ИИ, добро пожаловать, чтобы следовать