文章目录
1. 前言
前几天的论文阅读分享中我汇报的是这篇论文。感觉挺棒的，这里简单记录一下。
2. MIM
这里我将本文的Market Influence Maximization，简称为MIM问题。本文作者针对美国航空市场的收益问题提出了新的解决方案。提出了一个 Market Share Prediction Model以及后面的Market Influence Maximization两个部分的内容。本文模型和之前的模型的区别在于下面几个点：
当然，作者对比的部分只是 Market Share Prediction Model部分，以及其他论文中作者是怎么做的，而弱化了对MIM问题的说明。甚至在之前乃至之后的文章篇幅中均没有提到标题中的MIM问题的分析。而只是简单粗暴的定义了一个DNN模型，将输出的表示直接使用罗杰斯特函数来计算其比例：
这里的
m
r
,
k
m_{r, k}
mr,k就表示市场份额，也就是作者提出的Market Share Prediction Model部分。
f
r
,
k
f_{r,k}
fr,k可以看作是航班的一些属性构成的一个飞行频率矩阵。同时，这个矩阵中应该会糅杂网络结构信息，包括
因为本文的模型框架为：
在Budget Limit部分应该就是本文的重点部分。因为标题为MIM问题，故而作者需要将前面提出的Market Share Prediction Model转向MIM问题。首先定义了一个成本受限的IM问题：
最大化部分也就是利润，这里定义为
d
e
m
a
n
d
r
demand_r
demandr，表示为航线
r
r
r的总乘客人数，而
m
r
,
k
m_{r, k}
mr,k表示航空公司
k
k
k在航线
r
r
r的市场份额。从直观上来讲确实可以表示航空公司的利润。这个公式也就是他本文标题所提出的MIM问题。
然后，定义了Budget Limit部分的内容。
c
o
s
t
r
,
k
cost_{r,k}
costr,k表示航空公司
k
k
k在航线
r
r
r的单位运营成本，
f
r
,
k
,
f
r
e
q
f_{r,k,freq}
fr,k,freq表示航空公司
k
k
k在航线
r
r
r的飞行频率。单位运营成本乘以飞行频率，也就是最终的花费成本。
对于这个约束受限的极值问题，本文引入了拉格朗日求极值问题。将问题进行了转化。
上面的L也就是在拉格朗日极值问题的目标函数，因为在神经网络中为非连续函数，所以这里启发式的改写为了：
为了求极值问题，我们需要对式子进行求导工作，不妨先将整个式子写在一起：
然后对公式14进行求导：
也就是说，可以求出
λ
\lambda
λ：
然后将它回代到公式14中，可以得到：
为了进一步简化这个公式，作者在论文中定义：
上式公式8就可以简化为：
这里的 L L a g r a n g e L_{Lagrange} LLagrange也就是最终的目标函数表示。
记
o
(
A
k
)
o(\mathcal{A}_{k})
o(Ak)为
o
′
o^{'}
o′，
c
(
A
k
)
2
2
\frac{c(\mathcal{A}_{k})^2}{2}
2c(Ak)2为
c
′
c^{'}
c′，那么因为所求为最大化利润，也就是最大值，所知这里的
L
L
a
g
r
a
n
g
e
L_{Lagrange}
LLagrange的一阶导数应该是小于0的，也就是说：
而
c
c
c所求为最大限制的接近成本，故而这里的
c
′
c^{'}
c′为大于0的数。所以有：
因为求为一阶导数值为0的最大值，故而这里求近似的时候，其实
β
\beta
β也就是一个极小值。故而可以改写为：
我们这里再次回忆一下
c
(
A
k
)
c(\mathcal{A}_{k})
c(Ak)的表示：
我们所希望的是在约束下的最大值，所以我们希望花费无限接近
b
u
d
g
e
t
k
budget_k
budgetk下的MIM。也就是说其实
c
(
A
k
)
c(\mathcal{A}_{k})
c(Ak)的表示也就是一个无限接近0的量。所以可以将公式12改写为：
进一步的，作者在论文中定义了一个自适应的更新梯度的算法，叫做AGA：
我们这里关注while-do部分，也就是说当
c
(
A
k
)
c(\mathcal{A}_{k})
c(Ak)大于0的时候，也即是花费大于限制，此时需要用公式13来进行约束，也就是让
c
(
A
k
)
c(\mathcal{A}_{k})
c(Ak)接近于0。而反之，说明花费小于限制，所以这里就不需要进行约束
c
(
A
k
)
c(\mathcal{A}_{k})
c(Ak)，直接进行频率矩阵
A
k
\mathcal{A}_{k}
Ak的梯度上升即可。
简单摘几个实验结果：
3. 感悟
确实给人一种眼前一新的这种感觉。感觉自己要多思考思考为什么可以这么做，这个问题的转化是怎么想出来的。可能这真的是领域不同，因为自己所从事的是社交网络，而在航空中的利润预测问题，乃至成本限制问题，真的就统一在了这个问题中。并且得到了很好的解决。
但是唯一的缺陷就在于本文没有代码，所以也无法尝试。接着我会尝试来复现一下这个论文，看看是否可迁移和转换。