使用从统计信息中导出的特征来预测行为

摘要

本文中描述了用于生成依赖于具有缩减的维度的特征空间的预测模型的训练系统。训练系统通过产生分区来执行这个任务，分区中的每一个对应于方面值的子集(其中每个方面值进而可对应于一个或多个属性值)。训练系统接着产生与分区相关联的统计信息的实例。统计信息的每个实例因此对应于应用到多个方面值的特征信息，而非单个方面值的特征信息。训练系统接着基于特征信息来训练预测模型。本文中还描述了使用预测模型来在各种在线上下文中做出预测的预测模块。

说明书

背景

在线系统可针对各种用途来采用预测模型，诸如用于确定用户将点击某一 广告或选择搜索结果内的某一项之类的可能性。在线系统可由此基于其预测 来采取各种动作，诸如通过提供具有高点击概率的一个或多个广告或通过在搜 索结果内的显著位置中显示具有高点击概率的项。

在一种情况下，预测模型可通过标识描述一事件的特征集合来产生预测 (其中“事件”一般对应于其中预测被做出的环境)。这些特征整体上形成特 征向量。预测模块接着将特征向量映射到预测。一些特征对应于单个属性值 (诸如不同的用户ID、不同的广告ID等)，而其他特征对应于属性值的组合 (诸如用户ID和广告ID的不同组合)。在这种情况下，特征向量包括每个 个别属性值的特征以及属性值的每个组合；然而，特征向量将针对任意给定的 事件被稀疏地填充，意味着它在被用于描述任意特定事件时将仅包括少量的非 零特征。如可理解的，与以上描述的那种类型的预测模型相关联的特征空间 可具有非常高的维度。除了其他问题，以高效地方式来训练这种种类的预测 模型是困难的，尤其在其中预测模型本质上是复杂(例如，非线性)的那些情 况下。

概述

本文中描述了用于生成依赖于维度缩减的特征空间的预测模型的训练系 统。在一些实现中，训练系统通过基于分区策略产生复数个分区来操作。分 区与方面值的各个子集相关联。训练系统接着标识主数据集中关于相应复数 个分区的复数个数据子集，并生成针对相应数据子集的统计信息的复数个实 例。统计信息的复数个实例对应于反映数据子集中标记的分布的特征信息。 该功能接着基于特征信息来生成预测模型。

换言之，训练系统将统计信息的实例视为在训练模型时使用的特征。统 计信息的每个实例对应于复数个方面值(诸如复数个用户ID)的子集，而非单 个方面值(诸如单个用户ID)。相比于其中分开的特征被分派到各个方面值， 该策略可极大地缩减特征空间的维度。

根据另一说明性方面，训练系统可按导致预测准确性的最小丢失的方式来 分组方面值。

根据另一说明性方面，预测模块可使用通过使用训练系统产生的预测模型 来做出预测。

根据一潜在的益处，训练系统可以高效的方式来产生预测模型，主要是由 于其高维度特征空间到较低维度特征空间的映射。训练系统可通过产生复杂 的预测模型来充分利用这个高效性，其本来在使用高维度频率空间的预测模型 的情况中不可行。

上面的方法可以显现在各种类型的系统、组件，方法、计算机可读存储介 质、数据结构、图形用户界面呈现、制品等等中。

提供本概述以便以简化形式介绍一些概念；这些概念将在以下的详细描述 中进一步描述。本概述并不旨在标识所要求保护主题的关键特征或必要特征， 也不旨在用于限制所要求保护主题的范围。

附图简述

图1显示了用于产生并应用预测模型的方式的说明性概览，其中该预测模 型依赖于大小缩减的频率空间。

图2显示了用在图1的方式内的训练过程中的训练示例的主数据集的说明 性构成。

图3显示了通过图1的训练过程产生的说明性表格。

图4是根据图1中阐述的原理的可被用于产生分区的一个分区策略的高级 概念性描绘。

图5显示了用于实践图1的方法的一个环境。该环境包括训练系统和预 测模块。

相比于图5的示例而言，图6显示了用于实践图1的方法的更具体的环境。

图7和8示出由图5的训练系统提供的训练过程的说明性方面。

图9示出了图5的预测模块的一种实现。

图10是提供图5的环境的一种操作方式的概览的流程图。

图11是提供关于图5的训练系统的一种操作方式的附加细节的流程图。

图12是提供关于图5的预测模块的一种操作方式的附加细节的流程图。

图13示出了可以被用来实现前面的附图中所示出的特征的任何方面的说 明性计算功能。

贯穿本公开和各附图，相同的编号参考相同的组件和特征。100系列标号 指的是最初在图1中所找到的特征，200系列的标号指的是最初在图2中找到 的特征，300系列的标号指的是最初在图3中找到的特征，依此类推。

详细描述

本发明是按如下方式来组织的。章节A提供了用于产生和使用预测模型 的方法的概念概览。章节B描述了用于实现章节A的方法的说明性功能。章 节C阐述了解释章节B的功能的操作的说明性方法。章节D描述了可被用于 实现在前述章节中描述的特征的任意方面的说明性计算功能。

作为预备，一些附图在被不同地称为功能、模块、特征、元素等的一个或 多个结构组件的上下文中描述概念。附图中示出的各组件可以由任何物理和 有形的机制(例如，由计算机装备上运行的软件、硬件(例如芯片实现的逻辑 功能)等和/或以上的任意组合)以各种方式来实现。在一种情况下，附图中 所示出的将各种组件分离为不同的单元可以反映在实际实现中使用对应的不 同的物理和有形的组件。另选地或者另外地，附图中所示出的任何单个组件 都可以通过多个实际物理组件来实现。另选地或另外地，附图中的任何两个 或更多分开组件的描绘可以反映单个实际物理组件所执行的不同功能。图13 (将依次讨论)提供关于附图中所示的功能的一个说明性物理实现的附加细 节。

其他附图以流程图形式描述了概念。以此形式，某些操作被描述为构成 以某一顺序执行的不同的框。这些实现是说明性而非限制性的。此处描述的 某些框可被分组在一起并在单个操作中执行，某些框可被分成多个组件框，并 且某些框可以按与此处所示出的不同的次序来执行(包括以并行方式执行这些 框)。流程图中示出的框可以任何方式由任何物理和有形机制来实现，例如 由正在计算机装备上运行的软件、硬件(如芯片实现的逻辑功能)等和/或它们 的任何组合来实现。

至于术语，短语“被配置成”包含任何类型的物理和有形的功能可以被构建 来执行已标识的操作的任何方式。功能可以被配置成使用例如正在计算机装 备上运行的软件、硬件(例如，芯片实现的逻辑功能)等和/或其任何组合来执 行操作。

术语“逻辑”包含用于执行任务的任何物理和有形的功能。例如，流程图 中示出的每一个操作都对应于用于执行该操作的逻辑组件。操作可以使用例 如正在计算机装备上运行的软件、硬件(例如，芯片实现的逻辑功能)等和/ 或其任何组合来执行操作。在由计算装备实现时，逻辑组件表示作为计算系 统的物理部分的、无论如何实现的电子组件。

权利要求中的短语“用于...的装置”(如果被使用)旨在援引35U.S.C.§112 第六段的规定。除了本特定短语之外，没有其他语言旨在援引该法条的该部 分的规定。

下列的阐述可以将一个或多个特征标识为“可任选的”。这种类型的陈述 不应该被解读为可以被视为可选的特征的穷尽的指示；也就是说，其他特征也 可以被视为可选，虽然在文本中没有明确地标识。最后，术语“示例性”或“说 明性”指的是可能的许多实现中的一个实现。

A.用于训练和使用预测模型的说明性方法

图1显示了包括训练阶段102和模型应用阶段104的说明性方法。在训 练阶段102，训练系统(图1中未显示)生成预测模型106。在模型应用阶段 104，预测模型(图1中未显示)使用预测模型106来生成预测。本章节提供 了训练阶段102和模型应用阶段104的概念概览。之后的章节提供了关于这 两个组件的附加细节。

针对训练阶段102，数据收集过程108产生主数据集110。训练系统基于 主数据集110中的数据来生成预测模型106。不同的环境可使用不同种类的数 据收集过程来收集各个不同种类的数据。

例如，图2显示了存储一种种类的主数据集的数据存储202，该种种类的 主数据集由多个训练示例组成。每个训练示例描述一事件，诸如用户对点击 一对象或不点击一对象的决定，该对象诸如搜索结果内的广告或项。每个训 练示例由一个或多个方面值和标记组成。方面值描述事件的不同特征。标记 标识事件的任意类型的结果或评估。例如，标记可标识用户实际上是点击对 象还是拒绝点击对象。

更具体地，如在图2的概念分类树中概括的，一事件与各种变量相关联， 该各种变量在本文中被称为方面。例如，用户相关的方面关于与系统交互的 用户。例如，一个这样的用户相关的方面可标识该用户，另一方面可标识用 户的位置，另一方面可标识与用户的浏览器相关联的用户代理字符串等。内 容相关的方面关于被提供给用户的内容，或在预测时被考虑用于呈现给用户的 内容。例如，一个这样的内容相关的方面可标识广告或搜索结果项，另一方 面可标识广告客户，另一方面可标识广告的类别等。上下文相关的方面关于 向用户递送(或要递送)内容所处的上下文。例如，一个这样的上下文相关 的方面可描述用户提交的查询，另一这样的方面可描述一内容项相对于其他内 容项的定位等。这些方面是作为示例而非限制被引述的。

每个方面变量可采用不同方面值集。在一些情况下，一方面值进而可对 应于单个属性值。在其他情况下，一方面值可对应于两个或更多个属性值的 结合。例如，考虑与用户身份相关联的方面(例如，存储在浏览器cookie中 的用户ID)。在这种情况下，每个方面值映射到单个属性值，即具体的用户 身份。接着考虑与用户身份和广告身份的组合相关联的方面。在这种情况下， 每个方面值映射到具体用户身份和具体广告身份的组合。换言之，在这个后 一种情况下，方面值具有两个分量，与用户身份相关联的第一分量以及与广告 身份相关联的第二分量。如可仅由这个简化的示例所理解的，可能的方面值 的域是非常大的，潜在地可能具有数百万或甚至更大的数量级。

返回到图1，分区过程122为每个考虑中的方面产生多个分区(也称为箱 (bin))。每个分区与一个方面值集相关联。例如，假设分区过程112产生 与用户身份方面相关联的分区。第一分区可与用户身份值的第一子集相关联， 第二分组可与用户身份值的第二子集相关联，以此类推。分区过程112对其 他方面执行类似的分区过程，该其他方面包括与单个属性相关联的方面以及与 属性的组合(诸如用户身份和广告身份)相关联的方面两者。

接着，在过滤和聚集过程114，训练系统标识选自主数据集110的针对各 个不同的分区的复数个数据子集。训练系统接着基于相应分区的相应数据子 集来形成统计信息的复数个实例。例如，考虑其中第一分区与特定的用户身 份集相关联的情况。训练系统可在主数据集110中提取关于该用户身份集的 训练示例的那个子集。这构成针对这个分区的数据子集。训练系统可由此基 于在该数据子集中提供的信息来形成统计信息。

更具体地，不同的实现可生成不同种类的统计测量。在一个情况下，训 练系统可形成与训练示例相关联的标记值的计数。考虑其中分区对应于一组 用户身份的以上示例。训练系统可基于所标识的组内用户执行点击的次数来 形式第一计数，基于所标识的组内用户在给予机会点击时拒绝点击的次数来形 成第二计数。统计信息还可包括各个平均值、比例等。统计信息还可包括表 示预测模块的输出的信息。例如，除了用户对点击或不点击对象的实际决定 之外，预测模块可已经生成了关于用户是否会点击或不点击对象的预测。统 计信息可提供基于这些预测的值的一个或多个统计测量。

更一般而言，术语“统计”在本文中被广泛地用于指代可从一个或多个训练 示例和/或一个或多个预测中得到的任意信息。统计信息的不同实例共同构成 特征信息。特征信息内的各个统计测量构成特征。例如，特定分区内点击事 件的次数的计数构成特征信息中的一个特征。统计信息在其反映标记的分布 (诸如点击事件或不点击事件的分布)的程度上可一般地被视为以标记为条件 的。

训练系统可使用多个表格或其他类型的查找数据结构来制定其结果。暂 时前进到图3，该图示出了三个这样的表格。每个表格与一特定方面相关联， 其中该方面可涉及单个属性(诸如用户身份)或属性的组合(诸如用户身份和 广告身份)。每个表格包括与不同分区相关联的复数个条目。每个分区进而 提供针对该分区生成的统计信息，该统计信息可包括对应于特征的一个或多个 统计测量。

例如，考虑与用户身份相关联的最顶端的表格。该表格可包括提供针对 第一组用户身份的统计信息的第一分区(即，箱A)，提供针对第二组用户身 份的统计信息的第二分区(即，箱B)，以此类推。任何表格还可任选地包括 兜底“垃圾”分区。即，对于用户身份表格而言，垃圾分区可存储关于所有没有 落入任何其他分区(诸如箱A、B、C等)中的用户身份的统计信息。

在另一实现中，训练系统可将一些方面值映射到表格内的两个或更多个分 区。例如，训练系统可提供分区的分层结构(例如，树)，其中子分区可被 视为被包含在更一般的分区内。在这种情况下，训练系统可将一方面值映射 到具体分区以及其更广泛的父分区两者。如果方面值不属于任何一个具体分 区，则训练系统可将其仅仅映射到一般的兜底分区。与属于两个或更多个分 区的一方面值相关联的特征可反映与这些分区相关联的统计信息的任意种类 的组合。依然其他策略可能用于结构化分区集以及用于将方面值映射到这些 分区。

参考图1，在模型训练过程116中，训练系统接下来基于训练示例集以及 由训练系统生成的特征信息来产生预测模型106。例如，训练系统可使用被包 括在主数据集110内的训练示例的第一集合来生成特征信息。训练系统可由 此使用主数据集110中训练示例的扣留的集合以及特征信息来产生预测模型 106。

在操作中，训练系统将扣留的数据集中的每个训练示例映射到一个或多个 方面值。训练系统接着例如使用图3中显示的表格中的一个或多个来确定与 方面值相关联的特征信息。训练系统接着使用训练技术来基于特征信息以及 与训练示例相关联的标记来生成预测模型106。任意机器学习过程可被用于执 行这个任务。在一种情况下，模型训练过程116的结果是部分地定义预测模 型106的权重、参数等的集合。

在模型应用阶段104，预测模型106被用于配置预测模块(图1中未显示)； 预测模块进而被部署在任意目标系统中。例如，在搜索相关的上下文中，预 测模块可被部署为搜索引擎系统的一部分。在广告相关的上下文中，预测模 块可被部署为广告服务器系统的一部分，以此类推。

在操作中，预测模块接收描述在线事件的输入信息。例如，输入信息可 指示用户访问了包括用于呈现广告的一个或多个空位的页面。或者，输入信 息可指示用户提交了特定查询等。预测模块标识与事件相关联的方面值，诸 如用户的身份、可被呈现给用户的特定候选广告的身份等。预测模块接着查 阅图3中显示的表格中的一个或多个以标识与所标识的方面值相关联的特征信 息。预测模块接着基于所标识的特征信息来生成预测。

如图1上的一般性注释，注意，训练系统将多个方面值集映射到特定特征， 而非将个别方面值映射到特定特征。凭借这个方法，相比于其中每个方面值 被分配其自己的特征的情况，训练系统可极大地缩减特征空间的维度。这允 许训练系统以高效的方式来执行训练阶段102。作为相关的益处，管理员可充 分利用训练系统的效率来构造本质上相对复杂(例如，非线性)的预测模型。

训练系统可使用不同的分区策略来定义分区。在一个方式中，训练系统 可按满足与预测准确性的丢失有关的目标的方式来定义分区。例如，训练系 统可按最小化预测准确性的丢失、或至少确保预测准确性的丢失低于规定的阈 值的方式来产生分区。预测准确性指统计信息准确地表示与对统计信息做出 贡献的各个训练示例相关联的标记的程度。

图4示出以上描述的分区策略的高级概念描述。在这个示例中，训练系 统产生方面值的群集，其中每个群集中的方面值展现类似的以标记为条件的统 计简档。例如，训练系统可标识与不同的各个用户ID相关联的点进率。训 练系统可由此形成具有类似的点进率的用户ID的群集。此外，训练系统使用 统计信息的单个实例来表示群集的所有成员。图4将单个实例表示为黑点。注 意，这个“黑点实例”可以或可以不对应于其群集的实际成员。训练系统通过以 统计信息的实例准确地表征相应群集中的成员的方式执行群集，同时整体上最 小化关于群集的具体成员的描述性信息的丢失来最小化预测准确性的丢失。

在其他实现中，训练系统可使用其他分区策略来产生分区。在一个替代 技术中，训练系统可基于频率测量来分组方面值。例如，训练系统可以评估 每个方面值在主数据集110内出现的频率。训练系统可由此将具有类似频率 值的方面值分组在一起。

在另一情况下，训练系统可使用散列技术来分组方面值。例如，训练系 统可将不同的分区与不同的散列桶相关联。训练系统可由此应用散列函数来 将特定方面值路由到散列桶中的至少一个。

在另一情况下，训练系统可使用截断策略来分组方面值。例如，训练系 统可使用IP地址的一个或多个字节来将IP相关的方面值路由到多个分区中的 一个。(注意，这个操作可被认为是特定种类的散列)。

在另一情况下，训练系统可基于共享的方面值来分组方面值。例如，训 练系统可确保特定分区中的所有条目具有至少一个公共方面值(诸如特定用户 ID)。

训练系统还可使用其他类型的分区策略来定义分区。上述示例是作为示 例而非限制被引述的。

B.用于实现该方法的说明性功能

图5显示了用于实现图1的方法的一个环境502。环境502包括用于执行 图1的训练阶段102的训练系统504以及用于执行图1的模型应用阶段104的 预测模块506。

环境502还包括用于提供收集的数据并将其存储在数据存储510中的数据 收集模块508。数据收集模块508可表示与任意其他系统功能集成的功能；在 这种情况下，数据收集模块508执行补充该其他系统功能所提供的服务的操作。 例如，在搜索引擎系统的上下文中，数据收集模块508可创建反映用户查询、 点击动作、不点击动作、IP地址、位置等的日志。如果被授权，则数据收集 模块508还可存储关于提交查询的用户的人口统计信息，并将该信息与用户采 取的动作相关。这样的人口统计信息可由用户提供和/或从其他源获得。数据 收集模块508还可存储关于可被递送到用户的内容项的信息。这些内容项可 对应于文档、网页、广告等。

图5还指示环境502可存储关于预测模块506做出的预测的信息。例如， 预测模块506可提供特定用户有可能点击特定广告的预测。作为响应，广告 服务系统可将该广告呈现给用户。用户将要么忽略该广告要么点击该广告。 环境502将存储用户关于该广告的实际动作以及预测模块的关于用户的可能动 作的预测两者。

作为以上数据收集过程的结果，数据存储510存储章节A中描述的主数据 集110。在正式的术语中，主数据集110可表示空间(X，Y)，其中X指与训 练示例相关联的方面值的有限集，而Y指与训练示例的标记相关联的值的二进 制集[0，1]。符号x_i指空间X内的单个方面值，而符号y_i指单个标记值。

训练系统504可包括(或被概念化为包括)执行不同功能的不同模块。分 区定义模块512定义要被用于形成统计信息的实例的分区的数量。在一个情 况下，分区定义模块512选择固定数量的分区，m。在其他情况下，分区定义 模块512可基于一个或多个因素来以动态方式定义分区的数量。

分区定义模块512接着定义其中方面值将被映射到不同的各个分区的方 式。如在章节A中提到的，在一个方法中，分区定义模块512以以下方式指 定方面值和分区之间的映射：最小化预测准确性的丢失或实现就预测准确性的 丢失所指定的某个其他目标。

在正式的术语中，分区定义模块512尝试将与各个方面值相关联的空间X 压缩为更小的空间T，同时尽可能多地捕捉关于Y的信息。在此假设空间T 由M个比特来索引，并由此包括m个分区，例如m＝|T|＝2^M。硬分区函数 T＝T(x)定义其中空间T被分解成不同的分区的方式。符号t指空间T内的单 个分区。

为了导出函数T(x)，首先考虑T中关于Y的信息的量可被表示为：

$\left(\begin{array}{c}I(Y;T)=E_{t,y}\ln \frac{p\left(y\right|t)}{p\left(y\right)}=\underset{t}{\Sigma }p\left(t\right)\left(\underset{y\in \{0,1\}}{\Sigma }p\right(y|t\left)\ln \frac{p\left(y\right|t)}{p\left(y\right)}\right)\\ =\underset{t}{\Sigma }p\left(t\right)\left(\underset{y\in \{0,1\}}{\Sigma }\frac{{\Sigma }_{x:T\left(x\right)-t}p\left(x\right)p\left(y\right|x)}{p\left(t\right)}\ln \frac{p\left(y\right|t)}{p\left(y\right)}\right)\\ =\underset{x}{\Sigma }p\left(x\right)\left(\underset{y\in \{0,1\}}{\Sigma }p\right(y|x\left)\ln \frac{p\left(y\right|T\left(x\right))}{p\left(y\right)}\right)\\ =\underset{x}{\Sigma }p\left(x\right)\left(\underset{y\in \{0,1\}}{\Sigma }p\right(y|x\left)\right(\ln \frac{p\left(y\right|x)}{p\left(y\right)}-\ln \frac{p\left(y\right|n)}{p\left(y\right|T\left(x\right))}\left)\right)\\ =E_{x,y}\ln \frac{p\left(y\right|x)}{p\left(y\right)}-=\underset{x}{\Sigma }p\left(x\right)\underset{y\in \{0,1\}}{\Sigma }p\left(y\right|x)\ln \frac{p\left(y\right|x)}{p\left(y\right|T\left(x\right))}\\ =I(X;Y)=\underset{x}{\Sigma }p\left(x\right)D_{KL}\left(p\right(y|x\left)\right|\left|p\right(y|T\left(x\right)\left)\right)\end{array}\right)$

一般而言，D_KL(P||Q))指具有参数P和Q的两个伯努利(Bernoulli)分布 之间的Kullback-Leibler散度测量。符号E是期望值算子。p(a)指某个事件具 有值a的概率，而p(a|b)指在给定b的情况下某个事件具有值a的概率。

以上推导指示针对分区函数T(x)的信息丢失的量等于 ∑_xp(x)D_KL(p(y|x)||p(y)|T(x)))。Y和X之间的交互信息的量是恒定的。由此， 为了最大化Y和T之间的交互信息，分区定义模块512可最小化针对分区函数 T(x)的信息丢失的量。该最小化任务可被表达为：

$T^{*}\underset{t}{\arg \min }\underset{x}{\Sigma }p\left(x\right)D_{KL}\left(p\right(y|x\left)\right|\left|p\right(y|T\left(x\right)\left)\right)$

当针对x的不同值的分区可被独立地选择时，用于选择针对方面值x的最 合适的分区的准则可被表示为：

$T^{*}\left(x\right)=\underset{t}{\arg \min }{D}_{KL}\left(p\right(y|x\left)\right|\left|p\right(y|t\left)\right)$

为了提供以上等式的一个应用的具体示例，考虑其中点进率CTR_x与每个 方面值x相关联的说明性情况。分区定义模块512可通过根据所有值x的CTR_x对所有值x进行排序来应用以上等式。分区定义模块512可由此形成具有类似 点进率的方面值的群集，其中使用KL散度来测量任意两个点进率之间的距离。 这构建了初始的分区分组以及方面值和分区之间的映射。

在预测模型被部署后，假设遇到未被初始训练示例集表示的新的方面值x。 分区定义模块512可使用以上等式来将新的方面值映射到满足以上所述的 argmin等式的分区中，如在T*(x)＝argmin_tD_KL(CTR_x||CTR_t)中，其中CTR_t指 与整个候选分区t相关联的点进率。如将在以下解释的，分区定义模块512还 可周期性地重新计算整个映射函数T(x)以将在预测模型的部署之后被收集的新 的数据考虑在内。

以上等式是在以下假设的情况下被预测的：预测模块506仅将从方面值中 导出的与方面空间X相关联的特征考虑在内。在另一情况下，预测模块506 还可将除了X之外的事件的某些特征考虑在内。令随机变量Z指所有这样的其 他特征。在一些情况下，Z可仅表示一个特征，诸如用户的性别等。在其他 情况下，Z可表示所有其他特征的某个聚集。

一种概括这些其他特征的贡献的方式是通过将Z设置为等于预测模块506 的输出；该输出进而将其他特征考虑在内，如所表示的。在 此假设，域Z是离散的并具有有限的基数。在其中预测模块506的输出是连 续的那些情况下，分区定义模块512可以适当的方式来离散化该输出。

目标依然是将空间X压缩到具有m个分区的更小的空间T，同时尽可能多 地捕捉Y中的信息。现在将变量Z的贡献考虑在内，T中关于Y的信息的量 可以有条件的方式被表示为如下：

$\left(\begin{array}{c}I\left(Y\right|T;Z)=E_{t,y,z}\ln \frac{p\left(y\right|t,z)}{p\left(y\right|z)}=\underset{t,z}{\Sigma }p(t,z)\left(\underset{y\in (0,1)}{\Sigma }p\right(y|t,z\left)\ln \frac{p\left(y\right|t,z)}{p\left(y\right|z)}\right)\\ =I(X;Y|Z)-\underset{x,z}{\Sigma }p(x,z)D_{KL}\left(p\right(y|x,z\left)\right|\left|p\right(y|T\left(x\right),z\left)\right)\end{array}\right)$

考虑I(X；Y|Z)所表示的交互信息是恒定的，分区定义模块512可将最优分区 函数表示为如下：

$T^{*}=\underset{T}{\arg \min }\underset{x,z}{\Sigma }p(x,z)D_{KL}\left(p\right(y|x,z\left)\right|\left|p\right(y|T\left(x\right),z\left)\right)$

当针对x的不同值的分区可被独立地选择时，用于选择针对方面值x的最 合适的分区的准则可被表示为：

$T^{*}\left(x\right)=\underset{t}{\arg \min }\underset{z}{\Sigma }p\left(z\right|x)D_{KL}\left(p\right(y|x,z\left)\right|\left|p\right(y|t,z\left)\right)$

在其他情况下，分区定义模块512可使用其他分区策略来定义分区的数量 以及定义方面值到特定分区的映射。例如，如在章节A中描述的，分区定义 模块512可替换地使用频率测量来例如通过将具有类似频率测量的方面值分组 来将方面值映射到分区。在另一情况下，分区定义模块512可使用散列或截 断策略来将方面值映射到分区。在另一情况下，分区定义模块512可尝试将 方面值映射到分区，使得至少一个分区包括一个或多个公共方面值。这些选 项是作为示例而非限制被引述的。这些替代技术无需以以上描述的方式来最 小化预测准确性的丢失。

作为其处理的结果，分区定义模块512产生映射函数M，其将不同的方面 值映射到与例如在M(X)→k₁，k₂，....，k_n中的各个分区相关联的索引k。例如， 在一个实现中，映射函数可将每个方面值映射到单个索引值；该单个索引值进 而标识合适表格内的分区。在另一实现中，映射函数可将每个方面值映射到 与表格相关联的两个或更多个分区。这后一选项在其中分区以分层结构的方 式被结构化的情况下是适当的。

聚集模块514为每个分区标识主数据集110内的数据子集；该子集匹配通 过分区定义模块512指定的准则。聚集模块514接着基于该数据子集来形成 该分区的统计信息。如在章节A中描述的，聚集模块514可形成不同的统计 值。例如，聚集模块514可形成所考虑的方面值x的点击事件的次数的计数以及不点击事件的次数的计数聚集模块514还可形成各个其他统计测量， 诸如归一化计数、平均值、标准偏差、点进率、其他比例(例如，等。聚集模块514还可将统计分布表示为混合模型，诸如高斯混合模型。聚 集模块514可由此提供表示该混合模型的组件的参数的特征。聚集模块514 还可基于预测模块506所做的预测，而非用户所采取的实际动作，来形成统计 测量。

在初始训练后，聚集模块514可随着新数据被收集来更新统计信息的实例。 更正式地说，在特定时间，每个分区t具有以标记为条件的概率q_t＝p(y＝1|t)。 聚集模块514可以二阶段方法来更新分区。在第一阶段期间，聚集模块514 可将方面值与特定分区相关联。在第二阶段期间，聚集模块514可根据 q_t＝p(y＝1|t)＝∑_x：T(x)＝tp(x)p(y＝1|x)来更新分区的值q_t。这个算法具有基 于方面值的概率分布p(y|x)来聚合地群集方面值的效果。

更具体地，聚集模块514可基于以下表达式来执行它的聚集操作：

T(k)→A(V(M(x_i)，y_i，f(x_i)，[extraData(额外数据)]))函数V(...)表示一 方面值到特定分区内的特定统计测量的映射，其中函数M(x_i)标识该分区的索 引。该表达式指示统计测量可基于y_i、f(x_i)和extraData(额外数据)中的任 意一个来更新。符号y_i表示与训练示例相关联的标记，例如，用户是点击了还 是没有点击指定对象。符号f(x_i)指基于x_i的任何任意函数，例如，修改对应的 y_i的贡献的一个任意函数。例如，f(x_i)可指基于一项在搜索结果内的位置来对 y_i的贡献打折的权重(其中y_i反映用户点击了该项还是没有点击该项)。符号 extraData(额外数据)指的是也可能影响聚集的补充信息。例如，extraData 可对应于预测模块506做出的预测。外围函数A(...)指定聚集模块514所执行 的聚集操作。

例如，考虑其中聚集模块514使用以上表达式来更新与用户ID方面相关 联的表格的情况。聚集模块514可使用以上表达式来更新与点击事件相关联 的第一统计测量以及与不点击事件相关联的第二统计测量：

$A\left(V\right(M\left(x_i\right),y_i,f\left(x_i\right)\left)\right)=\left[\underset{(x_i,y_i):y_i=1}{\Sigma }f\left(x_i\right)\underset{(x_i,y_i):y_i=0}{\Sigma }f\left(x_i\right)\right]$

即，这个表达式中的第一项生成点击事件的计数，而这个表达式中的第二 项生成不点击事件的计数。函数f(x_i)根据用户所点击(或没有点击)的对象 的位置来对计数的每个贡献进行打折。

模型生成模块516基于聚集模块514所提供的特征信息以及扣留的训练示 例集来产生预测模型518。模型生成模块516可使用任意机器学习技术来执行 这个任务。

预测模块506接着在预测模型518被部署后使用预测模型518来做出预测。 可使用任意机器学习技术来实现预测模块506，任意机器学习技术诸如决策树、 神经网络、支持向量机之类的集合。模型生成模块516执行的训练可按对正 被环境502使用的无论什么类型的预测模块506而言适当的方式来定制。

数据存储520可存储训练系统504所产生的各个信息。该信息可包括分 区定义模块512所提供的将方面值映射到分区的映射函数T(x)。所存储的信息 还可包括聚集模块514所提供的特征信息。所存储的信息还可包括定义模型 生成模块516所产生的预测模型518的任何信息。例如，在一些实现中，数 据存储520存储定义预测模型518的各个权重、参数等。

最终，图5示出环境502可使用任意并行处理资源522来实现训练系统504 的任意方面。例如，环境502可使用并行处理资源522来执行聚集模块514 的操作，其需要标识映射到分区的数据并接着将被映射的数据累积到各个统计 测量中。在一个实现中，例如，不同的处理资源可针对不同的各个分区来执 行聚集模块514的功能。此外，在一些实现中，不同的处理资源还可被用于 针对任意单个分区来执行聚集模块514的功能，从而进一步加速针对这个分区 所执行的操作。

并行处理资源522可被实现为复数个处理器模块和相关联的数据存储。可 使用CPU驱动的(和/或GPU驱动的)计算设备来实现处理器模块。替代地 或附加地，可通过硬连线的逻辑组件来实现处理器模块。

相比于图5的示例而言，图6显示了用于实践图1的方法的更具体的环境 602。在这个环境602中，用户可与任何类型的用户设备交互以经由通信机制 606(诸如广域网(例如，因特网))与各种各样的在线系统604通信。系统 604可向用户提供任意相应的服务。例如，一个系统可提供搜索引擎服务。另 一系统可提供广告服务器服务，以此类推。

每个系统可采用在它提供的服务的上下文中预测用户行为的预测模块。 例如，代表性系统608提供预测模块610。例如，搜索引擎系统可提供预测模 块来评估用户将点击搜索结果内的某个项的可能性。搜索引擎系统可基于这 个预测来执行各种动作，诸如通过基于该预测来选择搜索结果内该项的位置例 如以更突出地显示特定用户可能感兴趣的项。

数据收集模块612、数据存储614和训练系统616可执行与以上针对图5 描述的被相同命名的组件相同的功能。在图6的上下文中，数据收集模块612、 数据存储614和训练系统616中的任意一个可被集成到它们进行服务的(诸) 系统中，诸如搜索引擎系统。替代地或附加地，这些组件中的一些可通过与 它们进行服务的(诸)系统分开的计算装置来实现。例如，训练系统616可 被实现为向两个或更多个系统提供训练相关的服务并独立于这些系统的组件。

就物理实现而言，任意用户设备可被任意类型的计算设备来实现，该任意 类型的计算设备诸如个人计算机、计算机工作站、膝上型计算机、平板类型的 计算机、智能电话或其他类型的蜂窝式电话、游戏控制台设备、机顶盒设备等。 系统604、数据收集模块612和训练系统616中的每一个可被实现为与一个或 多个数据存储相关联的一个或多个服务器。任何这样的组件的功能可被实现 在单个站点处或可跨多个站点来分布。

图7和8示出由图5的训练系统504提供的训练过程的说明性方面。参 考图1，训练包含在训练阶段102被执行的初始训练以及在模型应用阶段104 期间发生的动态训练。

参考图7，训练系统504可使用主数据集110的一部分来定义分区并生成 统计信息。训练系统504可由此使用主数据集110的另一部分(被称为扣留 的数据集702)来训练预测模型518。在这种情况下，对于扣留的数据集702 中的每个训练示例，训练需要标识与这个训练示例相关联的(诸)方面值并接 着标识与(诸)方面值相关联的特征信息。这提供了(诸)方面值、特征信 息以及标记之间的一个示例性关联。模型生成模块516基于以以上描述的方 式所产生的训练实例的集合来训练预测模型518。

训练系统504使用在预测模型518的部署之后被收集的部署后数据704来 更新预测模型518。这进一步的训练可构成响应于在预测模型518的部署之后 发生的用户点击事件(和不点击事件)来更新分区所提供的统计信息。例如， 考虑在初始训练过程中遇到方面值的情况；其中，训练系统504可将与这个方 面值的新出现相关联的数据路由到适当的分区，并接着基于该新的数据来更新 针对这个分区的统计。即，新的数据对应于关于方面值以及随后获得的标记 (例如，点击或不点击事件)的信息。在另一情况下，假设新遇到的方面值 在初始训练阶段102期间未被观察到。在此，训练系统504使用分区定义模 块512来确定用于放置该新的方面值的最适当的分区。训练系统504接着基 于与该新的方面值的出现相关联的数据来更新针对该分区的统计信息。

此外，训练系统504可周期性地重新估计其用于将方面值映射到不同分区 的整个策略。这个规定有助于解决其中与方面值相关联的以标记为条件的统 计信息随着时间(例如，基于底层用户行为和/或其他因素的改变)改变的情况。

图8从时间角度概括了以上对训练过程的解释。初始训练阶段102包括 第一训练时间段(Count_train(计数_训练))，在该第一训练时间段中，训练系统 504定义分区映射策略并生成统计信息的实例。初始训练阶段102包括用于基 于在时间段Count_train中习得的特征来训练预测模型518的第二训练时间段 (Train(训练))。在部署后，在模型应用阶段104，训练系统504继续以 以上描述的方式来更新预测模型518。

图9示出了图5的预测模块506的一种实现。预测模块506包括存储一 个或多个表格904(诸如图3中显示的那种种类的表格)的数据存储902。每 个这样的表格指定与一方面相关联的分区集。该方面可对应于单个属性(诸 如用户ID)或属性的组合(诸如用户ID和广告ID)。每个分区提供由训练 系统504提供的统计信息。该统计信息提供在执行预测时使用的特征。第二 数据存储906可存储由模型生成模块516生成的任何信息(例如，权重、参数 等)。总体而言，在数据存储902和906中提供的信息构成预测模型518。

特征查找模块908在适合于生成预测时接收输入信息。例如，特征查找 模块908可在用户向搜索引擎系统提交搜索查询时接收输入信息；在这种情况 下，搜索引擎系统将调用预测模块506来确定用户将点击多个候选搜索结果项 中的每一个的概率。

在第一个操作中，特征查找模块908可确定与所考虑的事件相关联的所有 方面值，例如，在以上的示例中对应于其中用户向搜索引擎系统提交了查询的 情况。特征查找模块908接着将(诸)方面值用作查找在表格904中提供的 对应特征的键。这产生了特征信息。

预测生成模块910接着将特征信息作为输入馈送到其预测功能中以产生输 出预测。在搜索引擎系统的情况下，预测可针对每个候选搜索结果项指示用 户将点击这个项的概率。例如，假设预测模型518被实现为神经网络。预测 生成模块910可将特征信息中的特征作为输入向量馈送到神经网络的输入层 中。神经网络生成指示与这个输入向量相关联的概率的范围从0到1的值。

动作采取模块912基于预测生成模块910生成的预测来采取以上描述的任 何种类的动作。动作采取模块912可被预测模块506被部署在其中的系统中 的任意组件(诸如被搜索引擎系统或广告服务系统内的组件)实现。

C.说明性过程

图10-12示出解释图1的环境502的一个操作方式的规程。由于在章节B 中已经描述了环境502的操作之下的原理，在此章节将以概述的方式提出某些 操作。图5和9也用置于椭圆内的对应于以下描述的操作的附图标记所注释。

从图10开始，图10示出表示图5的环境502的一种操作方式的概览的过 程1002。在框1004中，数据收集模块508收集初始训练数据以提供存储在数 据存储510中的主数据集110。在框1006中，训练系统504基于主数据集110 来生成预测模型518。预测模型518提供对应于各个分区的统计信息的复数个 实例。在一个实现中，训练系统504可在一个或多个表格(诸如在图3中显 示的那种种类的表格)中表示统计信息(其整体上构成特征信息)。在框1008 中，环境502部署预测模型518并使用其来生成预测。在框1010中，数据收 集模块508基于部署后事件来收集附加数据。反馈循环指示训练系统504可 使用部署后数据来执行进一步的训练，从而产生经更新的预测模型518。

图11示出提供关于图5的训练系统504的一种操作方式的附加细节的过 程1102。在框1104中，训练系统504接收主数据集110。在框1106中，分 区定义模块512基于分区策略来产生分区。在章节B中解释的一个示例中， 分区定义模块512以最小化与标记Y相关联的预测准确性的丢失的方式来形成 分区。

在框1108中，聚集模块514基于框1106中定义的映射函数来标识数据子 集。在框1110中，聚集模块514504生成在框1108中标识的各个数据子集的 统计信息的实例；该信息整体上构成特征信息。更具体地，框1108和1110 在本文中不受限制地解释。在第一实现中，聚集模块514可生成包括复数个 数据项的数据子集，并接着生成这个完整数据子集的统计信息。在另一情况 中，聚集模块514可标识单个数据项并接着基于这个单个项来更新统计信息， 并接着针对数据子集中的所有其他数据项来连续地重复这个相同的二阶段过 程。如还在章节B中解释的，聚集模块514504可通过使用任意并行处理资源 522来执行框1108和1110以加快这些操作。

在框1112中，针对扣留的数据集702中的训练示例，模型生成模块516 基于在框1110中计算的特征信息来生成预测模型518。在框1114中，模型生 成模块516可将预测模型518存储在数据存储520中。环境502还可使用预 测模型518来自动地配置预测模块506。

图12示出提供关于图5的预测模块506的一种操作方式的附加细节的过 程1202。在框1204，预测模块506接收与新事件相关联的输入信息，诸如做 出关于用户是否将点击在线环境中的特定对象的预测的新的机会。在框1206 中，特征查找模块908标识与输入信息相关联的一个或多个方面值。在框1208 中，特征查找模块908执行查找操作来确定与所标识的(诸)方面值相关联的 统计信息。该统计信息构成特征集。在框1210中，预测生成模块910基于 所标识的特征来生成预测。在框1212中，动作采取模块912可基于框1210 中的预测来执行任意(诸)专用于应用的动作。例如，动作采取模块912可 基于框1210中做出的结论来做出关于哪些广告要显示给用户的决定。或者， 动作采取模块912可基于框1210中做出的结论来确定项在页面中的位置，等。

作为总结评论，以上示例描述了其中标记与点击(或不点击事件)相关联 的情况。但更广泛地来说，标记可指与方面值集相关联的任意评估、结论或 结果。此外，图5中示出的环境502可被应用到除了图6的那种类型的服务 驱动的在线环境602之外的其他环境，包括各种离线环境。例如，环境502 可被用于处理任意类型的科学数据、任意类型的业务相关数据等。例如，在 业务相关环境中，不同的分区可与金融资产(例如，股票)的不同分组相关联。

D.代表性计算功能

图13显示了可以被用来实现上文所描述的功能的任何方面的说明性计算 功能1300。例如，图13中所示类型的计算功能1300可被用于实现图5、6和 9中所示的任何组件。在一种情况下，计算功能1300可对应于包括一个或多 个处理设备的任何类型的计算设备。在所有情形中，计算功能1300表示一个 或多个物理且有形的处理机制。

计算功能1300可包括诸如RAM1302和ROM1304之类的易失性和非易 失性存储器，以及一个或多个处理设备1306(例如，一个或多个CPU，和/或 一个或多个GPU等等)。计算功能1300还可任选地包括诸如硬盘模块、光 盘模块等等之类的各种介质设备1308。当处理设备1306执行由存储器(例如， RAM1302、ROM1304或其他)维护的指令时，计算功能1300可以执行上文 所标识的各种操作。

更一般地，指令和其它信息可以被存储在任何计算机可读介质1310上， 计算机可读介质包括但不限于静态存储器存储设备、磁存储设备、光存储设备 等。术语计算机可读介质还涵盖多个存储设备。在多种情况下，计算机可读 介质1310都表示某种形式的物理和有形的实体。术语计算机可读介质还包括 传播信号，例如经由物理管道和/或空气或其他无线介质等来传送或接收的。然 而，特定术语“计算可读存储介质”和“计算机可读介质设备”明确地排除传播信 号本身，但是包括所有其他形式的计算机可读介质。

计算功能1300还包括用于(通过输入设备1314)接收各种输入，以及用 于(通过输出设备)提供各种输出的输入/输出模块1312。说明性的输入设备 包括键盘设备、鼠标输入设备、触摸屏输入设备、数字化垫、一个或多个相机、 语音识别机制、任何移动检测机制(例如，加速计、陀螺仪等)等。一种特定 输出机制可包括呈现设备1316及相关联的图形用户界面(GUI)1318。计算 功能1300还可以包括用于通过一个或多个通信管道1322与其他设备交换数据 的一个或多个网络接口1320。一条或多条通信总线1324将上述组件通信地耦 合在一起。

通信管道(一个或多个)1322可以以任何方式来实现，例如，通过局域网、 广域网(例如，因特网)等等，或其任何组合。(诸)通信管道1322可包括 可由任何协议或协议的组合管理的硬连线的链路、无线链路、路由器、网关功 能、名称服务器等等的任何组合。

作为替代或除此之外，前述各节中所述的任何功能可至少部分地由一个或 多个硬件逻辑组件来执行。作为示例而非限制，计算功能可使用以下的一个 或多个来实现：现场可编程门阵列(FPGA)；专用集成电路(ASIC)；专用 标准产品(ASSP)；片上系统(SOC)；复杂可编程逻辑器件(CPLD)等等。

作为结束语，本文所述的功能可采用各种机制来确保功能所维护的用户数 据的私密性。例如，该功能可允许用户明确地选择进入(以及明确地选择退 出)功能的供应。功能还可提供适用的安全机制来确保用户数据的私密性(如 数据净化机制、加密机制、口令保护机制等)。

此外，说明书在说明性挑战或问题的上下文中描述了各种概念。这种说 明方式不构成其他人以此处所指定的方式理解和/或明确表达挑战或问题的许 可。此外，所要求保护的主题也不仅限于解决提到的挑战/问题中的任意或全 部的实现。

尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所 附权利要求书中定义的主题不必限于上述具体特征或动作。更确切而言，上 述具体特征和动作是作为实现权利要求的示例形式公开的。