# Линейные модели, kNN, Naive Bayes и SVM

> Эта глава связывает четыре семейства моделей с их целями, предположениями,
> геометрией и наблюдаемым поведением.

## Общая постановка

Пусть \(\mathbf X\in\mathbb R^{n\times d}\), строка
\(\mathbf x^{(i)}\) — объект. Модель выбирают не по названию, а по индуктивному
предположению: линейная зависимость, локальная гладкость, условная независимость
или разделение классов с большим зазором. Масштабирование обязательно для
регуляризованных линейных моделей, kNN и SVM: иначе единицы измерения определяют
геометрию.

## Линейная регрессия

Модель \(\hat y=\mathbf w^\top\mathbf x+b\) минимизирует MSE:

\[
L(\mathbf w,b)=\frac1{2n}\|\mathbf X\mathbf w+b\mathbf1-\mathbf y\|_2^2.
\]

После добавления столбца единиц обозначим расширенную матрицу
\(\tilde{\mathbf X}\) и параметры \(\boldsymbol\beta\). Тогда

\[
\nabla L=\frac1n\tilde{\mathbf X}^{\top}
(\tilde{\mathbf X}\boldsymbol\beta-\mathbf y).
\]

Условие стационарности даёт нормальные уравнения
\(\tilde{\mathbf X}^{\top}\tilde{\mathbf X}\boldsymbol\beta
=\tilde{\mathbf X}^{\top}\mathbf y\). При полном столбцовом ранге
\(\hat{\boldsymbol\beta}=(\tilde{\mathbf X}^{\top}\tilde{\mathbf X})^{-1}
\tilde{\mathbf X}^{\top}\mathbf y\), но в коде устойчивее QR/SVD, а не явная
обратная матрица.

Ridge добавляет \(\lambda\|\mathbf w\|_2^2/2\), уменьшая дисперсию и проблему
коллинеарности. Lasso добавляет \(\lambda\|\mathbf w\|_1\), создавая нулевые
коэффициенты, но нестабильно выбирает один из коррелирующих признаков.
Линейность относится к параметрам: полиномиальные признаки всё ещё допускают
линейную регрессию.

**Предположения.** Для предсказания нужны репрезентативные данные и примерно
аддитивная зависимость. Независимость ошибок, постоянная дисперсия и нормальность
нужны прежде всего для классических доверительных интервалов, а не для самого
вычисления коэффициентов. Корреляция не превращает коэффициент в причинный эффект.

## Логистическая регрессия

Для \(Y\in\{0,1\}\) логит линейный:

\[
p_\theta(Y=1\mid\mathbf x)=\sigma(z),\quad
z=\mathbf w^\top\mathbf x+b,\quad \sigma(z)=\frac1{1+e^{-z}}.
\]

Отношение шансов удовлетворяет
\(\log[p/(1-p)]=z\): увеличение \(x_j\) на единицу умножает шансы на \(e^{w_j}\)
при фиксированных остальных признаках. Максимизация правдоподобия Бернулли
эквивалентна минимизации log loss:

\[
L=-\frac1n\sum_i[y^{(i)}\log p_i+(1-y^{(i)})\log(1-p_i)].
\]

Поскольку \(d\ell/dz=p-y\),
\(\nabla_{\mathbf w}L=\mathbf X^\top(\mathbf p-\mathbf y)/n\). Уверенная ошибка
получает большой градиент. Граница при пороге \(0.5\) есть
\(\mathbf w^\top\mathbf x+b=0\), но рабочий порог выбирают отдельно.
Мультикласс обобщается softmax-регрессией.

## k ближайших соседей

kNN не подгоняет явную функцию: для запроса ищет множество \(N_k(\mathbf x)\).
Регрессия усредняет ответы, классификация голосует:

\[
\hat p(Y=c\mid\mathbf x)=\frac1k\sum_{i\in N_k(\mathbf x)}
\mathbb1\{y^{(i)}=c\}.
\]

Малое \(k\) даёт низкое смещение и высокую дисперсию; большое — наоборот.
Взвешивание \(1/(r_i+\varepsilon)\) усиливает близких соседей. Основное
предположение — локальная близость признаков означает близость ответа.
В высокой размерности расстояния становятся похожими, объём локальной окрестности
растёт экспоненциально: это проклятие размерности. Обучение почти бесплатно,
предсказание и память дороги.

## Наивный Байес

По формуле Байеса

\[
p(y=c\mid\mathbf x)\propto p(y=c)p(\mathbf x\mid y=c).
\]

Naive Bayes предполагает условную независимость признаков:

\[
p(\mathbf x\mid y=c)=\prod_{j=1}^d p(x_j\mid y=c).
\]

Вычисляют логарифмы:
\(\log p(c\mid\mathbf x)=\mathrm{const}+\log p(c)+\sum_j\log p(x_j\mid c)\).
GaussianNB моделирует числовые признаки нормальными, MultinomialNB — счётчики,
BernoulliNB — бинарные признаки. Сглаживание Лапласа
\(\hat p=(N_{jc}+\alpha)/(N_c+\alpha V)\) не позволяет невиданному слову
обнулить произведение. Независимость почти всегда ложна, но граница решения
часто остаётся хорошей; вероятности при коррелирующих признаках могут быть
чрезмерно уверенными.

## SVM и большой зазор

Для \(y^{(i)}\in\{-1,+1\}\) функциональный отступ
\(m_i=y^{(i)}(\mathbf w^\top\mathbf x^{(i)}+b)\). Soft-margin SVM решает

\[
\min_{\mathbf w,b}\frac12\|\mathbf w\|_2^2+
C\sum_i\max(0,1-m_i).
\]

Первое слагаемое максимизирует геометрический зазор \(2/\|\mathbf w\|_2\),
hinge loss штрафует точки внутри полосы и ошибки. \(C\) — цена нарушения:
большое \(C\) уменьшает train-ошибки, но ослабляет регуляризацию. Только точки с
\(m_i\le1\) — опорные — влияют на решение.

Kernel trick заменяет скалярное произведение на
\(K(\mathbf x,\mathbf z)=\phi(\mathbf x)^\top\phi(\mathbf z)\). Для RBF
\(K=\exp(-\gamma\|\mathbf x-\mathbf z\|^2)\): большая \(\gamma\) создаёт очень
локальную гибкую границу. Ядро должно задавать положительно полуопределённую
Gram-матрицу. Kernel SVM масштабируется плохо по \(n\); линейный SVM эффективнее
для больших разреженных данных. SVM score не является вероятностью; калибровка
требует отдельных данных.

## Разобранный пример

Для логистической модели \(z=-1+0.8x\), при \(x=2\):
\(z=0.6\), \(p=1/(1+e^{-0.6})\approx0.646\). При \(y=1\)
\(\ell=-\log0.646\approx0.437\), производная по \(z\) равна
\(p-y=-0.354\): градиентный шаг увеличит \(z\). Рост \(x\) на единицу умножает
шансы на \(e^{0.8}\approx2.23\), а не увеличивает вероятность на константу.

## Самостоятельный пример sklearn

```python
from sklearn.datasets import make_classification
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_classification(
    n_samples=600, n_features=8, class_sep=1.2, random_state=7
)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, stratify=y, random_state=7
)
for model in [
    LogisticRegression(max_iter=2000),
    SVC(C=1.0, kernel="rbf", gamma="scale"),
]:
    pipe = make_pipeline(StandardScaler(), model)
    pipe.fit(X_train, y_train)
    print(type(model).__name__, pipe.score(X_test, y_test))
```

Замените последний estimator на `KNeighborsClassifier` или `GaussianNB`
(масштабирование для GaussianNB не обязательно) и сравните на одном split.

## Типичные ошибки и ограничения

- Коэффициенты без масштаба и проверки коллинеарности нельзя сравнивать.
- Логистическая регрессия задаёт линейный logit, а не линейную вероятность.
- kNN с ID, шумовыми признаками или необработанными единицами измеряет не то.
- Naive Bayes не подтверждает независимость; его вероятности проверяют отдельно.
- `SVC(probability=True)` выполняет дополнительную калибровку и дороже обучается.
- Выбор модели по train score смешивает способность запоминать и обобщать.

## Краткое резюме

- Линейные модели оптимизируют выпуклый риск и дают сильный baseline.
- kNN переносит локальную структуру, но страдает в высокой размерности.
- Naive Bayes силён при подходящей модели признаков, несмотря на грубое допущение.
- SVM контролирует границу через зазор, \(C\) и ядро.

## Связанные материалы

- Практика: [`../assignments/01_model_selection.md`](../assignments/01_model_selection.md).
- Практика: [`../assignments/03_regression.md`](../assignments/03_regression.md).

- Предыдущая глава: [`01_validation_and_baselines.md`](01_validation_and_baselines.md).
- Следующая глава: [`03_metrics_thresholds_and_calibration.md`](03_metrics_thresholds_and_calibration.md).
- Термины: [`../glossary.md`](../glossary.md).