Table of Contents

  1. Algorithm
  2. Review
    1. 简介
    2. 杠杆对齐电影剧本信息
    3. 一个多模态序列模型
    4. 结论
  3. Tips
    1. 例子
    2. C 实现
  4. Share

Algorithm

Leetcode 2896: Apply Operations to Make Two Strings Equal

https://dreamume.medium.com/leetcode-2896-apply-operations-to-make-two-strings-equal-416d27820881

Review

Detecting Scene Changes in Audiovisual Content

简介

当观看一个电影或一个连续剧时，我们体验一个紧密地叙述，通常不需要太多思考底层结构。然而，电影和连续剧不是原子单位，由更小的元素比如帧、场景、序列和行为。理解这些元素和它们互相如何关联比如视频总结和高亮检测、基于内容的视频提取、声音加工和视频编辑很重要。在 Netflix，这样的工作流被世界上许多团队每天执行数百次，这样投资在内容理解的算法相关工具可收割特别的奖励

然而更多粒度单元比如帧和影片边界要么是琐碎的要么可主要依赖基于像素的信息，更高的顺序段需要一个更细节的内容理解，比如叙述或情感弧。更进一步，一些线索可从视频之外比如场景或音频和对话轨道得出。场景边界检测，特别地，确定场景间过渡的任务，一个场景指在相同时间和位置（通常有相关静态角色集）的连续序列影片和共享一个共同的行为或主题

在这个博客中，我们呈现两个补充处理在试听内容中检测场景边界。第一个方法，可视为一个弱监督，对齐荧幕字幕和时间字幕和赋予一个时间戳到屏幕的场景头来杠杆化场景形式的辅助数据。第二个处理，我们显示一个相对简单，预训练影片水平嵌入在我们内部的评测基准中有更好的当前艺术状态基线

杠杆对齐电影剧本信息

电影剧本是电影或演出的蓝本。它们以特殊的形式格式化，每个场景以一个场景头开始，显示属性比如位置和时间。这种一致的格式使得它能够分析电影剧本为一个结构化格式。同时，a) 改变在不停进行中（方向或角色的决定）或 b) 在发布的产品和编辑很少反映在电影剧本中，例如，不能重写来反映改变

为了与数据源对齐协调，我们需要对齐时间采样文字（例如，关闭的标题和音频描述）与电影剧本文字（对话和行为线），容忍 a) 正在发生的改变可导致语义相似但不匹配线对和 b) 可能的后期改变更重要（重排序，删除或插入整个场景）。为处理第一个挑战，我们使用语句水平预训练嵌入，例如，从一个嵌入模型优化精简确定，在两种源中呈现文字。对第二个挑战，我们使用动态时间变形（DTW），一种度量两个序列随时间或速度改变之间的相似性的方法。当 DTW 假设一个对齐上的单调条件，其频繁在实际中违反，它足够强壮来从本地非对齐和显著事件的大多数中恢复好对齐

DTW 的结果，场景头有时间戳可显示视频中可能的场景边界。对齐也用于例如有争议的视听的 ML 模型，电影剧本信息比如场景水平嵌入或转换标签赋值到视听的内容到训练的电影剧本预测模型

一个多模态序列模型

上述对齐方法是得到和运行在场景改变任务的好方法，因为它组合了容易使用预训练嵌入和知名的动态规划技术。然而，它预假设高质量电影剧本的有效性。一个补充处理（事实上，可使用上述对齐作为一个特性）是我们接下来呈现在注释的场景改变数据上训练一系列模型。Netflix 某个工作流捕获了这个信息，且那是我们主要的数据源；公开发布的数据集也是有效的

从架构上来看，模型很简单 - 一个双向 GRU 在每一步吸收影片呈现且预测是否一个片段是一个场景的结尾。这些预训练、多模态影片嵌入、一个喜欢的设计选择在我们的设置中给定获取标签场景改变数据和我们从预训练各种对影片的嵌入模型相关更大的缩放的难度，这些丰富了模型

对视频嵌入，我们杠杆一个室内模型预训练在对齐的视频剪辑与配对文字（前述提及的“时间戳文字“）。对音频嵌入，我们首先执行源分割来尝试从背景（音乐、音效、噪音）分割前景（语音），使用 wav2vec2 分别嵌入每个独立的波形，且然后串联结果。早期和后期阶段混合处理已探索出来；下图 1，音频和视频嵌入被串联且给到一个单个 biGRU，且之后下图 2，每个输入模态编码到它自己的 biGRU，隐藏状态在输出层之前被串联

img

img

我们发现：

  • 我们的结果匹配且有时甚至超出艺术状态（只使用视频模态且在我们的评估数据上的评测）。我们对正向标签使用 F-1 评分评估输出，且也释放这个评估来考虑 “off-by-n” F-1，例如，如果模型预测场景改变在 n 次真实影片片段中。这对我们使用案例由于采用人工循环设置这些模型来说是一个更实际可行的办法
  • 之前的工作，添加音频特性提升结果 10-15%。性能上一个主要的驱动变种是后期 vs 早期混合
  • 后期混合一致地 3-7% 好于早期混合。直觉上，这个结果是有意义的 - 影片片段间时间上的依赖性跟特殊的模态很像且应该独立地编码

结论

我们呈现了两种补充方式处理场景边界检测来杠杆各种有效的模态 - 电影剧本、音频和视频。逻辑上，下一步是 a) 组合这些处理且在同一的模型下使用电影剧本特性 和 b) 跨多个电影片段干涉任务一般化输出，例如，电影片段类型分类和可记忆时刻确认，作为我们可以假设这个路径对训练一般化目的视频理解更长形式内容的模型有帮助。更长形式内容也包含更多复杂叙述结构，且我们想象这个工作作为在我们的多模态机器学习模型下一系列目标为更好集成叙述理解的工程的开始

Tips

Van der Corput sequence

一个 van der Corput 序列是一个在单位区间中最简单的一维低差异序列的例子。它在 1935 年首次由荷兰数学家 J. G. van der Corput 描述。它通过反向的基于 n 表示的自然数序列（ $ 1, 2, 3, \ldots $ ）构成

正整数 $ n \ge 1 $ 的 b 进制表示为

$ n = \sum^{L-1}_ {k=0} d_ {k}(n)b^{k} = d_ {0}(n)b^{0} + \cdots + d_ {L-1}(n)b^{L-1} $

以 b 为基表示 n，且 $ 0 \le d_ {k}(n) < b $。即，n 为以 b 为基 k 数字的展开。van der Corput 序列中第 n 个数为

$ g_ {b}(n) = \sum^{L-1}_ {k=0} d_ {k}(n)b^{-k-1} = d_ {0}(n)b^{-1} + \cdots + d_ {L-1}(n)b^{-L} $

例子

例如，为获得十进制 van der Corput 序列，我们通过除以数 1 到 9 为 ( x / 10 )，然后我们改变分母到 100 来开始分割 ( x / 100 )。对分子，我们开始所有的两位数字数从 10 到 99，但以数字的后向序。结果，我们将给出以结尾数字为组的分子。首先，所有两位数字分子以 1 结束，这样下一个分子为 01, 11, 21, 31, 41, 51, 61, 71, 81, 91。然后分子以 2 结尾，为 02, 12, 22, 32, 42, 52, 62, 72, 82, 92。之后以 3 为结尾，…

这样，序列开始为

$ \{ \frac{1}{10}, \frac{2}{10}, \frac{3}{10}, \frac{4}{10}, \frac{5}{10}, \frac{6}{10}, \frac{7}{10}, \frac{8}{10}, \frac{9}{10}, \frac{1}{100}, \frac{11}{100}, \frac{21}{100}, \frac{31}{100}, \frac{41}{100}, \frac{51}{100}, \frac{61}{100}, \frac{71}{100}, \frac{81}{100}, \frac{91}{100}, \frac{2}{100}, \frac{12}{100}, \frac{22}{100}, \frac{32}{100} \} $

或以十进制表示

$ 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91, 0.02, 0.12, 0.22, 0.32, \ldots $

也可以用二进制表示

$ 0.1_ {2}, 0.01_ {2}, 0.11_ {2}, 0.001_ {2}, 0.101_ {2}, 0.011_ {2}, 0.111_ {2}, 0.0001_ {2}, 0.1001_ {2}, 0.0101_ {2}, 0.1101_ {2}, 0.0011_ {2}, 0.1011_ {2}, 0.0111_ {2}, 0.1111_ {2}, \ldots $

或对应的

$ \frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, \frac{5}{8}, \frac{3}{8}, \frac{7}{8}, \frac{1}{16}, \frac{9}{16}, \frac{5}{16}, \frac{13}{16}, \frac{3}{16}, \frac{11}{16}, \frac{7}{16}, \frac{15}{16}, \ldots $

van der Corput 序列中的元素（任意进制）形成单位区间中的一个紧密集。即，对 [0, 1] 中任意实数，存在一个 van der Corput 序列的子序列覆盖该数。它们在单位区间内有统一的分布

C 实现

double corput(int n, int base) {
  double q = 0;
  double bk = (double)1 / base;

  while (n > 0) {
    q += (n % base) * bk;
    n /= base;
    bk /= base;
  }

  return q;
}

Share

Prepare for Your Google Interviews: System Design

我们期望在前 20 分钟内你收集需求且开发一个初始的解决方案。沟通在谷歌是非常重要的，因此它是我们开发和构建我们产品的关键。在你的面试中，展示这些能力是很重要的。理解一个问题且设计一个解决方案都是面试过程的有价值的部分。我们想要你广开思路，我们不只是想要看到最后的答案。我们想要理解你如何思考的。谷歌是一个协作的工作场所，由团队计划和执行工程。这些团队需要一起工作，来解决大的，经常是不明确的问题。这些问题由多个有效的解决方案。所以，告诉我们你如何计划解决这些问题，且要问问题。记住，我们不是在寻找一个特定的回答。你在面试时解决的问题将是故意未明确说明的。我们让这些问题是开放的，因为实际问题需要你去深入挖掘。你将需要问明确的问题

在谷歌，我们每天处理全球化的数据和计算系统。我们的应用程序服务全球的用户。简单确认一个解决方案只是一个开始。解决方案必须是足够可扩展的来抵达广泛的观众，足够可靠在满足我们用户的需求，且高效使用我们的资源。在面试中，我们将看到你设计可扩展系统的能力。你需要保持在头脑中的问题包括：

  • 我们如何说明系统是可正常工作的？
  • 设计中有瓶颈吗？
  • 组件如何一起工作？
  • 我们如何提供优秀的服务给每个人？

在长时间内你设计的所有可容易地放入一个机器中。我们会给你一个大数据集，问你它如何分片到多个工作机器。或我们会呈现一个请求，其可在机器池中任意机器中，且问你确定最快的机器且丢弃其他。你也应该准备讨论系统组件属性比如延迟，吞吐和存储。我们想要看到这些属性的数值估计，比如系统可处理每秒多少次请求。也要准备提供清晰的调整，如何设计备份这些

我们的系统影响全球的用户，我们需要工程师具体且量化地解决实际世界中的问题。当设计时，你应该总是考虑实际且物理定律。你也应该对各种操作的成本和延迟有一般化的想法，比如读磁盘，读内存，本地网络往返，跨陆地网络。在面试时，你将有一个白板，你可使用它来估计运行你的系统需要的资源，或图形化你的设计。你应该知道工业解决方案范型比如数据分片，复制类型，前向写日志，分离数据和元数据存储，加载分布式

作为谷歌的系统设计师，你将需要确定补偿和折中。在面试中，我们将问你确定系统化的缺点且描述系统如何响应各种故障。我们想要你来设计补偿和折中，你可解释你的原因。你是否存储数据到磁盘且花费更少的钱来存储，代价是延迟的增加？或你把数据放在闪存盘里，你能够快速获取但成本高。这些问题会在面试中出现。我们寻找可考虑多个解决方案的系统设计师，提交一个后，继续迭代

现在你有聚焦的领域，这里有一些通用的最好实践可用在实际面试中。我们想要理解你如何思考，所以在面试过程中解释你的想法是重要的。我们不只评估你的技术能力，也看你如何解决问题。许多问题会故意设计为开放的来给我们看一个你如何解决技术问题的想法。我们鼓励你问问题来清楚细节。且我们都知道我们第一个解决方案可能不是最好的。这样，当你回答了一个问题，想想如何改进且让你的面试官知道你怎么思考的。最后，在纸上或在白板上练习。在面试过程中，你可能不能正常使用你访问的资源

这些是我们帮助你准备谷歌的系统设计面试的提示