搜广推校招面经四十九
tiktok广告算法
一、倒排索引原理及Map中Key的处理
具体使用方法见【搜广推校招面经三十六】
倒排索引(Inverted Index)是信息检索系统中常用的一种数据结构,用于快速查找包含某个关键词的文档。以下是倒排索引的原理及Map中Key的处理方式的详细说明。
1.1. 倒排索引的原理
(1) 基本概念
- 正排索引:以文档为单位,记录每个文档包含的关键词。
- 倒排索引:以关键词为单位,记录每个关键词出现在哪些文档中。
(2) 数据结构
倒排索引通常由两部分组成:
- 词典(Dictionary):存储所有关键词。
- 倒排列表(Posting List):记录每个关键词对应的文档列表及其相关信息(如词频、位置等)。
2. Map中Key的处理
在实现倒排索引时,通常使用Map(或字典)来存储词典和倒排列表。以下是Map中Key的处理方式:
(1) Key的选择
- Key:关键词(Term)。
- Value:倒排列表(Posting List),通常是一个列表或数组,存储文档ID及其相关信息。
(2) Key的存储
- 哈希表:使用哈希表(如Python的
dict
或Java的HashMap
)存储Key-Value对,确保快速查找。 - 排序存储:将Key按字典序排序,便于范围查询和前缀匹配。
(3) Key的冲突处理
- 哈希冲突:当两个不同的Key映射到同一个哈希值时,使用链地址法或开放地址法解决冲突。
- 重复Key:在倒排索引中,Key是唯一的,不会出现重复。
二、Transformer的结构、原理、优点、除 d k \sqrt{d_k} dk、手写自注意力机制一套。
见【搜广推校招面经三十四、搜广推校招面经二】
三、MMoE与PLE的计算方式及区别
MMoE(Multi-gate Mixture of Experts)和PLE(Progressive Layered Extraction)是多任务学习(Multi-task Learning, MTL)中常用的模型结构。它们通过共享部分参数和引入特定机制来处理多任务学习中的任务冲突问题。
3.1. MMoE(Multi-gate Mixture of Experts)
(1) 核心思想
MMoE通过引入多个专家(Experts)和一个门控网络(Gating Network)来建模任务之间的关系,从而缓解任务冲突。
(2) 计算方式
- 专家网络:多个独立的子网络(Experts),每个专家负责学习不同的特征表示。
- 门控网络:为每个任务分配一个门控网络,用于动态调整各专家对当前任务的贡献。
(3)公式
对于任务
k
k
k,其输出
y
k
y_k
yk 计算如下:
y
k
=
h
k
(
∑
i
=
1
n
g
i
k
(
x
)
⋅
f
i
(
x
)
)
y_k = h^k \left( \sum_{i=1}^{n} g_i^k(x) \cdot f_i(x) \right)
yk=hk(i=1∑ngik(x)⋅fi(x))
其中:
- x x x:输入特征
- f i ( x ) f_i(x) fi(x):第 i i i 个专家的输出
- g i k ( x ) g_i^k(x) gik(x):任务 k k k 的门控网络对第 i i i 个专家的权重(通过一个softmax计算)
- h k h^k hk:任务 k k k 的输出层
3.2. PLE(Progressive Layered Extraction)
(1) 核心思想
PLE通过分层提取共享特征和任务特定特征,逐步分离任务间的共享信息和特定信息,从而更好地处理任务冲突。
(2) 计算方式
- 共享专家:多个共享专家(Shared Experts),用于提取任务间的共享特征。
- 任务特定专家:每个任务有自己的特定专家(Task-specific Experts),用于提取任务特定特征。
- 门控网络:为每个任务分配一个门控网络,用于动态调整共享专家和任务特定专家的贡献。
(3)公式
对于任务
k
k
k,其输出
y
k
y_k
yk 计算如下:
y
k
=
h
k
(
∑
i
=
1
n
s
g
s
,
i
k
(
x
)
⋅
f
s
,
i
(
x
)
+
∑
j
=
1
n
t
g
t
,
j
k
(
x
)
⋅
f
t
,
j
k
(
x
)
)
y_k = h^k \left( \sum_{i=1}^{n_s} g_{s,i}^k(x) \cdot f_{s,i}(x) + \sum_{j=1}^{n_t} g_{t,j}^k(x) \cdot f_{t,j}^k(x) \right)
yk=hk(i=1∑nsgs,ik(x)⋅fs,i(x)+j=1∑ntgt,jk(x)⋅ft,jk(x))
其中:
- f s , i ( x ) f_{s,i}(x) fs,i(x):第 i i i 个共享专家的输出
- f t , j k ( x ) f_{t,j}^k(x) ft,jk(x):任务 k k k 的第 j j j 个特定专家的输出
- g s , i k ( x ) g_{s,i}^k(x) gs,ik(x):任务 k k k 的门控网络对第 i i i 个共享专家的权重(通过一个softmax计算)
- g t , j k ( x ) g_{t,j}^k(x) gt,jk(x):任务 k k k 的门控网络对第 j j j 个特定专家的权重(通过一个softmax计算)
- n s n_s ns:共享专家的数量
- n t n_t nt:任务特定专家的数量
3.3. MMoE与PLE的区别
特性 | MMoE | PLE |
---|---|---|
核心思想 | 通过门控网络动态调整专家权重 | 分层提取共享特征和任务特定特征 |
专家类型 | 所有任务共享一组专家 | 共享专家 + 任务特定专家 |
门控网络 | 每个任务一个门控网络 | 每个任务一个门控网络 |
任务冲突处理 | 动态调整专家权重 | 分层分离共享信息和任务特定信息 |
适用场景 | 任务相关性较弱的多任务场景 | 任务相关性较强的多任务场景 |
3.4. 参考资料
- MMoE论文
- PLE论文