關于“On the eigenvectors of $p$-Laplacian”目標函式的優化問題
作者：凱魯嘎吉 - 博客園 http://www.cnblogs.com/kailugaji/
圖p-拉普拉斯 (Graph p-Laplacian) / p-譜聚類演算法 (p-spectral clustering) 從提出到現在有一些年景了，但關于目標函式的優化問題卻很少被提及，而是直接參考前人[2]的結論，這篇博客，我們追根溯源，從最初提出圖p-拉普拉斯開始，來探討目標函式的優化(最小化)問題，
1. Graph $p$-Laplacian
給定一個帶權無向圖$G=(V, E)$，其中$V$是邊集，$E$是點集，
$H(V)$: The Hilbert space of real-valued functions on each vertex.
$H(E)$: The Hilbert space of real-valued functions on each edge.
The graph $p$-Laplacian ${{\Delta }_{p}}:H(V)\to H(V)$ 為：
${{\Delta }_{p}}f=-\frac{1}{2}div({{\left\| \nabla f \right\|}^{p-2}}\nabla f)$
其中$\Delta $是拉普拉斯算子，$\nabla $是梯度，$div$為散度，當$p=2$時，${{\Delta }_{p}}f={{\Delta }_{2}}f=-\frac{1}{2}div(\nabla f)$，此時，圖$p$-拉普拉斯退化為標準的圖拉普拉斯，
通過引入函式$f$的二次型，標準圖拉普拉斯算子${{\Delta }_{2}}$滿足：
$\left\langle f,{{\Delta }_{2}}f \right\rangle =\frac{1}{2}\sum\limits_{i,j\in V}{{{w}_{ij}}{{({{f}_{i}}-{{f}_{j}})}^{2}}}$
與圖拉普拉斯類似，$p$-拉普拉斯算子[1]滿足：
$\left\langle f,{{\Delta }_{p}}f \right\rangle =\frac{1}{2}\sum\limits_{i,j\in V}{{{w}_{ij}}{{\left| {{f}_{i}}-{{f}_{j}} \right|}^{p}}}$
對于每一個節點$i\in V$，未規范化的圖$p$-拉普拉斯算子為：
${{(\Delta _{p}^{w})}_{i}}=\sum\limits_{j\in V}{{{w}_{ij}}{{\phi }_{p}}({{f}_{i}}-{{f}_{j}})},i\in V$
其中${{\phi }_{p}}(x)={{\left| x \right|}^{p-1}}sig(x)$，
定義一個特征向量
${{(\Delta _{p}^{w}f)}_{i}}={{\lambda }_{p}}{{\phi }_{p}}({{f}_{i}}),i\in V$
注：特征向量在縮放時是不變的，
定理1：$f$是$p$-拉普拉斯的特征向量，當且僅當下列函式${{F}_{p}}$在$f$處有臨界點：
${{F}_{p}}(f)=\frac{\left\langle f,{{\Delta }_{p}}f \right\rangle }{\left\| f \right\|_{p}^{p}}=\frac{\sum\nolimits_{ij}{{{w}_{ij}}{{\left| {{f}_{i}}-{{f}_{j}} \right|}^{p}}}}{2\left\| f \right\|_{p}^{p}}$(廣義Rayleigh-Ritz原理)
其中$\left\| f \right\|_{p}^{p}=\sum\nolimits_{i}{{{\left| {{f}_{i}} \right|}^{p}}},\text{ }i,j\in V$，相應地特征值${{\lambda }_{p}}$通過等式${{\lambda }_{p}}={{F}_{p}}(f)$得出，
2. 用圖$p$-拉普拉斯進行$K$聚類
Luo等人[2]通過求解下面的$p$-拉普拉斯嵌入問題，引入了對$p$-拉普拉斯全特征向量的一種近似，目標函式為：
$\underset{F}{\mathop{\min }}\,{{J}_{E}}(F)=\sum\limits_{k}{\frac{\sum\nolimits_{ij}{{{w}_{ij}}{{\left| f_{i}^{k}-f_{j}^{k} \right|}^{p}}}}{\left\| {{f}^{k}} \right\|_{p}^{p}}}$
$s.t.\text{ }{{F}^{T}}F=I.$
但是，在求導程序中出現錯誤，原文截圖為：
也就是從這里起，后面的結果已經無效，
我推導的為：
$\frac{\partial {{J}_{E}}}{\partial f_{i}^{k}}=\frac{1}{\left\| {{f}^{k}} \right\|_{p}^{p}}\left[ p\sum\nolimits_{j}{{{w}_{ij}}{{\phi }_{p}}(f_{i}^{k}-f_{j}^{k})}-p\sum\nolimits_{j}{{{w}_{ji}}{{\phi }_{p}}(f_{j}^{k}-f_{i}^{k})} \right]-\sum\nolimits_{ij}{{{w}_{ij}}{{\left| f_{i}^{k}-f_{j}^{k} \right|}^{p}}}\cdot \frac{p\cdot {{\phi }_{p}}(f_{i}^{k})}{{{\left( \sum\nolimits_{i}{{{\left| {{f}_{i}} \right|}^{p}}} \right)}^{2}}}$
$=\frac{p}{\left\| {{f}^{k}} \right\|_{p}^{p}}\left[ 2\sum\nolimits_{j}{{{w}_{ij}}{{\phi }_{p}}(f_{i}^{k}-f_{j}^{k})}-\frac{{{\phi }_{p}}(f_{i}^{k})}{\left\| {{f}^{k}} \right\|_{p}^{p}}\sum\nolimits_{ij}{{{w}_{ij}}{{\left| f_{i}^{k}-f_{j}^{k} \right|}^{p}}} \right]$
不管怎樣，在求導的程序中，總會有系數$p$，而[2]中沒有，可以認為這篇文章在求偏導的程序中出現問題，
演算法總體流程：
注：(22)公式出錯，
有趣的是，直接參考這篇文章結論的大有論文在，例如，這一篇[4]
更有趣的是，時隔整整十年，[3]明確指出[2]中的推導錯誤：
[3]給出了他自己提的目標函式與求導公式：
可以看出，[3]的推導結論與我的推導是一致的，只是目標函式分母部分有無系數2，
3. 參考文獻
[1] Bühler, Thomas & Hein, Matthias. (2009). Spectral clustering based on the graph Laplacian. Proceedings of the 26th International Conference On Machine Learning, ICML 2009. 382. 11-88. 10.1145/1553374.1553385. Code: p-Spectral Clustering
[2] Luo, Dijun & Huang, Heng & Ding, Chris & Nie, Feiping. (2010). On the eigenvectors of p-Laplacian. Machine Learning. 81. 37-51. 10.1007/s10994-010-5201-z.
[3] Pasadakis, Dimosthenis & Alappat, Christie & Schenk, Olaf & Wellein, Gerhard. (2020). $K$-way $p$-spectral clustering on Grassmann manifolds.
[4] W. Liu, X. Ma, Y. Zhou, D. Tao and J. Cheng, "$p$-Laplacian Regularization for Scene Recognition," in IEEE Transactions on Cybernetics, vol. 49, no. 8, pp. 2927-2940, Aug. 2019, doi: 10.1109/TCYB.2018.2833843.
[5] 拉普拉斯矩陣與拉普拉斯算子的關系 - 知乎
最后的思考：做研究切忌浮躁，要追根溯源，明白公式的來龍去脈，自己動手，豐衣足食，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205080.html
標籤：其他