一种缓存预测模型的算法

机器学习中最常见的任务是为特定问题构建预测模型。机器学习中的预测模型可以是简单的二元分类器，回归模型或更奇特的东西。大量的机器学习文献正是关注如何构建这样的机器学习模型。

在过去的20年里，万维网的快速发展和我们世界的不断数字化推到了现有基础设施和算法的极限，导致了我们通常所说的“大数据”。大数据意味着，除了明显的“更大”的规模、更高的数据速度、异构性和数据的基本属性之外，当数据超过某个阈值时，会给一个正常工作的经典系统带来问题。

在这种范式转换中，机器学习从一开始就在最前沿。数据的空前可用性创造了令人兴奋的机会，但也带来了一些具体的挑战。更多数据通常意味着更好的模型，但扩展学习算法以使其能够使用所有可用数据需要更改实现（使用分布式/云环境或GPU），有时甚至连下面的原则(现在，像随机梯度下降这样的简单优化方法比像拟牛顿方法这样更复杂但可扩展的技术更受青睐)。

一种缓存预测模型的算法

在这篇简短的文本中，我们尝试描述并提供一个简单的解决方案，用于解决大数据学习系统开发人员面临的一个鲜为人知的问题：在模型非常大的情况下实时预测。这里“非常大”相当于模型的总大小比可用RAM大的事实。

基本上，我们有以下场景。我们接收一个带标签的数据集，我们想对一些不可见的实例进行预测。数据集可以自然地划分为许多子集，以便更方便(从准确性和训练时间角度来看)在每个子集中有一个预测器，而不是对所有数据只有一个预测器。在预测时，数据以在线方式到达，我们希望系统能够实时工作。到目前为止，一切顺利;这看起来像是一个标准的机器学习问题。正如我们前面提到的，挑战在于模型可能太大，无法将它们全部存储在内存中。

为了使事情更具体，让我们看看我们遇到的具体问题。我们有一堆二手车广告。价格是“标签”，特征是诸如生产年份、里程和动力等，任务是实时预测的价格。为了做到这一点，我们在汽车模型的基础上分割数据，对于每一组，我们训练一个回归模型(在这个讨论中使用哪种模型并不重要)。然后，当我们收到一个新的广告，我们检查汽车模型并应用适当的预测。

为了快速预测，理想情况下我们希望将所有预测模型保留在RAM中。由于有限的可用内存，这并不总是可行的。为了最小化模型加载操作（即使在具有SSD的机器上也很昂贵），我们使用了不那么新的想法为模型实现缓存机制，以便随时可用那些最有可能使用的机器学习模型。换句话说，我们尝试使用有效的内存分配策略来优化预测速度。

我们根据缓存命中率定义最优性。这通常是一个不错的选择。即使模型尺寸在很大范围内变化，由于较大的模型具有较高的加载时间，因此命中率仍然相关。

我们采取的方法是根据现有的数据估计每个汽车模型出现的概率。为此，我们对数据做了两个假设:

1.每个广告都是从一些未知的概率分布中独立得出的。
2.广告的分布是固定的，或随着时间的推移缓慢变化。

在许多情况下，这种假设是很自然的。但即使它们不完全正确，算法仍然可以工作。

该算法有两个主要组成部分：一个试图确定广告可能性的概率估计器和一个缓存决策方法，它告诉我们是否需要更改内存中加载的模型。

通常，事件的概率近似于该事件的频率。在我们的例子中，因为概率分布可能会随时间发生变化，所以最好根据时间对数据进行不同的加权 - 随着时间的推移，事件变得越来越不相关。

看一个例子是很有用的，让我们考虑我们已经收到了以下的广告(在任意的时间t之前):VW-GOLF, OPEL-ASTRA, VW-GOLF, VW-PASSAT, VW-PASSAT和VW-GOLF。

一种缓存预测模型的算法

VW Golf在t时刻的“概率”近似为:

P(t,VW-GOLF) = ((((d + 0)d + 1)d + 0) d + 0)d + 1

，其中d是“丢弃旧信息”所需的超级“dumping factor”（我们使用值0.999）。请注意，这个值实际上不是概率，因为我们没有进行过归一化，但这是我们想要的，因为实际值并不重要，我们只需要能够比较它们。

该算法的工作原理如下。只要有足够的内存，我们会在预测需要时立即加载其他模型。当超过某个内存阈值时，我们会停止添加新模型。在这种情况下，如果我们有一个缓存未命中，我们会替换已经加载的预测模型，并找到一个比在RAM中具有预测模型的最不可能的汽车更可能发生的新汽车模型。当然，在每个接收到的广告之后，通过将所有“概率”乘以dumping factor并将1加到观察模型的“概率”来更新概率。很简单，就像广告一样！

使用的不同参数 - 相关阈值，dumping factor等是在经验基础上设定的 - good old fashion trial and error strategy .

以下Python代码表示算法的基本模拟：

import random
# Here the items are just some int value
make_models = [int(random.gauss(5, 2)) for i in range(100)]
dict_models = {}
dict_stats = {}
# Relevance coefficient
_REL_COEFF = 1.2;
# Relevance increment
_REL_INC = 1.0;
# Damping factor
_DF = 0.999;
free_memory = 100
memory_limit = 50
_dictionary_ = {}
_dictStats_ = {}
min_fr = float("inf")
min_key = ""
# System receive a stream of items
for make_model in make_models:
 # Update the statistics
 if make_model in _dictStats_:
 _dictStats_[make_model] = _dictStats_[make_model] + _REL_INC
 if make_model in _dictionary_:
 if _dictStats_[make_model] &lt;= min_fr + _REL_INC:
 min_fr = min_fr + _REL_INC
 min_fr = float("inf")
 for (key,value) in _dictStats_.items():
 if min_fr &gt; value and key in _dictionary_:
 min_fr = value
 min_key = key
 
 else:
 _dictStats_[make_model] = _REL_INC
 if min_fr &gt; _dictStats_[make_model] and make_model in _dictionary_:
 min_fr = _REL_INC
 min_key = make_model
 
 for key in _dictStats_.keys():
 _dictStats_[key] = _dictStats_[key] * _DF
 min_fr = min_fr * _DF
 
 # Load/change the predictive model if required
 if not (make_model in _dictionary_): 
 if free_memory - 10 &gt; memory_limit:
 _dictionary_[make_model] = make_model
 free_memory -= 10
 if _dictStats_[make_model] &lt; min_fr:
 min_fr = _dictStats_[make_model]
 min_key = make_model
 else:
 if _dictStats_[make_model] &gt; _REL_COEFF*min_fr:
 del _dictionary_[min_key]
 _dictionary_[make_model] = make_model
 
 min_fr = float("inf")
 for (key,value) in _dictStats_.items():
 if min_fr &gt; value and key in _dictionary_:
 min_fr = value
 min_key = key

一种缓存预测模型的算法

此缓存策略非常轻量级：更新概率和查找需要替换的模型在模型数量上都是线性的。实施算法可以是很简单。然而，在合适的时间和地点，它可能非常有用！

一种缓存预测模型的算法

相关推荐