普通视图

发现新文章,点击刷新页面。
今天 — 2025年4月9日技术

每日一题-使数组的值全部为 K 的最少操作次数🟢

2025年4月9日 00:00

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有 严格大于 h 的整数值都 相等 ,那么我们称整数 h 是 合法的 。

比方说,如果 nums = [10, 8, 10, 8] ,那么 h = 9 是一个 合法 整数,因为所有满足 nums[i] > 9 的数都等于 10 ,但是 5 不是 合法 整数。

你可以对 nums 执行以下操作:

  • 选择一个整数 h ,它对于 当前 nums 中的值是合法的。
  • 对于每个下标 i ,如果它满足 nums[i] > h ,那么将 nums[i] 变为 h 。

你的目标是将 nums 中的所有元素都变为 k ,请你返回 最少 操作次数。如果无法将所有元素都变 k ,那么返回 -1 。

 

示例 1:

输入:nums = [5,2,5,4,5], k = 2

输出:2

解释:

依次选择合法整数 4 和 2 ,将数组全部变为 2 。

示例 2:

输入:nums = [2,1,2], k = 2

输出:-1

解释:

没法将所有值变为 2 。

示例 3:

输入:nums = [9,7,5,3], k = 1

输出:4

解释:

依次选择合法整数 7 ,5 ,3 和 1 ,将数组全部变为 1 。

 

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= 100

本质是计算不同元素个数(Python/Java/C++/Go/JS/Rust)

作者 endlesscheng
2024年12月8日 09:11

思考框架

  1. 理解操作在做什么。
  2. 把 $\textit{nums}$ 中的数都变成一样的,能变成哪些数?
  3. 如何最小化操作次数?

操作在做什么

题目说「选择一个整数 $h$」,哪些 $h$ 是可以选的?

根据「合法」的定义,$h$ 不能低于 $\textit{nums}$ 的次大值。比如 $\textit{nums}=[5,2,5,4,5]$,$h$ 不能小于次大值 $4$,否则大于 $h$ 的数不都相等。

所以操作只能改变大于次大值的数,也就是最大值

能变成哪些数

要让所有数都变成 $k$,前提条件是所有数都变成一样的。那么,能变成哪些数呢?

仍然以 $\textit{nums}=[5,2,5,4,5]$ 为例。选择 $h=4$,可以把最大值 $5$ 改成次大值 $4$。修改后 $\textit{nums}=[4,2,4,4,4]$,有更多的数都相同。并且修改后,原来的次大值 $4$ 就变成最大值了。下一次操作,我们就可以选择更小的 $h$,把更多的数都变成一样的。

选择 $h=2$,可以把最大值 $4$ 改成次大值 $2$。修改后 $\textit{nums}=[2,2,2,2,2]$,所有数都相同。

如果想继续改成比 $2$ 小的数,比如 $0$,选择 $h=0$ 即可。

所以,$\textit{nums}$ 中的数可以都变成任意 $\le \min(\textit{nums})$ 的数。

最小化操作次数

为了最小化操作次数,每次选 $h$ 为次大值是最优的。贪心地想,能一步到达次大值,没必要分好几步。

分类讨论:

  • 如果 $k > \min(nums)$,无法满足要求,返回 $-1$。
  • 如果 $k = \min(nums)$,操作次数为 $\textit{nums}$ 中的不同元素个数减一。比如 $[5,2,5,4,5]\to [4,2,4,4,4]\to [2,2,2,2,2]$,最大值 $5\to 4\to 2$,用了 $2$ 次操作。
  • 如果 $k < \min(nums)$,操作次数为 $\textit{nums}$ 中的不同元素个数。因为都变成 $\min(nums)$ 后,还需要再操作一次,才能都变成 $k$。

###py

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        mn = min(nums)
        if k > mn:
            return -1
        return len(set(nums)) - (k == mn)

###java

class Solution {
    public int minOperations(int[] nums, int k) {
        int min = Arrays.stream(nums).min().getAsInt();
        if (k > min) {
            return -1;
        }
        int distinctCount = (int) Arrays.stream(nums).distinct().count();
        return distinctCount - (k == min ? 1 : 0);
    }
}

###cpp

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int mn = ranges::min(nums);
        if (k > mn) {
            return -1;
        }
        unordered_set<int> st(nums.begin(), nums.end());
        return st.size() - (k == mn);
    }
};

###go

func minOperations(nums []int, k int) int {
    mn := slices.Min(nums)
    if k > mn {
        return -1
    }

    set := map[int]struct{}{}
    for _, x := range nums {
        set[x] = struct{}{}
    }
    if k == mn {
        return len(set) - 1
    }
    return len(set)
}

###js

var minOperations = function(nums, k) {
    const min = Math.min(...nums);
    if (k > min) {
        return -1;
    }
    return new Set(nums).size - (k === min ? 1 : 0);
};

###rust

use std::collections::HashSet;

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let min = *nums.iter().min().unwrap();
        if k > min {
            return -1;
        }
        let set = nums.into_iter().collect::<HashSet<_>>();
        set.len() as i32 - if k == min { 1 } else { 0 }
    }
}

复杂度分析

  • 时间复杂度:$\mathcal{O}(n)$,其中 $n$ 是 $\textit{nums}$ 的长度。
  • 空间复杂度:$\mathcal{O}(n)$。

分类题单

如何科学刷题?

  1. 滑动窗口与双指针(定长/不定长/单序列/双序列/三指针/分组循环)
  2. 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
  3. 单调栈(基础/矩形面积/贡献法/最小字典序)
  4. 网格图(DFS/BFS/综合应用)
  5. 位运算(基础/性质/拆位/试填/恒等式/思维)
  6. 图论算法(DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径)
  7. 动态规划(入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望)
  8. 常用数据结构(前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树)
  9. 数学算法(数论/组合/概率期望/博弈/计算几何/随机算法)
  10. 贪心与思维(基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造)
  11. 链表、二叉树与回溯(前后指针/快慢指针/DFS/BFS/直径/LCA/一般树)
  12. 字符串(KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机)

我的题解精选(已分类)

欢迎关注 B站@灵茶山艾府

Threejs全球坐标分布效果

作者 谢小飞
2025年4月8日 23:31

  在浏览网页时,笔者发现华为云一个有趣的效果,就是将地球上布局的城市标注出来,当城市出现在地球正面视线范围内时,就显示出来,而在靠近边缘时,就慢慢的隐藏直至消失不见;那么这种效果是如何实现的呢?里面又包含了哪些的逻辑呢?本文我们就来看下这个效果的实现过程。

  我们先来看下效果示例:

全球坐标分布效果

由于gif文件太大了,这里就不截取动图效果了,感兴趣的小伙伴可以直接滑到文末查看实现的效果。

环境准备

  首先还是准备我们画布的基础环境,初始化场景、相机、渲染器、控制器四件套:

export default class Index {
  constructor() {
    // 初始化场景
    this.scene = initScene();
    this.scene.background = new Color(0xf7f7f7);

    // 初始化相机
    this.camera = initCamera(new Vector3(10, 0, 0), 55, 0.001, 20000);

    // 初始化渲染器
    this.renderer = initRenderer();

    // 初始化控制器哦
    this.controls = initOrbitControls(this.camera, this.renderer);
    // 禁止缩放
    this.controls.enableZoom = false;
    // 阻尼
    this.controls.enableDamping = true;
    // 自动旋转
    this.controls.autoRotate = true;
  }
}

  我们再向场景中添加一个地球,这里我们直接用一个地球的纹理贴图即可:

// 球体的半径大小
const SPHERE_RADIUX = 3;

initMesh() {
    this.loader = new TextureLoader();
    const mat = new MeshBasicMaterial({
        map: this.loader.load("ditu.jpg"),
    });
    const geo = new SphereGeometry(SPHERE_RADIUX);
    const sphere = new Mesh(geo, mat);
    sphere.position.set(0, 0, 0);
    this.scene.add(sphere);
}

  下面就需要在地球🌍上贴上一个个的城市定位了,这里用到一个新的渲染器:CSS2DRenderer,这个渲染器用于将Html元素嵌入到3D场景中去,用于在场景中展示一些额外的信息;比如VR看房时候的标签,使用html标签有更好的操控,比如使用CSS还可以实现点击、悬浮、激活等等效果。

  我们在初始化场景的时候添加一个CSS2DRenderer渲染器:

import {
  CSS2DRenderer,
  CSS2DObject,
} from "three/examples/jsm/renderers/CSS2DRenderer.js";

export default class Index {
  constructor() {
    // 其他场景代码
    const labelRenderer = new CSS2DRenderer();
    labelRenderer.setSize(window.innerWidth, window.innerHeight);
    labelRenderer.domElement.style.position = "absolute"; // 设置渲染器样式
    labelRenderer.domElement.style.top = "0";
    labelRenderer.domElement.style.left = "0";
    labelRenderer.domElement.style.zIndex = "1";
    this.labelRenderer = labelRenderer;
    document.body.appendChild(labelRenderer.domElement);

    // 这里修改
    this.controls = initOrbitControls(this.camera, this.labelRenderer, false);
  }
}

这里要注意的是,我们在初始化controls控制器的时候,需要修改将CSS2DRenderer传入控制器的构造函数中,否则就会出现画布无法转动的情况。

  下面我们就需要将Html标签添加到CSS2DRenderer中去,

const list = [
  { id: 0, name: "北京", lng: 116.39, lat: 39.9 },
  // 省略其他城市
];

const tagsList = [];
for (let i = 0; i < list.length; i++) {
  const { name, lng, lat } = list[i];

  const pos = this.latLongToVector3(lng, lat, SPHERE_RADIUX);

  const box = document.createElement("div");
  box.className = "global_position-box";
  box.innerHtml = name;

  const tag = new CSS2DObject(box);
  tag.position.copy(pos);
  this.scene.add(tag);
  tagsList.push(tag);
}

this.tagsList = tagsList;

  这里在循环列表的时候,需要将数据的经纬度坐标转换成在三维空间里的x、y、z坐标,我们用到一个latLongToVector3函数进行转换处理,我们下面会介绍到这个函数。

  通过CSS2DObject实例化标签后,设置标签的左边;但是将标签添加到页面上去后,我们会看到,如果是在我们视线背面的标签,同时也显现出来了。

CSS2DObject效果

  这样的效果肯定不是我们想要的,因此,我们需要在每次render的时候,就需要不断的去控制每个html标签的透明度,当标签在我们视线后面的时候就设置为0,这才是我们想要的效果;那么标签的透明怎么来计算呢?我们先来学习三个工具函数的使用。

经纬度vs球坐标系

  首先我们要学习的一个就是经纬度和三维球体坐标转换的一个关系函数,它也是Three.js中做三维地图经常会遇到的一个问题,下面我们就来看下它的原理和实现逻辑。

  我们知道在三维坐标系中,我们用xyz能很快确定一个点在空间上的坐标;但是在球体坐标系中,我们需要另外三个参数来确定一个点的位置,我们看下数学中是如何来表示的:

  • 径向距离:也就是我们常说的球体半径,是球面坐标点到球心的距离,用r表示。
  • 极角:是z轴与r的交角,一般用θ表示。
  • 方位角:是赤道面(由 x 轴与 y 轴确定的平面)上起始于 x 轴,沿逆时针方向量出的角度,通常用φ表示。

我们假设地球是一个完美的球体。

球体坐标

需要注意的是,Three.js中,y轴和z轴与数学描述中的位置是相反的,即y轴是纵向的,z轴是从后往前延伸的;这也导致了下面代码中y和z的计算方式与公式的计算方式互换。

  如果用公式来表示,直角坐标和球坐标的对应关系如下:

转换公式

  公式有了,我们下面就要来看公式中的极角θ和方位角φ分别如何来得到;我们知道,纬度是点相对于赤道平面的角度,从-90°的南极到90°的北极,而极角是Three.js中的Y轴和点之间的夹角,因此北极是0,赤道是90,而南极是180;因此我们需要用90减去纬度,再通过度数和弧度的转换即可得到如下代码:

const phi = (90 - latitude) * (Math.PI / 180);

  其次是方位角,由于是沿逆时针方向量出的角度,我们对其取反:

const theta = (longitude + 180) * (Math.PI / 180); 

但是我们实际开发中拿到的地图不一定是标准的地图,需要对方位角进行处理,不一定是加180。

  极角和方位角得到了,我们通过公式得到一个标准的经纬度转换三维空间坐标的函数如下:

/**
 * 将经纬度转换为三维空间坐标
 * @param {number} longitude - 经度(-180到180)
 * @param {number} latitude - 纬度(-90到90)
 * @param {number} radius - 球体半径
 * @returns {THREE.Vector3} 返回Three.js的三维向量坐标
 */
function latLongToVector3(longitude, latitude, radius): Vector3 {
  // 极角(从北极开始)
    const phi = (90 - latitude) * (Math.PI / 180); 
    // 方位角(从本初子午线开始)
    const theta = (longitude + 180) * (Math.PI / 180); 

    // 计算球体上的点坐标(Y轴向上)
    const x = -radius * Math.sin(phi) * Math.cos(theta);
    const y = radius * Math.cos(phi);
    const z = radius * Math.sin(phi) * Math.sin(theta);

    return new THREE.Vector3(x, y, z);
}

角度计算函数

  下面我们再来看一个数学问题:

在三维空间中,已知ABC三个点的坐标,求每个点的角度?

  经常学高数的朋友都知道,不要把它想象成三维,而是一个平面上的三角形;根据下面三角形的余弦定理:

余弦定理

  我们看上面的公式,根据任意三条边的长度,我们都可以计算出角度的余弦值;因此我们需要一个函数来计算三维空间下两个点之间的距离:

// 计算空间上的两个点之间的距离
export function calc3DPointDist(x1, y1, z1, x2, y2, z2) {
  const distX = x2 - x1;
  const distY = y2 - y1;
  const distZ = z2 - z1;
  return Math.sqrt(distX * distX + distY * distY + distZ * distZ);
}

  有了这个函数,我们就可以计算每个角对应边的长度了:

/**
 * 已经ABC三维坐标,求各个点的角度
 * @param {*} A
 * @param {*} B
 * @param {*} C
 * @param {String} pos
 * @returns
 */
export function calc3DAngle(A, B, C, pos = "A") {
  // 三角形每条边的长度
  const a = calc3DPointDist(B.x, B.y, B.z, C.x, C.y, C.z);
  const b = calc3DPointDist(A.x, A.y, A.z, C.x, C.y, C.z);
  const c = calc3DPointDist(A.x, A.y, A.z, B.x, B.y, B.z);
  // ...
}

  将上面的余弦定理继续推导一下,我们可以得到每个角度的cos计算公式:

余弦定理推导

  再利用Math.acos,我们就得到了ABC三个角的角度;再通过传入的参数pos,直接得到我们想要角的角度:

export function calc3DAngle(A, B, C, pos = "A") {
    // 省略上面a、b、c的计算
    let cosA = Math.acos((b * b + c * c - a * a) / (b * c * 2));
    let cosB = Math.acos((a * a + c * c - b * b) / (a * c * 2));
    let cosC = Math.acos((a * a + b * b - c * c) / (a * b * 2));
  
    return {
      A: (cosA * 180) / Math.PI,
      B: (cosB * 180) / Math.PI,
      C: (cosC * 180) / Math.PI,
    }[pos];
}

clamp函数

  clamp函数很多同学可能都没用过,一般在c++或者python中用的比较多,它的作用是;它需要传入三个值:

function clamp(num, min, max) {
  // ...
}

  三个参数分别代表如下含义:

  • num:需要判断的数值。
  • min:范围的最小值。
  • max:范围的最大值。

  为了方便大家理解,我们还是举几个例子🌰来简单看下:

// 返回10,小于最小值,返回最小值
clamp(5, 10, 20)


// 返回16,在返回内,返回原值
clamp(16, 10, 20)


// 返回20,超出最大值,返回最大值
clamp(36, 10, 20)

  通过三个demo,相信大家就能理解这个函数的作用了,函数的实现其实也非常简单:

function clamp(num, min, max) {
  return Math.min(Math.max(num, min), max);
}

显示还是隐藏标签

  对上面两个函数理解后,我们就可以回到地球上坐标的处理了;我们在threejs每次render的时候循环tagsList:

{
  render() {
    // 当前摄像头的位置
    const cameraPos = this.camera.position;

    if (this.tagsList && this.tagsList.length) {
      this.tagsList.map((tag) => {
        const { position, element } = tag;
      });
    }
  }
}

  首先我们将tag打印出来看下,里面有两个属性position和element,是我们所需要的;position属性是一个Vector3类型,表示tag当前的位置信息,element属性是一个dom节点,表示标签对应的dom元素。

  我们想象一下,在三维空间中,我们的相机位置Camera一直在旋转的,因为设置了autoRotate自动旋转;而标签的位置position是固定的;因此这两个点和原点之间就形成了一个特殊的三角形:

三维视角的位置

  临界情况就是以原点为顶点的角正好是90度,此时我们刚刚能看到标签;当相机位置不断旋转时,如果小于90度,我们还是可以看到标签的;但是如果大于90度,标签已经到了球体的后面了。

const originPoint = new Vector3(0, 0, 0)
this.tagsList.map((tag) => {
  const { position } = tag;
  // 以原点为顶点的角度
  const ang = calc3DAngle(cameraPos, originPoint, position, "B");
  // 省略其他
});

这里传入的顺序无所谓,我们只要计算以原点为顶点的角度即可。

  利用上面的calc3DAngle函数,我们将三个位置传入,就可以很轻松的得到角度ang;有了这个角度,我们就可以计算标签的透明度了;我们上面提到了,透明度的临界值就是90度,但是实际上由于视角和球体的缘故,这个角度不是很准确,笔者测试之后大概是在85度左右。

  同时,我们的标签也并不是一下子透明度就从1变到0的,我们需要给它一个缓冲范围,让它也缓缓,在这个范围内会进行变化;这个范围大致就是从80度到85度之间,透明度会从1到0逐渐的变化。

透明度映射

  看到这样的映射关系图,相信大家已经猜到了,没错,这里就要用到我们上面介绍的clamp函数了,我们将角度ang夹到80到85之间,然后使用scale函数进行映射后就得到了我们的透明度opacity,给element元素的样式赋值即可:

/**
 * 映射范围
 * @param {Number} number 需要映射的数值
 * @param {Number} inMin 映射入口的最小
 * @param {Number} inMax 映射入口的最大
 * @param {Number} outMin 映射出口的最小
 * @param {Number} outMax 映射出口的最大
 */
export function scale(number, inMin, inMax, outMin, outMax) {
  return ((number - inMin) * (outMax - outMin)) / (inMax - inMin) + outMin;
}

const ANG1 = 80;
const ANG2 = 85;

this.tagsList.map((tag) => {
  // 省略其他代码
  const opacity = scale(clamp(ang, ANG1, ANG2), ANG1, ANG2, 1, 0);
  tag.element.style.opacity = opacity;
});

  这样我们的标签就实现了一个过渡变化;最后,在vue页面卸载之后,别忘记还需要将CSS2DRenderer渲染器的dom节点删除,否则会导致页面会有问题:

{
  beforeDestroy() {
    if (this.labelRenderer) {
      document.body.removeChild(this.labelRenderer.domElement);
    }
  }
}

  我们来看下实现的效果,跟原页面的效果已经十分接近了。

本文所有源码敬请关注并在前端壹读后台回复关键词【全球坐标分布】即可获取。

总结

  我们发现很多3D场景下的问题,其本质都是一个个数学问题;本文我们研究了球体和经纬度转换函数、三个点之间的角度计算函数,这两个问题无不考验着我们的数学推理能力;笔者甚至发现,在完成这个案例的过程中,学习的数学知识,甚至比写代码的时间更长、更费时间。

如果觉得写得还不错,敬请关注我的掘金主页。更多文章敬请访问谢小飞的博客

昨天 — 2025年4月8日技术

一篇论文,看见百度广告推荐系统在大模型时代的革新

作者 百度Geek说
2025年4月8日 10:29

我们见证了 DeepSeek R1,用强大的推理能力再次点燃 AI 智力增长的火箭。

在上个星期,OpenAI 给 GPT-4o 的一波图像生成更新又让全网陷入了梗图、甚至玩梗视频制造的火热氛围中。

用 GPT-4o 渲染过的《星际穿越》电影片段。

AI 的「想象力」一次又一次震撼着我们,基于先进大模型的应用正在越来越多的领域引发革命,被改变的也包括科技领域本身。

比如,生成式 AI 正在改变人们获取信息的方式。很多人认为,大型语言模型(LLM)既然强于生成和推理,那么应该也能从用户的历史行为中洞察出深层次的兴趣,进而为推荐系统找到全新的可能性。

既然生成式 AI 能通过已知上下文预测生成新内容,那么已知一些人们感兴趣的内容,AI 应该也可以预测出他们的下一个兴趣点。这个预测的内容可以是一篇文章、一段视频、某个品牌的商品或是 App 上的服务。

近日,百度推荐广告团队在广告生成式推荐取得了新成果,其构建的生成式 AI 推荐系统实现了前所未有的效果。

图片

  • 论文标题:Sparse Meets Dense: Unified Generative Recommendations with Cascaded Sparse-Dense Representations

  • 论文 ArXiv:arxiv.org/pdf/2503.02…

在科技行业中,推荐系统虽不如图像生成、代码生成那样具有极高的讨论度,但一直是数字生态举足轻重的一部分。它在电商平台、视频 App 和社交网络上广泛出现,是提供符合用户偏好个性化内容的核心技术。

ChatGPT 推出以来,生成式检索(Generative Retrieval)逐渐成为了推荐系统领域最热门的研究方向。与传统的序列推荐方法不同的是,生成式模型可以根据用户的行为更加直接的进行预测,由 AI 模型处理复杂的用户 - 商品交互,可以提供推理和小样本学习等新能力,大幅提高推荐准确性和多样性。

尽管把生成式 AI 引入推荐系统的创新已有不少,但与序列密集检索方法相比,生成式检索方法仍然面临一些挑战,比如它们往往难以进行细粒度相似性建模。

谷歌的 TIGER 是推荐系统生成检索的知名方法,如图 1(左下)所示;百度则新提出了级联组织双表征生成式检索(Cascaded Organized Bi-Represented generAtive Retrieval,COBRA),这是一个将生成式和密集检索高效融合的框架。图 1(右)展示了 COBRA 的推理范式。

图片

COBRA 研究的主要贡献如下:

  • 级联双表示的检索框架:COBRA 作为一种新型生成式推荐框架,可在生成稀疏 ID 和稠密向量之间交替。通过将稠密表示合并到 ID 序列中,COBRA 弥补了基于 ID 的方法固有的信息损失。使用稀疏 ID 作为生成稠密向量的条件可以降低稠密表示的学习难度。

  • 端到端训练可学习的稠密表示:COBRA 利用原始特征数据作为输入,通过端到端训练生成稠密表示。与静态嵌入不同,COBRA 的稠密向量是动态学习的,可捕获语义信息和细粒度细节。

  • 生成过程由粗到细:在推理过程中,COBRA 首先生成稀疏 ID,然后将其反馈到模型中以生成精细的稠密表示,从而提取细粒度兴趣表征。此外,该研究还提出了 BeamFusion 来实现推荐多样性和精度的灵活可控。

  • 全面的实证验证:通过对多个基准数据集的大量实验,研究证明了 COBRA 在推荐准确率方面的表现优于现有的 SOTA 方法,验证了 COBRA 在推荐任务中真实有效性。

01 生成式检索 几波技术演进

其实,在形成如今 COBRA 方案之前,百度研究团队针对广告场景中的生成式推荐任务,经历了多个阶段的技术探索,并针对暴露出来的技术缺陷持续优化与完善。

在生成式推荐任务中,大模型要预测的 item 是综合体(如广告标题、品牌、多模信息等)⽽并⾮简单的 token。因此,1)如何对 item 进行表征,2)基于表征进行序列建模是生成式推荐的两个核心问题。

最开始,百度采用了「纯⽂本表征 + LLM 建模」的方案,直接利用 LLM 进行推荐。通过标题、落地页等文本来表征 item,虽然可以辅助理解用户意图、提升可解释性,但超长的输入导致了巨大的资源和性能开销,运行成本较高。随后尝试通过短语来表征 item,但短语很容易出现信息压缩过度、表达不全的情况,难以全面描述 item 的各种属性。此外,item 之间的序列关系偏重兴趣协同而并非单纯的语义关系,与 LLM 建模的语义关系存在着鸿沟。

在意识到无法简单的直接使用现有方法后,研究团队开始考虑对 item 进行压缩表达,全面满足性能、信息完备、item 关系建模的要求。

因此,研究团队形成了「稠密表征 + 对⽐学习度量」的方案,核心在于将 item 表征为稠密向量。为此,他们引入了一个编码器逐个对 item 内容进行编码,使得 item 序列转变为一组向量序列并输入到一个 Causal Decoder 中;接着通过 Next Item Prediction 的方式完成模型训练,在训练中引入对比学习,使得编码器、解码器能够同步更新。在推理阶段,算法通过编码器输出 item 向量来构建索引,并通过向量序列输入到解码器中获取用户表征,最终完成 ANN 召回。

这一方案的优势在于表达能力强,可以完整利用 item 原始信息,对比学习保证了端到端训练,进一步建模序列中隐含的协同信息。虽然 item 信息利用和序列关系建模两大关键问题得到了有效解决,但仍然是在较大稠密空间上建模,缺少了兴趣探索过程,建模复杂度并未降低。

图片

「稠密表征 + 对⽐学习度量」方案概览。

接下来,研究团队受到谷歌 TIGER 的启发,尝试了「稀疏表征 + 稀疏 ID ⽣成」的方案,通过稀疏 ID 来表征 item。

完整的实现过程是这样的:首先通过商业预训练模型对广告特征进行嵌入,然后使用残差量化变分自编码器(RQ-VAE)将嵌入向量量化为带层次结构的 ID Tuple(如 L1、L2、L3),最后将 ID 序列输入到 Causal Transformer 并通过下一个 ID 预测来建模序列。在推理阶段,在给定行为序列的情况下,模型可以通过自回归方式来生成下一个可能的广告 ID。

稀疏表征的引入充分发挥出了「嵌入 + 量化」的作用,将 item 转化为 ID,使模型在压缩空间中学习用户兴趣转移,尤其适合高度个性化推荐场景中的「千人千面广告推送」。然而,受限于相互隔离的「嵌入、量化、序列建模」,不可避免地出现了信息损失,导致对用户偏好的精细变化捕捉效果较弱。

在尝试了以上技术方案之后,研究团队认识到了单一表征方式难以同时兼顾粗粒度类别信息和细粒度特征信息的局限性,提出了 COBRA 框架,通过级联方式融合稀疏 ID 和稠密向量表征,形成了「稀疏 - 稠密级联表征 + ⽣成度量⼀体化」方案,大大增强了模型的灵活性和适应性。

02 COBRA 框架的四大创新

下图为 COBRA 的整体框架,在集成了级联稀疏 - 稠密表征和由粗到细生成之后,实现了当前 SOTA 级别的推荐性能。

图片

一是级联稀疏 - 稠密表征。

过程中,级联表征将稀疏 ID 和稠密向量集成在一个统一的生成式模型中。对于每个 item,它的稀疏 ID 和稠密向量组合起来以形成级联表征。这样做可以兼顾稀疏与稠密表征的优点,获得更全面的 item 特征,其中稀疏 ID 通过离散约束提供稳定的类别基础信息,稠密向量确保模型捕获高级语义和细粒度细节。

二是交替学习的序列建模。

得益于级联表征的方式,方案中将目标 item 的概率分布建模分为两个阶段,以利用稀疏与稠密表征的互补优势。COBRA 没有选择基于历史交互序列来直接预测下一个 item,而是转为交替预测稀疏 ID 和稠密向量。具体来说,采用 Causal Transformer 统一生成式模型接收级联表征作为输入,从而捕获序列依赖关系。

三是端到端训练。

COBRA 的端到端训练过程旨在同时优化稀疏和稠密表征预测。训练过程由一个复合损失函数控制,该函数结合了稀疏 ID 预测和稠密向量预测的损失。稀疏 ID 预测损失在基于历史序列预测下一个稀疏 ID 的过程中,保证了模型的效率;稠密向量预测损失用于细化稠密向量。同时,该稠密向量由端到端的可训练编码器生成,并在训练过程中进行优化,从而适应不同推荐任务的特定需求。

这种双目标的损失函数可以实现均衡的优化过程,使模型在稀疏 ID 的指导下动态地细化稠密向量,同时端到端的训练方法可以捕获高级语义和协同信息。

最后是由粗到细生成。

作为一种高效的策略,这有助于模型解耦与模块优化,并在保证候选多样化与覆盖性的同时进一步提高精度。在推理阶段,COBRA 采用由粗到细的生成过程,先生成稀疏 ID,后细化稠密向量,如下图 3 所示。

具体地,首先基于⽤户历史交互序列,使用 Transformer 解码器建模的 ID 概率分布,并利用 BeamSearch 算法生成下一个 item 的稀疏 ID。然后,将⽣成的稀疏 ID 追加到输⼊序列中,作为条件进⼀步⽣成对应的稠密向量,捕获 item 的细粒度特征。同时引⼊ BeamFusion 机制,并结合 BeamSearch 和近邻检索分数,在确保推荐精度的同时保证召回⼴告候选的多样性。

图片

由粗到细的生成过程。

COBRA 框架为生成式推荐领域提供了一个的新范式。

03 多场景性能提升 已实际应用

实测效果如何?研究团队使用公开和工业数据集对 COBRA 框架进行了全面评估,并重点展示了 COBRA 提升推荐准确率和多样性的能力,并通过离线和在线评估来验证实际效果。大量实验表明,COBRA 优于目前业内最先进的方法。

在公开数据集上,研究团队使用了 Amazon Product Reviews 数据集,并重点分析了「Beauty」、「Sports and Outdoors」以及「Toys and Games」三个子集。

实现结果如下表 2 所示,其中在「Beauty」数据集上,COBRA 的 Recall@5 和 Recall@10 相比之前的最佳模型 TIGER 分别提升了 18.3% 和 11.9%;在「Sports and Outdoors」数据集上,COBRA 的 Recall@5 和 NDCG@10 相比 TIGER 分别提升了 15.5% 和 18.8%;在「Toys and Games」数据集上,COBRA 的 Recall@10 和 NDCG@10 相比 TIGER 分别提升了 24.5% 和 19.2%。

图片

对于行业数据集,研究团队采用了 Baidu Industrial 数据集,它基于百度广告平台上的用户交互日志构建,涵盖了列表页、双栏、短视频等多种推荐场景,包含了 500 万用户和 200 万条广告,全面展现了真实用户行为和广告内容。

为了验证本文策略的有效性,研究团队对 COBRA 以及移除稀疏 ID 的变体 COBRA w/o ID、移除稠密向量的变体 COBRA w/o Dense 以及移除 BeamFusion 的变体 COBRA w/o BeamFusion 进行了比较。结果如下表 3 所示,相较于三种变体,COBRA 均体现出了优势,从而验证了该框架中各个组件的有效性。

在 K=800 时,COBRA 的召回率为 0.4466,相较没有稀疏 ID 的变体提升了 43.6%, 相较没有 BeamFusion 的变体提升了 36.1%。

图片

为了评估 COBRA 的表征学习能力,研究团队对广告稠密嵌入展开相似度矩阵分析,如下图 4 所示,展现了 COBRA 模型的类别内聚性和类别间分离性。相反,没有稀疏 ID 的模型变体显示出较弱的类别间分离性(图 4b),加入稀疏 ID 则可以增强内聚性和分离性(图 4c 差异矩阵定量分析)

这意味着 COBRA 不仅能够将同⼀类别的项目紧密地聚集在⼀起,还能将不同类别的项⽬有效地区分开来,从而在推荐时能够更精准地捕捉⽤户的兴趣点。

图片

进一步的可视化广告嵌入分布验证了 COBRA 的嵌入能力。通过随机抽取一万个广告,研究团队观察到了不同广告嵌入形成了明显的聚类中心,如下图 5 所示。我们可以看到,紫色、青色、浅绿色和深绿色聚类主要分别对应小说、游戏、法律服务和衣物广告。

图片

由于与大量业务直接相关,推荐系统是一个很「卷」的领域,在百度的研究中,工程师们把 COBRA 最终策略投放到真实生产环境上跑了一圈,在 A/B 测试中实现了转化率增加 3.6%,ARPU(平均每用户收入)增加 4.15% 的好成绩。

这些业务指标提升表明,COBRA 不仅在离线评估中表现出色,还能够在实际生产环境中带来可衡量的商业价值,目前该方法在百度广告推荐业务中已经全量上线。

04 结语

经过一系列提升和改进,生成式 AI 已经可以做到表达清晰、预测准确,并在百度的广告推荐系统中实现了应用。与很多领域一样,推荐系统正在向着需求个性化的方向快速发展,而在这个方向上,AI 提供的解决方案已经展现出了独特的优势。

对于普通人来说,在各种 App 上,大模型驱动的推荐系统可以帮助我们获取更多有用的内容,让信息流更加聪明。

对于科技公司而言,或许在几年之内,AI 驱动的业务就可以从目前的局部智能化进化到「需求预测 - 生产调度 - 仓储物流 - 营销交付」的全流程智能化阶段。

未来,AI 应用的深度将决定业务的增长速度。

------END------

推荐阅读

前沿多模态模型开发与应用实战3:DeepSeek-VL2多模态理解大模型算法解析与功能抢先体验

秒哒首发即爆发!上线首日吸引2万用户,打造3万应用!

秒哒,全面开放!

图灵数据洞察平台-TDF(Turing Data Finder)

两连发!文心大模型4.5及X1,上线千帆!

❌
❌