简介
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]}\)进行近似预计。
上面就整个算法的整体步骤，能够分为三步：
- 首先训练针对参数\( x\)的网络
- 利用训练失去的参数估计\( x\)
- 训练参数\( \theta\)
具体算法如下所示：
试验
试验局部设计比拟多的细节，能够参考文章原文。
总结
这篇文章的逻辑还是比拟清晰的，然而因为神经汇合函数这个方向还是比拟冷门的，和自变分编码器一样数学比拟多，了解起来比拟难，目前的工作还是比拟少，能够尝试在网络架构等方面做致力。