Формулы ML-алгоритмов¶

~4 минуты чтения

Справочник формул для 15 ключевых ML-алгоритмов: от линейной регрессии до Isolation Forest. Покрывает loss-функции, градиенты, kernel tricks и метрики качества. На собеседованиях по ML чаще всего просят вывести градиент logistic regression (встречается в 60%+ ML-интервью), объяснить разницу Gini vs Entropy для деревьев, и записать формулу attention из Transformer.

Linear Regression¶

Модель¶

\[\hat{y} = w_0 + w_1 x_1 + w_2 x_2 + ... + w_n x_n = \mathbf{w}^T \mathbf{x}\]

Loss (MSE)¶

\[L = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2\]

Аналитическое решение (OLS)¶

\[\mathbf{w} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}\]

Ridge Regression (L2)¶

\[L = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 + \lambda \sum_{j=1}^{p} w_j^2\]

\[\mathbf{w} = (\mathbf{X}^T \mathbf{X} + \lambda \mathbf{I})^{-1} \mathbf{X}^T \mathbf{y}\]

Lasso Regression (L1)¶

\[L = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 + \lambda \sum_{j=1}^{p} |w_j|\]

Elastic Net¶

\[L = \frac{1}{n} \sum_{i=1}^{n} (y_i - \hat{y}_i)^2 + \lambda_1 \sum_{j=1}^{p} |w_j| + \lambda_2 \sum_{j=1}^{p} w_j^2\]

Logistic Regression¶

Модель¶

\[P(y=1|\mathbf{x}) = \sigma(\mathbf{w}^T \mathbf{x}) = \frac{1}{1 + e^{-\mathbf{w}^T \mathbf{x}}}\]

Sigmoid функция¶

\[\sigma(z) = \frac{1}{1 + e^{-z}}\]

\[\sigma'(z) = \sigma(z)(1 - \sigma(z))\]

Binary Cross-Entropy Loss¶

\[L = -\frac{1}{n} \sum_{i=1}^{n} [y_i \log(\hat{y}_i) + (1-y_i) \log(1-\hat{y}_i)]\]

Градиент¶

\[\frac{\partial L}{\partial w_j} = \frac{1}{n} \sum_{i=1}^{n} (\hat{y}_i - y_i) x_{ij}\]

Softmax Regression (Multiclass)¶

Softmax функция¶

\[P(y=k|\mathbf{x}) = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}}\]

где \(z_k = \mathbf{w}_k^T \mathbf{x}\)

Cross-Entropy Loss¶

\[L = -\frac{1}{n} \sum_{i=1}^{n} \sum_{k=1}^{K} y_{ik} \log(\hat{y}_{ik})\]

Decision Tree¶

Gini Impurity¶

\[Gini(p) = \sum_{k=1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K} p_k^2\]

Entropy¶

\[H(p) = -\sum_{k=1}^{K} p_k \log_2(p_k)\]

Information Gain¶

\[IG = H(parent) - \sum_{i} \frac{n_i}{n} H(child_i)\]

MSE для регрессии¶

\[MSE = \frac{1}{n} \sum_{i=1}^{n} (y_i - \bar{y})^2\]

Random Forest¶

Предсказание (классификация)¶

\[\hat{y} = \text{mode}(h_1(\mathbf{x}), h_2(\mathbf{x}), ..., h_T(\mathbf{x}))\]

Предсказание (регрессия)¶

\[\hat{y} = \frac{1}{T} \sum_{t=1}^{T} h_t(\mathbf{x})\]

Out-of-Bag Error¶

\[OOB_{error} = \frac{1}{n} \sum_{i=1}^{n} L(y_i, \hat{y}_i^{OOB})\]

Gradient Boosting¶

Общая формула¶

\[F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \gamma_m h_m(\mathbf{x})\]

Pseudo-residuals¶

\[r_{im} = -\left[\frac{\partial L(y_i, F(\mathbf{x}_i))}{\partial F(\mathbf{x}_i)}\right]_{F=F_{m-1}}\]

Для MSE loss¶

\[r_{im} = y_i - F_{m-1}(\mathbf{x}_i)\]

XGBoost objective¶

\[Obj = \sum_{i=1}^{n} L(y_i, \hat{y}_i) + \sum_{k=1}^{K} \Omega(f_k)\]

\[\Omega(f) = \gamma T + \frac{1}{2}\lambda \|w\|^2\]

SVM¶

Primal формулировка¶

\[\min_{w,b} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^{n} \xi_i\]

\[\text{subject to: } y_i(w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0\]

Dual формулировка¶

\[\max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j K(x_i, x_j)\]

\[\text{subject to: } 0 \leq \alpha_i \leq C, \quad \sum_{i} \alpha_i y_i = 0\]

Kernel functions¶

Linear: \(K(x, x') = x^T x'\)
Polynomial: \(K(x, x') = (\gamma x^T x' + r)^d\)
RBF: \(K(x, x') = \exp(-\gamma \|x - x'\|^2)\)

Hinge Loss¶

\[L = \max(0, 1 - y \cdot f(x))\]

K-Nearest Neighbors¶

Расстояния¶

Euclidean: \(d(x, x') = \sqrt{\sum_{i} (x_i - x'_i)^2}\)
Manhattan: \(d(x, x') = \sum_{i} |x_i - x'_i|\)
Minkowski: \(d(x, x') = (\sum_{i} |x_i - x'_i|^p)^{1/p}\)
Cosine: \(d(x, x') = 1 - \frac{x \cdot x'}{\|x\| \cdot \|x'\|}\)

Предсказание¶

\[\hat{y} = \text{mode}(\{y_i : x_i \in N_k(x)\})\]

Weighted KNN¶

\[\hat{y} = \frac{\sum_{i \in N_k} w_i y_i}{\sum_{i \in N_k} w_i}, \quad w_i = \frac{1}{d(x, x_i)}\]

K-Means¶

Objective¶

\[J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2\]

Centroid update¶

\[\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i\]

Assignment¶

\[C_k = \{x_i : \|x_i - \mu_k\| \leq \|x_i - \mu_j\|, \forall j\}\]

PCA¶

Covariance matrix¶

\[\Sigma = \frac{1}{n-1} \mathbf{X}^T \mathbf{X}\]

Eigendecomposition¶

\[\Sigma = \mathbf{V} \Lambda \mathbf{V}^T\]

Projection¶

\[\mathbf{Z} = \mathbf{X} \mathbf{V}_k\]

где \(\mathbf{V}_k\) — первые k собственных векторов

Explained variance ratio¶

\[\text{explained\_variance}_k = \frac{\lambda_k}{\sum_{i} \lambda_i}\]

Naive Bayes¶

Bayes' Theorem¶

\[P(y|\mathbf{x}) = \frac{P(\mathbf{x}|y) P(y)}{P(\mathbf{x})}\]

Naive assumption¶

\[P(\mathbf{x}|y) = \prod_{i=1}^{n} P(x_i|y)\]

Classifier¶

\[\hat{y} = \arg\max_y P(y) \prod_{i=1}^{n} P(x_i|y)\]

Gaussian Naive Bayes¶

\[P(x_i|y) = \frac{1}{\sqrt{2\pi\sigma_y^2}} \exp\left(-\frac{(x_i - \mu_y)^2}{2\sigma_y^2}\right)\]

AUC-ROC¶

True Positive Rate (Recall)¶

\[TPR = \frac{TP}{TP + FN}\]

False Positive Rate¶

\[FPR = \frac{FP}{FP + TN}\]

AUC интерпретация¶

\[AUC = P(\text{score}_{positive} > \text{score}_{negative})\]

Information Theory¶

Entropy¶

\[H(X) = -\sum_{x} p(x) \log p(x)\]

Cross-Entropy¶

\[H(p, q) = -\sum_{x} p(x) \log q(x)\]

KL Divergence¶

\[D_{KL}(p\|q) = \sum_{x} p(x) \log \frac{p(x)}{q(x)} = H(p, q) - H(p)\]

Mutual Information¶

\[I(X; Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X, Y)\]

DBSCAN¶

Core Point¶

Точка \(p\) — core point если \(|N_\epsilon(p)| \geq \text{MinPts}\)

где \(N_\epsilon(p) = \{q \in D : d(p, q) \leq \epsilon\}\)

Density-Reachability¶

\(p\) density-reachable from \(q\) если существует цепочка \(p_1, ..., p_n\) где \(p_1 = q\), \(p_n = p\), и каждый \(p_{i+1} \in N_\epsilon(p_i)\) при \(p_i\) — core point

Gaussian Mixture Model (GMM)¶

Likelihood¶

\[p(\mathbf{x}) = \sum_{k=1}^{K} \pi_k \mathcal{N}(\mathbf{x}|\mu_k, \Sigma_k)\]

E-step (responsibilities)¶

\[\gamma_{nk} = \frac{\pi_k \mathcal{N}(\mathbf{x}_n|\mu_k, \Sigma_k)}{\sum_{j=1}^{K} \pi_j \mathcal{N}(\mathbf{x}_n|\mu_j, \Sigma_j)}\]

M-step¶

\[\mu_k = \frac{\sum_n \gamma_{nk} \mathbf{x}_n}{\sum_n \gamma_{nk}}, \quad \pi_k = \frac{\sum_n \gamma_{nk}}{N}\]

t-SNE¶

Joint Probability (high-dim)¶

\[p_{j|i} = \frac{\exp(-\|x_i - x_j\|^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-\|x_i - x_k\|^2 / 2\sigma_i^2)}\]

Joint Probability (low-dim, Student-t)¶

\[q_{ij} = \frac{(1 + \|y_i - y_j\|^2)^{-1}}{\sum_{k \neq l} (1 + \|y_k - y_l\|^2)^{-1}}\]

Objective (KL divergence)¶

\[C = KL(P\|Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}\]

UMAP¶

Fuzzy Set Membership¶

\[\mu(x_i, x_j) = \exp\left(-\frac{d(x_i, x_j) - \rho_i}{\sigma_i}\right)\]

Cross-Entropy Loss¶

\[C = \sum_{e \in E} \left[ \mu(e) \log\frac{\mu(e)}{\nu(e)} + (1-\mu(e)) \log\frac{1-\mu(e)}{1-\nu(e)} \right]\]

где \(\mu\) — high-dim graph weights, \(\nu\) — low-dim graph weights

Isolation Forest¶

Anomaly Score¶

\[s(x, n) = 2^{-\frac{E[h(x)]}{c(n)}}\]

где \(h(x)\) — path length, \(c(n) = 2H(n-1) - 2(n-1)/n\) — normalization

Interpretation¶

\(s \approx 1\): anomaly
\(s \approx 0.5\): normal
\(s < 0.5\): dense region

Metrics: Precision, Recall, F1¶

Precision¶

\[P = \frac{TP}{TP + FP}\]

Recall¶

\[R = \frac{TP}{TP + FN}\]

F1-Score¶

\[F_1 = 2 \cdot \frac{P \cdot R}{P + R} = \frac{2TP}{2TP + FP + FN}\]

F-beta Score¶

\[F_\beta = (1 + \beta^2) \cdot \frac{P \cdot R}{\beta^2 \cdot P + R}\]

Average Precision (AP)¶

\[AP = \sum_n (R_n - R_{n-1}) P_n\]

Silhouette Score (Clustering)¶

Per-sample¶

\[s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}\]

где \(a(i)\) = mean intra-cluster distance, \(b(i)\) = mean nearest-cluster distance

Interpretation¶

\(s \approx 1\): well-clustered
\(s \approx 0\): on boundary
\(s < 0\): likely misclassified

Типичные заблуждения¶

Заблуждение: OLS всегда даёт оптимальное решение для линейной регрессии

Аналитическое решение \(\mathbf{w} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}\) требует обратимости \(\mathbf{X}^T \mathbf{X}\). При мультиколлинеарности (rank-deficient matrix) решение нестабильно или невозможно. Ridge regression добавляет \(\lambda \mathbf{I}\) и гарантирует обратимость. Вычислительная сложность OLS -- \(O(n \cdot p^2 + p^3)\), для больших \(p\) предпочтителен SGD.

Заблуждение: Gini и Entropy дают одинаковые деревья

На практике разница между Gini impurity и Entropy менее 2% случаев. Но Entropy вычисляет логарифм (дороже), а Gini -- полином. scikit-learn использует Gini по умолчанию. Реальное отличие: Entropy сильнее "штрафует" неоднородные разбиения, что иногда даёт более сбалансированные деревья.

Заблуждение: K-Means всегда находит глобальный оптимум

K-Means минимизирует intra-cluster variance, но алгоритм гарантирует только локальный минимум. Результат зависит от начальной инициализации центроидов. K-Means++ (scikit-learn default) значительно улучшает инициализацию, но глобальный оптимум не гарантирован. Рекомендация: n_init=10 (запуск 10 раз, выбор лучшего).

Вопросы на собеседовании¶

"Выведите градиент logistic regression"

Слабый ответ: записывает формулу без вывода, путает знаки

Сильный ответ: "BCE loss = \(-\frac{1}{n}\sum[y\log\hat{y} + (1-y)\log(1-\hat{y})]\), где \(\hat{y} = \sigma(w^Tx)\). По chain rule: \(\frac{\partial L}{\partial w_j} = \frac{1}{n}\sum(\hat{y}_i - y_i)x_{ij}\). Это удобно -- тот же вид что и для MSE в линейной регрессии, благодаря свойству \(\sigma'(z) = \sigma(z)(1-\sigma(z))\)."

"В чём разница между L1 и L2 регуляризацией?"

Слабый ответ: "L1 -- абсолютные значения, L2 -- квадраты"

Сильный ответ: "L1 (Lasso) даёт sparse решения -- обнуляет неважные веса (feature selection). L2 (Ridge) уменьшает все веса, но не обнуляет. Геометрически: L1 -- ромб (углы на осях), L2 -- круг. Elastic Net комбинирует оба. Ridge гарантирует обратимость \(X^TX + \lambda I\), Lasso -- нет аналитического решения."

"Как выбрать K для K-Means?"

Слабый ответ: "Elbow method"

Сильный ответ: "Elbow method (inertia vs K) -- субъективен. Silhouette score -- объективнее (\(s \in [-1, 1]\), чем ближе к 1 -- тем лучше). Gap statistic сравнивает с uniform distribution. На практике: домен-знание важнее метрик. Для K-Means альтернативы: DBSCAN (не нужен K), GMM (мягкая кластеризация)."