领域—人工智能神经网络

Label-Smoothing

https://www.datalearner.com/blog/1051561454844661

标注数据不准确的时候，用交叉熵不太好。训练数据不会覆盖所有的情况，也不会全部都是准确的，所以使用交叉熵其实并不好。

其实是把原来的标注做一些修改，比如把[0,1]改为[0.05,0.95]

https://zhuanlan.zhihu.com/p/101553787

神经网络被训练得对自己的答案不那么自信。标签平滑强制对分类进行更紧密的分组，同时强制在聚类之间进行更等距的间隔。

以前的研究(Guo et al)表明，神经网络常常过于自信，相对于它们的真实准确性校准得很差。

算法

NP-NPC-NP-hard

P问题：指的是能在多项式时间内解决的问题。
NP问题：指的是能在多项式时间内验证的问题。在此，我们可以看出所有的P问题都属于NP问题，但是P是否等于NP呢，至今还未得到验证，即既证明不了P=NP，也证明不了P≠NP。
NPC问题（NP完全问题）：是指NP问题中最难的一类问题。证明一个问题是否是NPC问题：（1）先证明此问题是NP问题；（2）此问题可以通过一个已知是NPC的问题规约得到。由证明可知，必须得先定义第一个NPC问题，即电路可满足性问题。
NP-hard问题：这类问题至少比NP问题难。

————————————————
版权声明：本文为CSDN博主「Louis_lan」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liu14lang/article/details/84898516

=====

NP-hard：比所有的NP问题都难的问题

怎么理解 P 问题和 NP 问题？ - 王宇的回答 - 知乎
https://www.zhihu.com/question/27039635/answer/101730260

=======

NP问题有很多种，但若所有的NP问题都能多项式归约到问题X，X为NP hard

这里又要说道归约上了。如果A能用多项式次的B解决，称A能多项式归约到B。比如说现在问题A为判定二年级是否有人刷知乎, 那我可以把这个问题规约到问题B:判定每个班级是否有人刷知乎。 只要对二年级所有的班级做一边问题B，就能得到A的结果，如果这个次数是输入规模的多项式级别，我们认为A可以多项式规约到B。

作者：武翔宇
链接：https://www.zhihu.com/question/27039635/answer/49977321
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

=====

例子：k-clique问题：

problem： Prove that the following problem is NP-complete:given an undirected graph G=(V,E) and an integer k,
return a clique of size k as well as an independent set of size k,provided both exist.

首先，独立集和团是两个相对的概念，找K个元素的独立集和团是可以等价的。

对于任意一个有k个项的3SAT表达式，我们对于每个项构造一个三点三边呈现三角形的子图，（共有k个三角形）

对于每个变量，两种相反的形式（每隔变量取非）之间连一条边，如果能够找到k个元素的独立集，必然k个点分布在k个三角形，即选择了k个变量，使得表达式满足。

于是，当我们有多项式时间算法解决k独立集问题时，我们就一定有多项式时间算法解决3SAT问题，所以k独立集问题是NP-complete problem.

同样的，k独立集的等价命题 k-clique问题也是NP-complete的。
————————————————
版权声明：本文为CSDN博主「cryqqqcy」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/cryqqqcy/article/details/75118779

领域—社交网络推荐系统

graph-learning

图传播算法（上）：

https://mp.weixin.qq.com/s?__biz=MzI2MDE5MTQxNg==&mid=2649687693&idx=1&sn=1dc186d11b7c802ef518b32785c78e4a&chksm=f276c35ac5014a4cfb7d8fa6eb636ba011c99f519f6079512370fbfcc2cd5a37a739de72a7f2&scene=21#wechat_redirect

不断更新函数

PageRank

被更多网页链接到的网页更重要；有更少外链的网页将会传递更高的权重

图传播算法（下）

https://mp.weixin.qq.com/s?src=11&timestamp=1585742506&ver=2252&signature=-p016dG11Ls4lF6y2CFtc9MoFBxPNWIRivL9mZqPEgo32c3r4u20xW8EBfK1EmKiaQ4bfR77kUYz3X0Z5CabGJ*L9B1MntleaAGGAwrsTyHtQ7eVhXydbGpHCi1wvfit&new=1

HITS

  • Authority：可理解为权威页面，一般包含高质量内容。
  • hub：可理解为导航页面，指向很多Authority页面。

其经验假设为：

  • 被越多的hub页面所指向的页面，内容质量越高。
  • 一个hub页面会尽可能地指向更高质量的内容页面。

Weisfeiler-Lehman

解决图的相似性问题，虽然算法要解决的问题聚焦在Graph层面上，但是其立足点还是在节点上，如果我们能够找到一种衡量节点独立性（unique）的方法，那么我们就可以将图视作一个包含这些独立性节点的集合，两张图的相似性可以转化为两个集合的Jaccard相似度。

在节点邻居信息的基础上，加上哈希函数。

RVE2

解决恶意评分场景下问题。

给定一个有向的，带有权重的二部图Bipartite Graph G=（U,R,P）。其中，U代表用户集合，P代表商品集合，R表示所有边的集合，边（μ,p）表示用户μ对商品p的一次评分操作，设评分为score(μ,p)，score(μ,p)∈[-1,1]。

分别对用户、商品、评分设计了衡量指标。

刻画了上述三个指标之后，可以总结出下面5条经验假设：

  • 质量好的商品得到更高的评分
  • 质量好的商品得到更多可靠的正面评分
  • 可靠的评分在数值上更接近商品的质量
  • 可靠的评分来自公正用户
  • 给出越可靠评分的用户公正度越高

更新公式会趋向于忽略低可靠度的评分，而加大高可靠度评分的权重。也可证明，更新公式全部符合上述五条经验假设。

图卷积神经网络

https://mp.weixin.qq.com/s?__biz=MzI2MDE5MTQxNg==&mid=2649687812&idx=2&sn=c287f48f04b4755577da8ce46c487582&chksm=f276c2d3c5014bc57aaa25c7c50d87ba6d46762d79e1aa5761325bed25955be578253811ff60&scene=21#wechat_redirect

卷积神经网络很好，但是它研究的对象还是限制在Euclidean domains的数据。什么是Euclidean data？ Euclidean data最显著的特征就是有规则的空间结构，比如图片是规则的正方形栅格，比如语音是规则的一维序列。而这些数据结构能够用一维、二维的矩阵表示，卷积神经网络处理起来很高效。

但是，我们的现实生活中有很多数据并不具备规则的空间结构，称为Non Euclidean data。比如推荐系统、电子交易、计算几何、脑信号、分子结构等抽象出的图谱。这些图谱结构每个节点连接都不尽相同，有的节点有三个连接，有的节点有两个连接，是不规则的数据结构。

图卷积算子：发射消息、接收消息、变换

局部参数共享，感受域正比于层数

领域—社交网络推荐系统

图的拉普拉斯矩阵&拉普拉斯算子

https://zhuanlan.zhihu.com/p/85287578

拉普拉斯算子其实就是对每个变量分别求个二阶导，然后再加起来。如果用离散的方法来写的话就可以感觉是周围点与中心点的梯度差，或者说四个方向相邻的减去四个中心的。当中心点受到扰动之后，其可能变为相邻的周围点之一，拉普拉斯算子得到的是对该点进行微小扰动后可能获得的总增益 （或者说是总变化）。

图的拉普拉斯，周围点就相当于是这里的邻居节点，中心点就相当于图的要研究的那个节点，所以按照之前的算法，这里就等于他的 邻居节点的信息加起来 减去 邻居个数乘上自己的信息。所以用权重矩阵$W$的话，他的相反数就是：$\Delta f_{i}=\sum_{j \in N} W_{i j}\left(f_{i}-f_{j}\right)$（刚才拉普拉斯这里是周围减去中间，现在是中间减去周围，所以说相反数），这里$i$的信号就用$f_i$表示，如果不相邻，这里的$W_{ij}$就是0，所以算出来的结果就是相邻的所有节点和自己的差的和。

每一个算出来的$\Delta f_{i}$组合成一个列向量，如果把他们分解成 一个矩阵 乘 所有$f_i$的行向量 的话，就可以发现这个矩阵就是$D-W$。

半正定的证明：https://blog.csdn.net/beiyangdashu/article/details/49300479?utm_source=blogxgwz7