An Online Learning Approach to Interpolation and Extrapolation in Domain Generalization

Elan Rosenfeld, Pradeep Ravikumar, Andrej Risteski – CMU
Elan Rosenfeld 的代表作与对抗样本、分布外样本均相关:《Certified adversarial robustness via randomized smoothing》,《The Risks of Invariant Risk Minimization》。

解决问题及难点

本文从在线学习 (Online learning) 的角度考虑了域泛化 (Domain generalization) 问题:将域泛化问题分为内拓 (Interpolation) 与外延 (Extrapolation) 两个方向,并分别分析了在线学习对这两个任务的遗憾界 (Regret)。本文试图替换域泛化问题常用的单回合极大极小游戏 (Single-round min-max game) 的框架,更深入地分析此问题的统计和算法性质。

核心贡献

  • 将域泛化问题刻化为在线学习问题,定义为一个对抗出现的测试分布和一个最小化积累遗憾 (Cumulative regret) 的玩家。
  • 理论上证明了在计算层面,外延比内拓指数级别地复杂;在统计层面,两者的遗憾界并没有显著的差别(指\(\Theta(\sqrt{T})\) 与\(\Theta(\log T)\))。
  • ERM 对于内拓与外延都能够到达极大极小最优。

解决方案及创新点

内拓与外延

内拓 Interpolation

内拓等价于优化现有环境分布集合\(\mathcal{E}\) 的凸组合\(Conv(\mathcal E)\),即内拓的测试环境在已有环境组成的凸包内部或边界上:

\[\min _{f \in \mathcal{F}} \max _{e \in \operatorname{Conv}(\mathcal{E})} \mathbb{E}_e[\ell(f)]=\min _{f \in \mathcal{F}} \max _{e \in \mathcal{E}} \mathbb{E}_e[\ell(f)]
\]

因此,内拓是一个离散的单回合游戏。

外延 Extrapolation

外拓将测试环境分布定义为已有环境线性组合\(Extr(\mathcal E)\),系数只和必须为\(1\) 却允许某些组合系数是较小的负数 (系数满足\(\lambda>-\alpha\)),即外延的环境在已有环境组成的凸包附近:

\[\begin{aligned}
&\min _{f \in \mathcal{F}} \max _{e \in \operatorname{Extr}_\alpha(\mathcal{E})} \mathbb{E}_e[\ell(f)]= \\
&\min _{f \in \mathcal{F}} \max _{e \in \mathcal{E}}\left[(1+E \alpha) \mathbb{E}_e[\ell(f)]-\alpha \sum_{e^{\prime} \in \mathcal{E}} \mathbb{E}_{e^{\prime}}[\ell(f)]\right]
\end{aligned}
\]

本文发现这个损失等价于平均的损失加上最坏情况下的损失,因此,外延变为一个离散的单回合游戏。

Extrapolation

在线学习

每回合玩家选择一个参数\(\hat{\beta}\in B\),对手选择一组环境的系数\(\lambda_t\in \Delta\),定义损失函数为\(f_t(\beta):=\mathbb{E}_{(x, y) \sim p^{\lambda_t}}[\ell(\beta,(x, y))]=\sum_{e \in \mathcal{E}} \lambda_{t, e} \mathbb{E}_{(x, y) \sim p^e}[\ell(\beta,(x, y))]\)。

定义 T 轮之后的遗憾总和为:

\[\begin{aligned}
V_T:=& \min _{\hat{\beta}_1 \in B} \max _{\lambda_1 \in \Delta_E} \cdots \\
& \min _{\hat{\beta}_T \in B \lambda_T \in \Delta_E}\left(\sum_{t=1}^T f_t\left(\hat{\beta}_t\right)-\min _{\beta \in B} \sum_{t=1}^T f_t(\beta)\right)
\end{aligned}
\]

在理想的强凸条件下,\(V_t=\sum_{s=1}^t \frac{G_s^2}{2 s \sigma_{\min }}\),即遗憾界为\(\Theta(\log t)\)。其中,\(G_s\) 是\(f_s\) 的 Lipshitz 常数,\(\sigma_{min}\) 是\(f\) 的最小曲率。

本文的定理 1 证明了遗憾界的下界也是\(\Theta(\log t)\) 的,并可以通过 FTL 算法得到。这证明了在已知环境的条件下,使用 ERM 算法能够为内拓得到可证明的 Min-max 最优。

本文的定理 2 证明了在外拓的情形下没有算法能够达到次线性的遗憾界。因此,需要削弱对抗的对手使其选择整个损失函数序列。在这个情形下,定理 3 证明了达到次线性的遗憾界依旧是 NP-Hard。
从统计学的角度来看,使用 FTPL 算法(即基于扰动的 ERM)能够得到\(\Omega(\sqrt{T})\) 的下届,同时,定理 4 证明了对于这个问题可得到的下界就是\(\Omega(\sqrt{T})\) 的。因此,ERM 配合合适的正则化是可以得到好的域外泛化性的。

局限性和改进空间

感觉也没怎么看懂这个文章,就是证明了其实 ERM 算法能够得到很好的域外泛化性能。本文也给出了一些未来方向:

  • 利用在线学习的框架研究分布外泛化问题
  • 更有效更针对的定义内拓与外延

Gradient of Entropy Minimization Loss

\(\newcommand{\x}{\boldsymbol{x}} \newcommand{\z}{\boldsymbol{z}} \newcommand{\w}{\boldsymbol{w}} \newcommand{\bmu}{\boldsymbol{\mu}} \newcommand{\XX}{\mathcal{X}} \newcommand{\YY}{\mathcal{Y}} \newcommand{\bR}{\mathbb{R}} \newcommand{\to}{\rightarrow}\)

给定模型 \(f:\XX \to \bR^{K}\),其中 \(K\) 为类别的数量。\(f(\x)=[v_1;v_2;\ldots;v_K]\) 表示模型对于样本 \(\x\) 的输出 Logit 值,则模型对样本\(\x\) 的输出概率定义为:

\[\begin{equation}
p_i=\frac{\exp{(v_i) }}{\sum_{k=1}^K \exp(v_k)}
\label{eq:logits}
\end{equation}
\]

基于模型的输出概率,我们可以模型输出概率的熵与熵最小化损失:

\[\begin{equation}
\ell(\x) = -\sum_{k=1}^K p_k \ln p_k
\label{eq:em_loss}
\end{equation}
\]

为了能够进一步分析,熵最小化损失对于模型机理的影响,我们可以推导出损失对 Logit 值的梯度:

\[\begin{equation}
\begin{aligned}
\frac{\partial \ell(\x)}{\partial v_i}
&=\sum_{k=1}^K \frac{\partial \ell(\x)}{\partial p_k} \frac{\partial p_k}{\partial v_i}\\
&= \sum_{k=1}^K (-\ln p_k – 1) (\mathbb{I}[i=k] \cdot p_i – p_i p_k)\\
&= – p_i (\ln p_i + 1 – \sum_{i=1}^K p_k \ln p_k – \sum_{k=1}^K p_k) \\
&= p_i (\sum_{i=1}^K p_k \ln p_k – \ln p_i) \\
\end{aligned}
\label{eq:grad_of_em}
\end{equation}
\]

海信 A5 Pro CC 使用体验

那一天,我偶然进入华为体验店,发现了一款神奇的产品:一个跑着安卓系统的墨水屏平板。我觉得这个东西好啊,刷不了视频、玩不了游戏,不正适合我这样自控力不足的人,减少手机的使用频率,去追求一下内心的平静。

于是,我隔天就下单了一部 6G 内存、128G 存储、虎贲 T610 处理器的 2020 年产墨水屏手机(在 2022 年中旬的时候)。

续航

4000 毫安时大电池配合墨水屏,这部手机是续航无敌的样子,但实际上只能说不错,远达不到我的预期。我记录了某天手机电量的变化。为轻度使用 A5 Pro CC 做一个参考。如下表所示,我分别记录了手机的电量、应用使用情况、屏幕使用时间以及时间段内大致做的事情:

08:30 10:30 12:30 15:00 17:00 19:00 21:00 23:00
电量 photo_2022-09-20_13-47-20 photo_2022-09-20_13-47-23 photo_2022-09-20_13-47-25 photo_2022-09-20_13-47-31 photo_2022-09-20_13-47-36 photo_2022-09-20_13-47-39 photo_2022-09-20_13-47-43 photo_2022-09-20_13-47-47
使用情况 photo_2022-09-20_13-53-12 photo_2022-09-20_13-53-17 photo_2022-09-20_13-53-21 photo_2022-09-20_13-53-24 photo_2022-09-20_13-53-27 photo_2022-09-20_13-53-30 photo_2022-09-20_13-53-32 photo_2022-09-20_13-53-34
屏幕时间 0 mins 46 mins 63 mins 41 mins 8 mins 19 mins 32 mins 56 mins
备注 充满电 刷微博、京东 聊天、打车、海底捞点餐 聊天、网上冲浪 午睡 守望先锋 聊天、打电话、散步 刷微博、刷知乎、健身环

首先,我觉得应用使用情况并不准确,我明显能够感觉到使用 APP 的情况和手机给我的结果并不匹配,因此具体应用的使用情况仅供参考。不过,屏幕使用时间和待机时间这两项从数值和我个人感受来观察是准确的,有参考价值。

在全天使用手机的过程中,我始终启用手机的自动背光模式。除个别需要看清内容的应用外,屏幕刷新模式均设置为均衡。后台始终运行微信、飞书、Tim、Telegram 四个软件,并使用 Zepp Life 保持和小米手环的连接用于消息提醒。

整体来说,海信 A5 Pro CC 使用一整天是绰绰有余的,在使用了整整 14.5 个小时后,它还依旧能够剩下 18% 的电量。不过,这个续航表现远远不能满足我对与墨水屏的预期,毕竟 4000mAH 大电池配备极省电的墨水屏幕,这个梦幻组合要求它连续运行个两天不过分吧。

因此,对于海信 A5 Pro CC 的续航,我只能说:OK 够用但没能给到我惊喜。

性能

2020 年产的千元机,钱还都花在了墨水屏幕上,你说这性能不就图一乐。不过,我也用针对非旗舰手机的安兔兔 Lite 跑了一次分,让大家知道他的性能是真的不行。

跑分A 跑分B

最终得分 20W 分,仅超过 1% 的用户。CPU 和 GPU 都只能打败了 1% 的用户,不过手机的发热和功耗到还不错,10 分钟的性能测试,手机电量消耗为 3%,温度仅上升 5 度来到 31 度。这倒也不失为老旧中端芯片的优势,耗电与发热都可控制。

墨水屏

咱们先说屏幕的优势,在户外强光下对比背光全开的 iPhone 11,墨水屏由于显示方式的优越性,显示效果尤为突出,完全不会有 LCD 屏亮度不够的感觉,真的就像是在看一张彩色的纸。

颜色显示就不那么理想了。即使在强光的最优显示条件下,健康码中的绿色也比较暗淡,可以说绿是绿的,但习惯了普通屏幕的人猛一看还是回觉得它是灰色的。我也因为健康码被拦下来过一两次,解释一下 “我的屏幕颜色比较淡,您仔细看一下,这是绿码” 并主动指出健康码中绿码的字样后都直接通行了。

健康码

A5 Pro CC 颜色主打彩漫,因此,我选择了两种风格不同的漫画,对比了普通屏幕与墨水屏的显示区别。首先是风格卡通的漫画,缺少了艳丽的颜色支撑,我觉得视觉效果变差了不少:

第二种漫画在线条与颜色上都有很强的表现力,因此,视觉效果好像相差不大。巧合的是,漫画里刚好有一页是纯黑白的内容,为大家提供一个看黑白漫画的参考:

图片与文字显示,在内容颜色丰富的时候,效果还是不错的。例如:左侧两张图片,虽然比不上正常屏幕的清晰度与效果,至少内容还是能完全看清的。但是如右侧两张图片,对比度不足时,图片里面究竟是什么内容真的很难辨认。

图片显示

手机日常体验

其实,购买这部手机的同学最关心的肯定是日常使用体验怎么样。什么颜色有点淡、性能跑分很低,我都不 care,我也不玩游戏也不看视频,我就用它扫个码、打个电话、回个消息。接下来,我就简单从我最关心的几个方面总结一下它的使用体验。

输入法

大家最关注的问题肯定是输入法是否流畅,毕竟对墨水屏幕熟悉的同学一定体验过被 Kindle 输入法支配的恐惧。这边我简单录制了一段输入文字的视频给大家参考。我的结论是,输入体验相比 Kindle 简直是质的飞跃,完全能够满足正常聊天的输入需求,但是输入速度的仍然不高,如果你在和人线上吵架的话,那么使用 A5 Pro CC 无疑会使你落于下风。

手机自带的输入法优势在于专门针对墨水屏设计,界面对比度高、按键大,但是缺点在于输入没有任何震动反馈,快速输入的时候无法感知某个字幕是否被按下。这个问题可以通过下载第三方输入法解决,但是需要换对比度高的输入法皮肤才方便使用。

应用打开速度

应用打开速度是 A5 Pro CC 的又一项劣势,特别是某些优化的不太好的软件,打开速度惨不忍睹,这边我列举了除了常驻后台的聊天软件外,我最常用的四个软件:

而不幸的是,这个打开时间最长的软件,正是我每天去实验室、往返吃饭、回宿舍都要打开的常用软件。

扫码

手机的扫码功能是比较正常的,我在最极端的夜间环境中分别测试了某罗与某桔单车的扫码速度,其实都挺快的。这里有一个小技巧,就是为了方便观察扫码情况而调整角度,最好把手机的刷新模式设置为清晰。

别人扫墨水屏的时候,一定要记得把手机的背光打开,以提升别人扫描成功的概率。

刷手机/视频

只要你想玩手机,墨水屏也无法阻止你。我用 A5 Pro CC 刷微博的最大感想就是,彩色墨水屏真香,虽然颜色淡一点,但和普通手机刷微博的体验是一致的。而用 B 站就看视频就更有意思了,自从我使用墨水屏刷 B 站,我就发现我莫名巧妙地爱上了一个叫做 “槽逻辑” 的 UP 主,用墨水屏看他的视频反而更有舒适了。至于,用墨水屏刷知乎,这波是又能学习新知识,又能保护眼睛,我终于可以心安理得地躺在床上刷他个一下午了。

总结

总结来说,墨水屏确实使我使用手机的频率下降了,不是因为它不方便刷视频、刷微博,而是因为它的流畅度常常让我从根本上就不愿意拿起它。相应的,我的生活还是有所改善,我逐渐学会了只把手机当成一个接收消息的工具,而在电脑上去高效地查看消息、处理并回复工作内容,我觉得这是墨水屏手机这段时间为我带来的好处。但是,相应的,它的流畅度是真的太低了,在某些赶时间的情况下,不能立马刷辆共享单车、处理并回复信息,真的让人很着急。

我还是希望,未来能有更好的墨水屏产品诞生,有更丰富的颜色、更细腻的显示质量和更流程的运行速度。我一定会毫不犹疑地再次入手。至于这部手机,女生自用 99 新,咱们海鲜市场见。

Bilibili Video: BV15W4y1H7vt

统计视角解读 Logit Adjustment

摘自 ICLR 2021 的论文 Long-Tail Learning via Logit Adjustment

在长尾或类别不平衡的场景下,我们总期望能最小化类别平衡错误率 Balanced Error (BER):

\[\text{BER}(f) = \frac{1}{L}\sum_{ y \in \mathcal{Y} }\mathbb{P}_{x|y}[y\in \mathop{\arg\max}\limits_{ y^{‘} \notin \mathcal{Y}}~f_{y^{‘}}(x)]
\]

这一期望可以理解为:当我们对于测试分布一无所知时,用类别均衡错误率来度量模型的好坏至少出现太大偏差。同样,也可以理解为:类别均衡错误率均匀地反映了模型在每一个类别上的性能,表达了更多有关模型性能的信息。

明确问题之后,我们不禁会思考:这个问题的贝叶斯最优分类器\(f^*\) 是什么?

\[f^* \in \mathop{\arg\min}\limits_{f:\mathcal{X}\rightarrow \mathcal{Y}}~\text{BER}(f)
\]

根据以往的文献 Collell et al., 2016 中定理 1 可以知道,最优分类器表示为:

\[\begin{equation}
\mathop{\arg\max}_{y\in \mathcal{Y}}~f^*_y(x)=\mathop{\arg\max}_{y\in \mathcal{Y}}~\mathbb{P}^{bal}(y|x)=\mathop{\arg\max}_{y\in \mathcal{Y}}~\mathbb{P}(x|y)
\label{theorem}
\end{equation}
\]

其中,\(\mathbb{P}^{bal}\) 是类别平衡的概率分布。
这理论解读为:当条件分布\(\mathbb P(x|y)\) 固定时,针对 BER 的贝叶斯最优分类器也固定,不随着\(\mathbb P(y)\) 变化而变化。

进一步,我们假定类别概率满足\(\mathbb{P}(y \mid x) \propto \exp \left(s_y^*(x)\right)\)。其中,\(s_y^*(x):\mathcal X \rightarrow \mathbb R^{|\mathcal Y|}\) 是评分函数,也就是模型输出的 Logit。
再结合类别平衡概率分布定义\(\mathbb P^{bal}(y|x) \propto \mathbb P(y|x) / \mathbb P(y)\),可以将公式\(\eqref{theorem}\) 改造为:

\[\begin{aligned}
\mathop{\arg\max}_{y\in \mathcal{Y}}\mathbb P^{bal}(y|x)
&= \mathop{\arg\max}_{y\in \mathcal{Y}}~exp(s_y^*(x))/\mathbb P(y)\\
&= \mathop{\arg\max}_{y\in \mathcal{Y}}~s_y^*(x)-\ln \mathbb P(y)
\end{aligned}
\]

到此,我们理论性地推导得到了 Logit Adjustment 技术。