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

1次阅读

共计 4730 个字符，预计需要花费 12 分钟才能阅读完成。

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]}$ 进行近似预计。

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