问题标签 [online-algorithm]

I am trying to ascertain how VowpalWabbit's "state" is maintained as the size of our input set grows. In a typical machine learning environment, if I have 1000 input vectors, I would expect to send all of those at once, wait for a model building phase to complete, and then use the model to create new predictions.

In VW, it appears that the "online" nature of the algorithm shifts this paradigm to be more performant and capable of adjusting in real-time.

1. How is this real-time model modification implemented ?

2. 随着时间的推移，大众是否会在总输入数据大小方面占用越来越多的资源？也就是说，当我向我的大众模型添加更多数据时（当它很小时），一旦特征向量输入的累积数量增加到 1000、10000 或数百万，实时调整计算是否开始花费更长的时间？

“批量处理”是指一次处理所有事实的静态数据集（如在 CSV 中）以提取知识。在“在线”时，它使用实时支持存储：事实在发生时添加（“X 购买 Y”），并在此实时数据上发生查询（“您会向正在查看 y 的人推荐什么？” ）。

我（错误地）使用了“实时”一词，但我并不是说结果必须在固定时间内出现。('''编辑：上面的实时替换为在线''')

我想到了一个使用实时数据的推荐引擎。但是，我遇到的所有在线资源（例如 SO 问题）都没有区分实时数据挖掘包和批量处理数据挖掘包。我不得不单独搜索：

• 从 Lucene/Solr 和其他实时数据集（在线）读取的 Carrot2
• Knime 对静态文件（批量）执行计划执行
• Mahout 在 Hadoop（以及未来基于 Pregel 的 Giraph）上运行（在线？）
• 与 Cassandra 集成的商业软件包（在线？）

什么是在线数据挖掘包？

文献没有区分在线和批量处理包有什么原因吗？还是所有实际的数据挖掘本质上都是批量操作？

在我的聚类问题中，不仅点可以来去去去，而且特征也可以删除或添加。我的问题是否有任何聚类算法。

具体来说，我正在寻找这类聚类算法的凝聚层次聚类版本。

通常，我有一个更技术性的问题，但我会用一个数球的例子为你简化它。

假设我有不同颜色的球和为每种颜色保留的数组的一个索引（初始化为全 0）。每次我选择一个球，我都会将相应的索引增加 1。

球是随机挑选的，我一次只能挑选一个球。我唯一的目的是计算每种颜色的球数，直到我用完球。

我想计算不同颜色的球数量的标准偏差，同时我正在计算它们。在计算完所有球后，我不想通过再次遍历数组来计算它。

可视化：

随机排列的球：（BBGRRYYBBGGGGGGB每个字母代表颜色的第一个字母）从 0 到 3 的数组索引分别对应颜色 B、G、R 和 Y。当我完成挑选球时，我的阵列看起来像[5,7,2,2]。

在拥有最终数组后计算标准偏差非常简单，但我想在填充这个数组时这样做。

我想用 Java 做，我有大约 1000 种颜色。

实现它的最有效方法是什么？或者在拥有最终数组之前有没有办法做到这一点？

我想在大文本语料库上应用快速的在线降维技术，例如（在线/小批量）字典学习。我的输入数据自然不适合内存（这就是我想使用在线算法的原因）所以我正在寻找一种可以迭代文件而不是将所有内容加载到内存中的实现。可以用 sklearn 做到这一点吗？有替代品吗？

感谢注册

这是一个理论问题。假设我已经实现了两种类型的协同过滤：基于用户的 CF 和基于项目的 CF（以Slope One的形式）。

我有一个很好的数据集供这些算法运行。但后来我想做两件事：

1. 我想为数据集添加一个新评级。
2. 我想编辑现有评级。

我的算法应该如何处理这些变化（不做很多不必要的工作）？任何人都可以帮助我吗？

我了解到，神经网络可以复制任何功能。

通常，神经网络被输入一组描述符给它的输入神经元，然后在它的输出神经元上给出一个特定的分数。我希望我的神经网络能够识别屏幕上的某些行为。屏幕上的物体已经经过预处理并且清晰可见，因此识别应该不是问题。

是否可以使用神经网络来识别屏幕的像素化图片并在此基础上做出决策？训练数据的数量当然是巨大的。有没有办法通过在线监督学习来教授人工神经网络？

编辑：因为评论者说编程问题太笼统了：我想先在 python 中实现它，看看它是否有效。如果有人能指出我可以使用 python 进行在线学习的资源，我将不胜感激。

我在回答这个问题时看到了这个算法。

这是否正确计算标准偏差？有人可以告诉我为什么这在数学上有效吗？最好从这个公式中恢复：

考虑一棵树，其中每个节点都与系统状态相关联，并包含在系统上执行的一系列操作。

根是与系统的原始状态相关联的空节点。与节点关联的状态n是通过将包含在原始系统状态中的动作序列应用n到原始系统状态而获得的。节点的动作序列n是通过将新动作排队到父动作序列来获得的。

从一个节点移动到另一个节点（即，将一个新动作添加到动作序列中）会产生一个增益，该增益附加到连接两个节点的边上。

一些“数学”：

• 每个系统状态S都与一个值相关联U(S)
• n与状态相关的节点所获得的增益S不能大于U(S)和小于0
• 如果n和m是树中的节点 并且n是 , 的父节点m，即和U(n) - U(m) = g(n,m)之间的边上的增益表示从到的减少nmUnm

请参见图中的示例。

我的目标是在树中找到保证最高增益的路径（其中路径的增益是通过将路径上边缘的所有增益相加来计算的）：

请注意，树在一开始是未知的，因此不需要访问整个树的解决方案（丢弃肯定不会带来最佳解决方案的那些路径）以找到最佳解决方案将是最佳选择。

注意：我在这里和这里获得了一个答案，用于离线模式下的类似问题，即当图形已知时。但是，在这种情况下，树是未知的，因此诸如 Bellman-Ford 之类的算法的性能不会比蛮力方法（如建议的那样）好。相反，我想构建类似于回溯的东西，而不是构建整个树来找到最佳解决方案（分支和绑定？）。

编辑：随着深度的增加，U(S) 变得越来越小。

我将此作为在线计算可变长度数据数组的方差和均值的参考：http: //www.johndcook.com/standard_deviation.html。

数据是一组 16 位无符号值，可以有任意数量的样本（实际上，最小值约为 20 个样本，最大值约为 2e32 个样本。

由于数据集可能太大而无法存储，我已经使用上面提到的 C 在线算法实现了这一点，并验证了它的计算是否正确。

问题始于对应用程序的以下要求：除了计算整个集合的方差和均值外，我还需要计算由中间 50% 值组成的总体的分离结果（均值和方差），即忽略前 25% 和后 25% 的样本。事先不知道样本的数量，所以我必须在线计算附加集。

我知道我可以通过单独计算来添加和减去一个子集，并且它们使用类似于此处描述的 operator+ 实现：http: //www.johndcook.com/skewness_kurtosis.html（减去偏度和峰度细节，为此我没有用）。减法可以由此得出。

问题是：我如何维护这些子集？还是我应该尝试另一种技术？