动机
无监督学习没有唯一通用的“好群组”定义。欧几里得(Euclid)聚类奖励接近同一中心,图聚类重视组内强连接及组间弱连接,非负分解则寻找矩阵的相加构件。这些目标都有用途,但改变几何或表示方式,同一批观测也可能得到不同分组。
小样本带来第二层困难:较灵活的模型可更贴合已观察数据,却未必更能预测。选群组数、表示维数、正则化强度,本身就是学习决策。若反复查看测试样本来作选择,测试样本便成了训练的一部分。因此,优化与可信的模型评估必须一起理解。
本节推导 k-means、谱松弛、非负矩阵分解、岭回归及 lasso 的有限维基础。
定义
定义 3.1.1
(k-means 目标)
给定 与整数 ,选指派 及中心 ,以最小化
通常交替把观测指派给最近中心,再把每个非空群组的中心换成平均值。空群组需要明确处理规则;任意放置的新中心并不是“空集合的平均”。
欧几里得距离依赖量度单位。同一坐标从米改为毫米,平方差会增大一百万倍。标准化坐标会改变优化目标,有时合理,但若要评估预测表现,位置与尺度估计也必须只用训练数据拟合。
定义 3.1.2
(加权图及其拉普拉斯矩阵)
设 为对称、非负、对角为零的 矩阵。令 ,未归一化拉普拉斯(Laplacian)矩阵为 。若两顶点之间有一条每条边权重皆正的路径,便称它们连通。顶点子集 的割权重为 。
用什么图来聚类,本身就是建模选择。距离核、最近邻图及连接阈值可能表达不同邻近关系。下述谱结论要求矩阵对称,因此对称化不可忽略。另外,这里的未归一化形式不同于涉及 的归一化割形式;不可不检查目标就交换两者的特征向量。
定义 3.1.3
(非负矩阵分解)
对非负数据 ,非负矩阵分解(NMF)例如选 、 最小化 。每个数据列于是是 的非负列向量的相加组合。秩参数 、损失与限制都是问题定义的一部分。固定一个因子后,目标对另一因子是凸二次式;但联合优化通常非凸,不能把分别的凸性误当联合凸性。
“相加”有具体含义:非负系数不能抵销另一构件的正贡献。当量度本身具有可加性时,这可令表示较容易检视,却不能证明因子是唯一的物理对象。相关构件可在不同因子之间重新分配,精确拟合也仍有尺度歧义。可解释性是需要研究的问题,不是只加符号限制就得到的定理。
平方损失的无限制梯度为 与 。在受限制驻点,严格正的坐标必须有零梯度;零坐标则可有非负梯度,因为只可向增加方向移动。这已说明为何不能先解无限制正规方程,再把负值截成零:截断改变了耦合最优点,必须重新检查原来的受限制问题。
定义 3.1.4
(岭回归与 lasso 目标)
对设计矩阵 与响应 ,岭回归目标为 ,lasso 目标为 ,其中 、。水平为 的软阈值映射把实数 送到 。
定理/命题
定理 3.1.5
(质心最优性与交替下降)
对非空固定群组 ,算术平均 唯一最小化 。因此,最近中心指派后接平均更新,不会增加 k-means 目标,前提是空群组也以不增加目标的方式处理。下降不代表已找到全局最优聚类。
定理 3.1.6
(拉普拉斯量度边上的变化)
对每个 ,
其零空间恰由在每个连通分量内为常数的向量组成。特别地,若图连通且至少有两顶点,在 、 限制下, 的最小化点可以取为 的第二小特征值所对应的特征向量。
概念视角组合
同一能量也是割的计数
对顶点子集 ,令 为其指示向量,在 内取一,其余取零。在 中,只有恰好一端属于 的顶点对才有贡献,这时 。每个无序顶点对在双重和中出现两次,所以 ,即割权重。以三顶点单位权重路径图为例, 时 ,恰是离开 的一条边; 时为 ,即离开 的两条边。因此,对实向量定义的二次型,把“切断了多少条边”的组合计数推广成沿边变化的连续度量。
定理 3.1.7
(岭回归唯一性及正交设计下的 lasso 收缩)
对任何实 及 , 有唯一最小化点 。若 ,则 的最小化点各坐标为
这里每个系数都受惩罚;若截距不受惩罚,必须另列设定。
证明思路或证明
证明
(质心恒等式为何保证下降)
写 ,展开平方并利用 ,得
第二项证明均值唯一最优。固定中心时,各观测的最近中心指派逐项最小化误差;固定指派时,上式则逐组最小化误差。串起两个不等式便证明下降。目标下界为零,因此其数值序列收敛;但单凭这点,不能证明所有平手处理方式都会终止,更不能证明找到最佳分割。
证明
(图能量与谱松弛)
展开图能量的平方。由对称性,两个平方项合成 ,交叉项为 ,故等于 。非负加权平方和为零,要求每条正权边两端数值相等,从而在整个连通分量上相等;反过来,分量内常数显然给零能量。
对连通图取正交特征基底,第一向量为 ,特征值为 。每个可行向量可写成 ,其中 ,故 ,第二特征空间内可达等号。离散指示向量有更多限制;放宽成实向量后,最终仍需取整或阈值分组。
证明透视
从割变成特征向量时放宽了什么
图能量等于割权重,只对 – 指示向量 成立。实特征向量未必是指示向量,对它取阈值会改变向量及限制。谱定理精确解决的是松弛后的二次问题,不会自动保证任意阈值都产生全局最优的平衡图分割。
证明
(二次稳定化与稀疏阈值)
岭回归梯度为 。对任意非零 ,有 ,所以即使 秩不足,驻点仍是唯一最小值。
若 ,lasso 目标与 只差常数。正坐标的导数方程给 ,仅在 可行;负坐标给 ,仅在 可行。零处的次梯度条件是 。合起来就是软阈值公式。若列向量不正交,各坐标互相耦合,这个一次逐坐标公式一般不成立。
反例模式
列向量不正交时软阈值失效
设想一个断言:对任何设计,lasso 的最小化点都是 ,其中 。取只有一个观测、两个完全相同特征的例子:、、。此时 ,公式给出 ,目标值为
但 的目标值是 ,更小,所以公式的输出不是最小化点。这里 。事实上,令 ,目标至少为 ,当且仅当两个坐标不异号时取等号;这个下界在 最小,值为 。因此最小化点是所有满足 、 的 ,并不唯一。逐坐标软阈值只在 时精确成立;一般设计的各坐标相互牵动,lasso 必须当作耦合的凸问题来求解。
例题详解
岭回归也可按奇异方向理解。若设计的非零奇异值为 ,右奇异向量上的系数等于响应的相应左奇异坐标乘以 ;未正则化求逆则乘以 。极小奇异值会把噪声大幅放大,岭回归能抑制这种放大,但同时也收缩真实信号。选惩罚强度是在取舍偏差与方差,并非对所有真实系数都能免费改善。另外,特征尺度若改变,其相对二次惩罚也会改变,除非已明确处理尺度。
例题 3.1.8
(一次下降的 k-means 迭代)
观测为 ,起始中心为零与十。最近中心指派给群组 与 ,目标为 。均值更新给一与十,目标降至 。下次指派不变,故这是稳定的交替解。一般数据上若要证明全局最优,仍须另外论证。
例题 3.1.9
(三顶点路径图)
一与二、二与三之间各有一条单位权重边,故
向量 、、 分别对应特征值零、一、三。单位且均值为零的 能量为一,与两条边的平方差总和相同。正负号提供顶点排序,但中间的零仍需分组惯例。把特征向量反号,不会改变原来的图。
例题 3.1.10
(相加分解的尺度并不唯一)
矩阵 有精确非负秩一分解 、。对任何 , 与 给出相同乘积及零误差。因此非负性本身不能识别尺度。把列标准化可以消除此歧义,但一般不能证明高秩分解唯一。另外,非负因子乘积不可能精确重构含负元素的矩阵。
例题 3.1.11
(岭回归收缩,lasso 可以移除坐标)
取 、、。岭回归把每个系数除以二,得 ;lasso 以软阈值得 。零来自绝对值在原点的尖角,并非数值舍入。平方损失或惩罚的系数若改变,阈值也会改变,因此公式必须对照实际写下的目标。
模型选择利用数据挑选 、因子秩或 等设定。验证集在独立训练拟合后估计表现;交叉验证让不同折轮流担任验证集。所有依赖数据的步骤,包括尺度标准化、特征筛选及 PCA,都要在每个训练折内拟合,再应用到该折验证数据。选好设定后,可在全部开发数据上重新拟合;若要独立评估,最后仍需要未曾用来选择的测试样本。
对有 个自由参数的似然模型,常见分数为 、,通常选较小者。两者有不同渐近动机与正则条件,并非通用的有限样本风险界。例如无限制混合有似然奇异与识别困难,仅仅数参数,并不能证明正则模型的 BIC 近似适用。小样本时更要留意这些条件;验证分数本身也有不确定性,少许数值优势不代表持久的总体优势。
常见错误
反例模式
稳定 k-means 仍可错过较好分割
数据为 ,两中心为二与七。指派是 与 ,每个中心已是群组均值,交替步骤不会改变,目标为 。但改用群组 与 ,均值零与六,目标为 。所以稳定与下降都不能当作全局最优证书。
常见错误
(小样本不能支持无限次搜索模型)
尝试大量超参数后,报告最佳测试结果,会挑中有利的测试噪声。即使没有对测试集计算梯度,这样重用它仍改变了其统计角色。交叉验证前先用全部观测估计尺度,也把信息跨越了分割。完整选择程序应留在开发数据内,并报告评估的不确定性,不要把每个小差异都当成实质进步。
总结
质心更新解固定指派的 k-means 问题,拉普拉斯特征向量解松弛图能量问题,NMF 要求非负相加结构。岭回归稳定所有系数方向,lasso 则可把坐标设成精确零。每种方法都有指定目标,而选择目标及复杂度也是学习的一部分,可靠评估必须把这些选择算进去。
练习
快速检查
(群组含零、二、七。求最佳中心及最小平方误差;若用中心四,会增加多少误差?)
使用质心恒等式,不必重复展开二次式。
解答 · 答案
均值为三,最小平方误差为 。用中心四,额外增加 ,总误差为二十九。乘数是群组大小,不是数据维数。
快速检查
(图有两个分量:顶点一、二之间有单位权重边,第三顶点孤立。描述拉普拉斯零空间及其维数。)
孤立顶点本身也是连通分量。
解答 · 答案
拉普拉斯为 ,零空间是 ,维数二,可用 、 作基底。若只允许一个全图常数,便会漏掉不连通分量的自由度。
快速检查
(X 只有一行 (1,1),响应为二,岭参数为一。求岭系数,并比较未正则化最小二乘的唯一性。)
沿用定理中平方损失前有二分之一的约定。
解答 · 答案
岭方程为 ,故 。没有惩罚时,所有满足 的向量皆令平方误差最小。岭回归选出唯一但带偏的拟合,系数和为 ;即使原来可插值,加入惩罚后也不会自动保留精确插值。
快速检查
(正交设计下 ,lasso 参数为 0.5。求系数,并解释恰在阈值上的坐标。)
使用零处的次梯度条件。
解答 · 答案
软阈值结果为 。当 ,零满足次梯度条件,且二次项严格凸,故仍是唯一标量最小化点。在等号处系数变成零,并不会产生一整段最小化点。