基于向量的召回算法及其在个性化广告新闻中的应用实践-刘政.pdf

Embedding Based Recall: Practice, Progress and PerspectivesZheng Liu, Jianxun Lian, Xing XieSocial Computing Group, MSRAAug 15th, 2021Reinforced Anchor Knowledge Graph Generation for News Recommendation Reasoning, Liu et. al. KDD 2021Outline• Overview• Multi-Stage Pipeline• EBR: Pros and Cons• Embedding learning algorithms• Negative Augmentation• Hard Negative Sampling• Diversified representation• Training as knowledge distillation• Things beyond learning algorithms• Efficiency issues• Combo of sparse and denseOverview: Multi-Stage Pipeline× 106~9× 101~3× 100~1L1 Stage (Recall)L2 Stage (Rank)L3 Stage (Re-rank)•Rank: high-precision, KPI-oriented•Recall: fast, accurate, comprehensiveOverview: Multi-Stage PipelineMicrosoft Xbox 360 E 250GBXbox 360 Game System HDMIXbox 360 4GB Slim ConsoleMicrosoft Xbox 360QueryAdsFast, AccurateOverview: Multi-Stage PipelineMicrosoft Xbox 360 E 250GBXbox 360 Game System HDMIXbox 360 4GB Slim ConsoleMicrosoft game consoleQueryAdsVocabulary mis-matchOverview: EBR, Pros and CosXbox 360 Game System HDMIMicrosoft game consoleANN Index (PQ, HNSW)High-generalizable,Relatively fastOverview: EBR, Pros and ConsModel’s training isdata-intensiveXbox 360 Game System HDMIMicrosoft game console< Q: Xbox 360 Game System HDMI, K: Microsoft game console \>Overview: EBR, Pros and ConsXbox 360 Game System HDMINintendo switch console… the Xbox 360 console hard drive … Hard drive will be at least 20GB model… supports HD graphics in 16 x 9 wide-screen with anti-aliasingembeddings can beambiguousOverview: EBR, Pros and Cons[1] SimCSE, Gao et.al.[2] Understanding Contrastive Learning …ICML 2020, Wang et. al. AlignmentUniformityOutline• Overview• Multi-Stage Pipeline• EBR: Pros and Cons• Embedding learning algorithms• Negative Augmentation• Hard Negative Sampling• Training as distillation• Diversified representation• Things beyond learning algorithms• Efficiency issues• Combo of sparse and denseAlgos: Negative AugmentationQKDPR, Karpukhin et. al.One’s positive usedothers’ negativeLarger batch size ->higher accuracybatchAlgos: Negative Augmentation……Dev-1Dev-�Dev-�+Cross-device negative samplingExpand #negativesby × �RocketQA, Ding et. al.Algos: Negative AugmentationCross-device values made virtual-differentiableVirtual Differentiable Cross-Device Sharing (V-DCS)1.Generate embeddings for each batch, one batch/device2.Broadcast embeddings to all devices3.Compute the global NCE-loss symmetrically on all devices, based on the broadcasted embeddings4.Back-propagate and reduce the gradients on all devicesSoPQ, Xiao and Liu et. al.Algos: Hard Negative SamplingGet hard negatives by sample from ANN searchApproximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval (ANCE, Xiong et. al.)1.Learn embedding model with in-batch negative2.Build ANN index and get hard negatives3.Update embedding model with hard negative4.Repeat 2. and 3. until convergeAlgos: Training as distillationKeywords sorted by relevanceQuery + KeywordEst. relevance…TeacherQueryKeywordWeak-annotatedlabelStudentTraining as distillation•Training teacher model with labeled data•Annotate unlabeled data with teacher•Train student with labeled and weak-annotated dataRocketQA, Ding et. al.Weak Annotation, Li et. al. Algos: diversified representationUser history(Web browsings)Target (news/ads)User history may consist ofhighly diverse eventsUser embeddings can be ambiguousAlgos: diversified representationElastic Multi-embedding Retrieval (Bloom-filter style interest extractor)•Generate item embeddings•Compute item embeddings’ membership via learned hash•Group items based on binary codes•Aggregate items with the same binary codes for user embeddingsOctopus, Liu et. al. Comprehensive, elastic, parameter-efficient010000101000ANN Index3 hash-class, eachhas 4 functions ->34 latent paritionsOutline• Overview• Multi-Stage Pipeline• EBR: Pros and Cons• Embedding learning algorithms• Negative Augmentation• Hard Negative Sampling• Diversified representation• Training as knowledge distillation• Things beyond learning algorithms• Efficiency issues• Combo of sparse and denseThings beyond: EfficiencyDesired properties about ANN (HSWN, PQ, ANNOY …)• Accurate (high recall)• Fast (low latency)• Light (low mem cost)FAISS, Facebook AI ResearchNot enough budget to host the index in MEM …Things beyond: EfficiencyDiskANN, Subramanya et. al.• Bi-granularity structure: Vamana Graph + PQ, quantized embeddings and graph in MEM, full-precision embeddings in SSD• Using full-precision embeddings to build graph• Using quantized embeddings for coarse-screened search• Using full-precision embeddings for refinementquantized embeddingsbuild graphfull-precision embeddingscoarse screenfull-precision embeddingsThings beyond: EfficiencyUser history(Web browsings)Target (news/ads)BERTNot enough budget to encode the entire events with BERT…Applying PLMs for user modeling• Encode all events with BERT • Aggregate events embeddings for user embeddingsThings beyond: Efficiency...