Sample Complexity of Learning Multi-value Opinions in Social Networks
Sample Complexity of Learning Multi-value Opinions in Social Networks
复制标题
社交网络中学习多值意见的样本复杂性
DOI：
10.1007/978-3-031-21203-1_12
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Oyama Satoshi
中科院分区：
文献类型：
--
作者：
Shinoda Masato;Sakurai Yuko;Oyama Satoshi
我们考虑我们需要查询多少用户，以估计多值意见（信息）在社交网络中传播的程度。例如，如果新产品的发布日期已更改多次，则公司可能想知道最新信息已传达给哪些人。在我们考虑的传播模型中，社交网络被表示为有向图，并且代理（节点）如果接收到更强的意见（更新的信息）则更新其状态，然后根据其边的方向转发意见。以前的工作评估意见传播的社会网络中使用的可能近似正确（PAC）的学习框架，并认为只有二进制的意见。一般来说，PAC的可学习性，即，当从二值模型推广到多值模型时，不能保证所需样本数量的有限性。我们表明，PAC学习的多值意见传播在社会网络。我们首先证明了多意见模型所需的样本数是二意见模型所需的样本数的倍，当意见数为时。接下来，我们证明了学习多意见模型所需样本数量的上界和下界可以从Natarajan维度确定，这是Vapnik-Chervonenkis维度的推广。
We consider how many users we need to query in order to estimate the extent to which multi-value opinions (information) have propagated in a social network. For example, if the launch date of a new product has changed many times, the company might want to know to which people the most current information has reached. In the propagation model we consider, the social network is represented as a directed graph, and an agent (node) updates its state if it receives a stronger opinion (updated information) and then forwards the opinion in accordance with the direction of its edges. Previous work evaluated opinion propagation in a social network by using the probably approximately correct (PAC) learning framework and considered only binary opinions. In general, PAC learnability, i.e., the finiteness of the number of samples needed, is not guaranteed when generalizing from a binary-value model to a multi-value model. We show that the PAC learnability of multi-value opinions propagating in a social network. We first prove that the number of samples needed in a multi-opinion model is sufficient fortimes the number of samples needed in a binary-opinion model, whenis the number of opinions. We next prove that the upper and lower bounds on the number of samples needed to learn a multi-opinion model can be determined from the Natarajan dimension, which is a generalization of the Vapnik-Chervonenkis dimension.