关于算法:Learning-Neural-Set-Functions

简介

Neural Set Functions，神经符号函数，是一种相似于自编分编码器的技术，广泛应用于举荐零碎和异样检测。具体而言，就是利用神经网络，对汇合中元素进行估值或者抉择，算是传统基于效用函数办法的一种改良。我这里次要参考了腾讯 AI Lab 卞亚涛老师的文章：

Ou, Z., Xu, T., Su, Q., Li, Y., Zhao, P., & Bian, Y. (2022). Learning neural set functions under the optimal subset oracle. In Advances in Neural Information Processing Systems.
Bian, Y., Rong, Y., Xu, T., Wu, J., Krause, A., & Huang, J. (2022). Energy-based learning for cooperative games, with applications to valuation problems in machine learning. In International Conference on Learning Representations.
Liu, W., Wang, X., Owens, J., & Li, Y. (2020). Energy-based out-of-distribution detection. In Advances in Neural Information Processing Systems, 33, 21464-21475.

问题形容

对于一个汇合 \(V\)，其分汇合 \(S\subseteq V\)，由参数 \(\theta\) 决定的效用函数 \(F_{\theta}(S;V) \)，对应的汇合品质函数 \(p_{\theta}(S\mid V) \) 也由参数 \(\theta\) 决定，上面就对问题进行形容，咱们的优化指标是最大化穿插熵。
从概率论的角度来看，问题能够被形容成以下的问题：

$$
\begin{aligned}
&\underset{\theta}{\mathrm{arg}\max}\mathbb{E} _{\mathbb{P} (V,S)}\left[\log p_{\theta}(S\mid V) \right]\\
&\,\,\mathrm{s}.\mathrm{t}. p_{\theta}(S\mid V)\propto F_{\theta}(S;V),\forall S\in 2^V\\
\end{aligned}
$$

具体而言，能够转化为如下的优化问题：

$$
\begin{matrix}
\max\mathrm{imize}& -\sum_{S\subseteq V}{p}(S)\log p(S)\\
\mathrm{subject}\,\mathrm{to}& \sum_{S\subseteq V}{p}(S)F(S)=\mu ,\forall S\subseteq Vp(S)\ge 0,\sum_{S\subseteq V}{p}(S)=1.\\
\end{matrix}
$$

结构对应的拉格朗日函数为：

$$
L\left(p,\lambda _0,\lambda _1 \right) :=-\left[\sum_{S\subseteq N}{p}(S)\log p(S)+\lambda _0\left(\sum_{S\subseteq N}{p}(S)-1 \right) +\lambda _1\left(\mu -\sum_{S\subseteq N}{p}(S)F(S) \right) \right]
$$

由

$$
\frac{\partial L\left( p,\lambda _0,\lambda _1 \right)}{\partial p(S)}=-\left[\log p(S)+1+\lambda _0-\lambda _1F(S) \right] =0
$$

可得

$$
\begin{aligned}
p(S)&=\exp \left[-\left(\lambda_0+1-\lambda_1 F(S)\right)\right] \\
\lambda_0+1 &=\log \sum_{S \subseteq N} \exp \left(\lambda_1 F(S)\right)=: \log Z
\end{aligned}
$$

因而，咱们有

$$
p(S)=\frac{\left. \exp \left[ \lambda _1F(S) \right) \right]}{\mathrm{Z}}
$$

此外，

$$
H_{\max}=-\sum_{S\subseteq N}{p}(S)\log p(S)=\lambda _0+1-\lambda _1\sum_{S\subseteq N}{p}(S)F(S)=\lambda _0+1-\lambda _1\mu
\\
\lambda _1=-\frac{\partial H_{\max}}{\partial \mu}=:\frac{1}{T}
\\
p(S)=\frac{\exp\mathrm{[}F(S)/T)]}{\sum_{S\subseteq N}{\exp}[F(S)/T]}.
$$

这就表明，如果能够失去效用函数 \(F(S) \)，那么密度函数 \(p(S) \) 也能相应地失去。
此外，文章外面也证实了对于这个优化问题，实在数据密度函数是惟一的。

神经汇合函数

这里引入了一个全新的变量 \(X\)，其中重量 \(x_i\) 代表事件 \(i\) 是否属于汇合 \(S\)，这里咱们引入了 KL 散度，

$$
\mathbf{x}^*=\arg \min _{\mathbf{x}} \mathbb{K} \mathbb{L}(q(S ; \mathbf{x}) \| p(S))
$$

这里咱们将事件间的关系齐全解耦，并应用伯努利散布来金斯示意 \(q(S;\mathbf{x}):=\prod_{i\in S}{x_i}\prod_{j\notin S}{\left( 1-x_j \right)},\mathrm{x}\in [0,1]^n\)
上面就是具体的推导，和自变分编码器的思路是统一的，

$$
\begin{aligned}
0&\le \mathbb{K} \mathbb{L} (q\parallel p)=\sum_{S\subseteq N}{q}(S;\mathbf{x})\log \frac{q(S;\mathbf{x})}{p(S)}&=-\mathbb{E} _{q(S;\mathbf{x})}[\log p(S)]-\mathbb{H} (q(S;\mathbf{x}))\\
&=-\mathbb{E} _{q(S;\mathbf{x})}\left[\frac{F(S)}{T}-\log\mathrm{Z} \right] -\mathbb{H} (q(S;\mathbf{x}))\\
&=-\sum_{S\subseteq N}{\frac{F(S)}{T}}\prod_{i\in S}{x_i}\prod_{j\notin S}{\left( 1-x_j \right)}+\sum_{i=1}^n{\left[ x_i\log x_i+\left( 1-x_i \right) \log \left(1-x_i \right) \right]}+\log\mathrm{Z}.\\
\end{aligned}
$$

因而，咱们有

$$
\begin{aligned}
\log\mathrm{Z}&\ge \sum_{S\subseteq N}{\frac{F(S)}{T}}\prod_{i\in S}{x_i}\prod_{j\notin S}{\left( 1-x_j \right)}-\sum_{i=1}^n{\left[ x_i\log x_i+\left( 1-x_i \right) \log \left(1-x_i \right) \right]}\\
&=\frac{f_{\mathrm{mt}}^{F}(\mathrm{x)}}{T}+\mathbb{H} (q(S;\mathbf{x})):=(\mathrm{ELBO)}\\
\end{aligned}
$$

其中

$$
f_{\mathrm{mt}}^{F}(\mathrm{x)}:=\sum_{S\subseteq N}{F}(S)\prod_{i\in S}{x_i}\prod_{j\notin S}{\left( 1-x_j \right)},\mathrm{x}\in [0,1]^n,
$$

上式对 \(x_i \) 求偏导能够失去平衡点为：

$$
x_i^*=\sigma\left(\nabla_i f_{\mathrm{mt}}^F\left(\mathrm{x}^*\right) / T\right)=\left(1+\exp \left(-\nabla_i f_{\mathrm{mt}}^F\left(\mathrm{x}^*\right) / T\right)^{-1}\right.
$$

其对指标 \(i \) 的梯度为：

$$
\begin{aligned}
\nabla _if_{\mathrm{mt}}^{F}(\mathbf{x})&=\mathbb{E} _{q\left( S;\left( \mathbf{x}\mid x_i\gets 1 \right) \right)}[F(S)]-\mathbb{E} _{\left. q\left( S;\mathbf{x}\mid x_i\gets 0 \right) \right)}[F(S)]\\
&=f_{\mathrm{mt}}^{F}\left(\mathbf{x}\mid x_i\gets 1 \right) -f_{\mathrm{mt}}^{F}\left(\mathbf{x}\mid x_i\gets 0 \right)\\
&=\sum_{S\subseteq N,S\ni i}{F}(S)\prod_{j\in S-i}{x_j}\prod_{j^{\prime}\notin S}{\left( 1-x_{j^{\prime}} \right)}-\sum_{S\subseteq N-i}{F}(S)\prod_{j\in S}{x_j}\prod_{j^{\prime}\notin S,j^{\prime}\ne i}{\left( 1-x_{j^{\prime}} \right)}\\
&=\sum_{S\subseteq N-i}{[}F(S+i)-F(S)]\prod_{j\in S}{x_j}\prod_{j^{\prime}\in N-S-i}{\left( 1-x_{j^{\prime}} \right)}\\
&=\sum_{S\subseteq N-i}{[}F(S+i)-F(S)]q\left(S;\left( \mathbf{x}\mid x_i\gets 0 \right) \right) =\mathbb{E} _{S\sim q\left( S;\left( \mathbf{x}\mid x_i\gets 0 \right) \right)}[F(S+i)-F(S)].\\
\end{aligned}
$$

具体而言，其梯度能够由 \(\frac{1}{m}\sum_{k=1}^m{\left[ F\left( S_k+i \right) -F\left(S_k \right) \right]}\) 进行近似预计。

上面就整个算法的整体步骤，能够分为三步：

1. 首先训练针对参数 \(x\) 的网络
2. 利用训练失去的参数估计 \(x\)
3. 训练参数 \(\theta\)
   具体算法如下所示：

试验

试验局部设计比拟多的细节，能够参考文章原文。

总结

这篇文章的逻辑还是比拟清晰的，然而因为神经汇合函数这个方向还是比拟冷门的，和自变分编码器一样数学比拟多，了解起来比拟难，目前的工作还是比拟少，能够尝试在网络架构等方面做致力。