beam search – 一个搜索策略

一个近似搜索策略,用于在候选可能中选择最好的结果 渣翻:https://hackernoon.com/beam-search-a-search-strategy-5d92fb7817f

一个常用例子,BS(beam search) 用于获得与机器翻译等价的结果。对于那些不了解机器翻译的人,也肯定知道 Google Translate。

这就是为啥要讲这个。这些系统都用 BS 技术来找到与结果最等价的翻译。阅读这个 Wiki 来了解相同文件的定义。

让我们讨论一下这个使用机器翻译案例的策略。如果你是一个喜欢研究现象背后原理的人,一定要读一下 google encoder-decoder 网络架构。这个东西我就不讲了,有很多人讲。例如,如果你不知道这个架构,看看这个 quora 上的回答。

一个视角

机器翻译模型可以被认为是一种 “条件语言模型”,对于…

让我们看一下…

BS B(beam 宽度) 是唯一一个调整翻译结果的超参。 B 在一般情况决定了,在每一步,要记忆的单词的个数,来变换概率。

不翻译了。。这里有更直接的结果

beam search 时在每一个时间点选择 beam_width 个最大的可能类别,然后在每个时间点 beam_width 个类别组成的空间里寻找整体概率最大的一条路径,得到最后得识别输出。而 greedy search 则直接在每个时间点寻找概率最大的类别,然后依次组成这个路径。也就是说,greedy search 是 beam_width=1 版本的 beam search。上图是 CTC 论文里 greedy search 示意图。

对于 CTC 的一个直观理解与解释

渣翻 https://towardsdatascience.com/intuitively-understanding-connectionist-temporal-classification-3797e43a86c

通过 连接主义时间分类 loss 以及编码操作

如果想用使用计算机识别文字,神经网络很好用。使用一些列 CNN 从序列中提取特征,使用 RNN 来传播需略的信息。它会输出字符得分,给每个序列元素,通过一个简单的矩阵表示。现在,有两个事情我们想要对矩阵进行处理。

  1. 训练:计算损失值来训练神经网络
  2. 推理:解码矩阵来获得图片中的字符

两个任务可以同时被 CTC 操作完成。对于手写数字系统的描述,可以参见图像 1.

我们更进一步看看 CTC 操作,并且讨论一下它如完成的,以及它背后的公式是如此巧妙。最后,我将会指点你来找到 Python 代码以及不复杂的公式,如果你感兴趣的话。

fig 1

为什么我们使用 CTC

当然我们可以创建一个数据集,这个数据集有文本行,然后指出每列属于哪一个字符,就像图 2 中展示的那样。然后,我们可以训练一个神经网络来输出每一列的得分。而然,对于这个简单的解法,这里有两个问题。

  1. 这个十分的耗时(以及无聊)来在字符层面上标注数据
  2. 我们仅仅能够得到字符的得分,因此还需要一些操作来获取最终的文本。一个简单地字符可以跨越多个位置,比如,我们得到 “ttooo”,是因为 “o” 是一个比较宽的字符。我们已经删除了多余的 “t” and “o”,但是,如果要识别的字符是 “too”,我们应该怎么办?如果删除了多余的 “o”,将会给我们错误的答案。我们应该如何处理呢?

CTC 解决了几个问题

  1. 我们只需要告诉 CTC loss function,文本在图像中出现了,因此我们忽略位置和宽度文中在图像中。
  2. 不需要更多的文本识别处理

CTC 如何工作的

就像是我们已经讨论的,我们不希望在图像的每一列标注数据(这曾经被我们成为时间步)。神经网络的训练将会被 CTC 损失函数所指引。我们只需要把数据矩阵给 CTC 函数,以及对应的真实值即可。但是它是怎么知道每一个字符出现的呢?他不知道。相对而言,它尝试了图片中所有的真实文本,以及计算了所有的加和。通过这个方式, This way, the score of a GT text is high if the sum over the alignment-scores has a high value.

编码文本

如何编码重复的文本曾经是一个问题。这个问题通过引入一个虚假字符来解决了(称为空,但是不要把它和真正的 space 混淆。)。这个特殊的字符被标记为 “-”,在下面的文本中。我们使用了一个聪明的编码策略来解决重复字符的问题。当编码一个文本的时候,我们可以随机加入许多空在任何位置中,当我们解码的时候,我们将会把的这些删除。但是,我们必须在重复字符串中加入空,例如 “hello”,如此一来,重复字符就不是问题了。

Let’s look at some examples:

“to” → “—ttttttooo”, or “-t-o-”, or “to” “too” → “—ttttto-o”, or “-t-o-o-”, or “to-o”, but not “too”

正如你所见,这些模式也允许我们简单的创建一些相同文本串的不同对取,比如 “t-o”, 以及 “too”,以及 “-to”,所有的表示都是同一个文本 “to”,但是通过对图片不同对其获得的。神经网络被训练于输出一个编码的文本(在神经网络的矩阵中编码)。

损失计算

我们需要计算每一个损失值,这个损失值是由图像核真实文本给出来训练 NN 的。你已经知道 NN 输出一个矩阵,包含一个得分,为每个文本在每个时间步上。一个小矩阵在图三中展示:有许多的时间步(t0, t1),以及三个字符(”a”, “b”, 以及 blank “-“).

此外,你已经知道,loss 是通过加和所有积分来进行计算的,通过这个方式,字符出现在图片的哪个位置不重要。

对于一个 alignment 的得分(或者 path;在文学中一般这么称呼)通过将相应的字符相乘。在上面的例子中,path”aa” 的得分是:0.4*0.4=0.16,”a-” 的得分是 0.4*0.6=0.24,”-a” 的得分是 0.6*0.4=0.24. 为了获得 GT 文本的得分,我们加和这个文本的所有 path 的得分。我们假设,GT 文本是 “a”,我们已经计算了所有长度为 “2” 的 path,分别是 “aa”,“a-”,“-a”,我们已经计算了这些 path 所有的得分,所以我们只需要把他们加起来,得到 0.4×0.4 + 0.4×0.6 + 0.6×0.4 = 0.64。如 GT 文本可能是 “”,我们可以看到只有一种相关的 path,那么就是 “–”,获得的得分是 0.6×0.6 =0.36.

如果仔细看,你已经发现我们计算了 GT 的可能性,但是不是 loss 值,而然,loss 知识概率的负对数。这个 loss 值是反向传播算法以及 NN 的参数更新使用的,我这里没有进行详细的讨论。

解码

当我们训练一个 NN,我们想要使用它来识别那些之前没有看到的图像。或者更多在更多的技术术语:我们想要计算,NN 输出的矩阵最可能是什么。你已经知道一个方法来计算给出文本的得分,但是现在,我们没有被给出任何文本,事实上,它正是我们正在寻找的文本。尝试所有可能的文本,如果他们只有很少的时间步以及字符,但是对于练习用例而言,这不可行。

一个简单而快速的算法,是最佳 path 解码,包含两个步骤:

  1. 它计算了最佳 path,通过获取最可能的每一个时间步的字符
  2. 首先删除重复的字符,然后删除 path 里面所有的空。这仍然表示了识别的文本。

正如 FIG4 所展示的,字符是 “a”,“b” 以及 “-”(空),一共有 5 个时间步。让我们应用最佳 path decoder 来处理这个矩阵。在 t0,最可能的是“a”,同样应用于 t1,t2. 空字符在 t3 是最可能的。最后,“b” 是 t4 时刻最可能的。这将给出我们一个 path“aaa-b”,我们删除了重复的字符,这将会返回“a-b”,然后我们删除 path 中的空,这给我们一个“ab”,作为我们输出的识别结果。

最佳 path 解析是,当容纳,仅仅是一个近似。构建样例容易给出错误的结果,比如用这个方法构建 FIG3,将会得到 “”,作为识别文本。但是,我们已经知道“” 结果的概率是 0.36,而 “a” 的概率是 0.64。而然,近似算法经常在练习的情景下给出比较好的结果。也有许多其他的比较好的 decoder,例如 beam-search,prefix-search 以及 token passing,这些关于语言结构的方法,都有利于提升结果。

结论以及展望

首先我们看得是,神经网络如何解决这个问题;然后,我们展示了 CTC 如何解决这些问题,然后,我们解释了 CTC 为啥能够工作,如何计算的 loss,以及如何解码 CTC 训练的 NN。

This should give you a good understanding of what is happening behind the scenes when you e.g. call functions like ctc_loss or ctc_greedy_decoder in TensorFlow. However, when you want to implement CTC yourself, you need to know some more details, especially to make it run fast. Graves et al. [1] introduce the CTC operation, the paper also shows all the relevant math. If you are interested in how to improve decoding, take a look at the articles about beam search decoding [2][3]. I implemented some decoders and the loss function in Python and C++, which you can find on github [4][5]. Finally, if you want to look at the bigger picture of how to recognize (handwritten) text, look at my article on how to build a handwritten text recognition system [6].

使用主动学习加速机器学习

一篇 medium 文章的渣翻

https://becominghuman.ai/accelerate-machine-learning-with-active-learning-96cea4b72fdb

让我们讨论一下主动学习。我相信这个方法可以极大的增速,以及减少许多机器学习工程的花费。这篇文章我将从两个部分说明这个问题。在第一部分,我给出了一个极高的层级的主动学习的说明,以及如何把它利用到机器学习工程中。在第二部分,深入到一个主动学习 demo 中。

第一部分

主动学习是如何工作的

让我们通过一个很简单的概览,来看看机器学习是如何工作地。

Repeat thousands of times and you get a trained model!

许多机器学习模型是巨大的猜疑机器——他们看了许多数据,计算出一个猜测的结果,检查他们的答案,微调一下,然后再试试。在许多数据之后,模型将会变得十分准确。

标记数据

主动学习

主动学习是一种方法,有时可以极大减少标记样本的数量。它通过专家标记样本来完成这个工作。

不使用全部的数据一次标注所有数据,主动学习优先处理那些让模型感到困惑的数据,并且仅仅需要好那些数据的标签。模型在小样本数据上进行训练,然后根据那些最令模型疑惑的数据,请求更多的标签。

通过优先处理那些最迷惑的样本,模型可以专注于提供一些最有价值的信息。这帮助模型训练的更快,并且让专家跳过那些对于模型帮助不是很大的数据。结果是,我们可以很大程度上减少标记样本的数量,并且我们仍然得到一个很好的模型。这意味着节省时间和金钱!

第二部分

MNIST 例子

让我们看一下实际的主动学习样本。

使用文档良好的 MNIST 数据集,以及经典的 Tensorflow 卷积神经完了过。一个聪明的模型和架构可以做的更好,但是我们想要直接使用这个模型。

MNIST 数据集是公开可获取得的数据集,包含了大量的手写数字,以及数值标签。它经常被使用于机器学习入门教程,因为他的标记数据质量很高,并且简单地模型也可以表现的不错。

设计

这个工程包含两个部分:

  1. 在训练模型的时候,模仿主动学习
  2. 在严格的模型上确定主动学习的效率

训练一个模型

我们使用 mini-batch 训练。这个模型仅仅在训练集中,看一个小数量样本,通过小数量样本进行学习。

这里,我们可以看到一个正常的(非 – 主动学习)的训练过程,模型在一个随机结合的小批次上进行训练。每在小 – 批次训练中的迭代,都在测试记上运行模型(不作为训练集的一部分)来追踪模型是怎样增长的。我提供了准确率以及 cross-entropy 损失(就像是平均误差一样)。在这里,每一个小批次有个 10 个例子,我运行了 2000 批次(20000 个标注)。

对于这个分类任务,我们试图把 0~9 的数字进行分类,意味着随机猜测仅有 10% 的准确率。简单的神经网络已经做的不错了。

模拟主动学习

获得主动学习结果有一点小技巧。我们不在数据集中的随机选择数据,相反,模型将会评估许多在训练集中的例子,然后将置信度最小的数据作为小 – 批次(在这个工程中,我查看了 1000 个在训练集中的随机样本,来确定置信度至少为 10)。在那里,模型将会像处理小 – 批次数据一样处理进行训练过程,它将会重复这个过程来更新模型。就像是在 “非 – 主动学习” 样例中,每经过一些迭代,我将会在测试记上运行模型,追踪模型的训练过程。

有许多很好的文章来说明如何实现 主动学习。在这里,我仅仅想要把事情做的简单一些。这个模型使用一个 “softmax” 来生成概率——在这个例子中,是数字 0~9。” 置信度” 通过选择” 最大的概率减去最小的概率 “。模型越自信,这个差值越大。(置信度不意味着准确率)。

主动学习过程,使用了那些置信度比较低的数据,并且在上面进行训练。并且当然的,当模型改变了,它的置信度也一样会改变。

MNIST 数据集已经有了我们需要的标签,但是这个过程,在 mini-batch 中,模拟询问了专家,来获取标签。在通常情况下,专家会随机被提问,来获取数据。在主动学习的例子中,模型会选择那些数据,希望专家进行标注。

让我们来看一下主动学习结果 VS 一般的结果。注意 y-axis。

通过 mini-batch(8000 标签),主动学习的方法匹配了 2000 mini-batch(20000label)数据的准确率。所以,使用一接近一半的数据,主动学习可以达到同样地准确率。

倾斜数据的二分类任务

主动学习可以大施拳脚的地方是,数据的强烈偏差。

训练一个模型的时候,重要的不仅仅是标记的数据,还有不同数据的,合理的不同表示。如果我们尝试在 MNIST 上训练一个模型,而没有任何包含 3 的数据,收集多少数据并不重要,重要的是我们的模型不可能区分 3。如果我们仅仅含有一小部分 3,我们仍然会面临一个问题,就是模型仅仅会准确的区分其他数字,也就是那些有更好表达的数据。

数据的偏差,不均衡对于 MNIST 数据集中不存在,但是它的确是一个真实世界的问题。如果我们训练一个模型来识别 CT 中的脑瘤,大多数 CT 图像不会含有肿瘤图像,所以标注 “肿瘤” 的数据将会远不均衡于 “非肿瘤” 的样本数据。因为主动学习优先考虑的例子不那么自信,因此主动学习可能有助于识别 “异常 “或代表性不足的数据并且确定优先级。

我们在 MNIST 上模拟一下 skew 的问题。重新定义 MNIST 的问题,定义成 3 或者非 3,然后,非 3 的数据有 90%,而 3 的数据仅有 10%。所以愚蠢的策略将会在” 非 3“上达到 90% 的准确率,让我们看一下主动学习是如何做的:

在使用主动学习的时候,在 500mini-batch(5000labels)我们就达到,甚至更好地准确率。相比之下,cross-entropy 算法,通过 2000 mini-batch。主动学习减少了 4 倍的数据量。主动学习是如何做到的?看下图。

后续

未完,后面翻不翻看心情。。也不知道工业界玩 active learning 的多不多。

批量转换ipynb

一段脚本将ipython notebook转化为py文件。

It’s hard to make notebook file to import so it’s important to make notebook importable.

#!/usr/bin/env python
# coding: utf-8
import nbformat
from nbconvert import PythonExporter
def convertNotebook(notebookPath, modulePath):
  with open(notebookPath) as fh:
    nb = nbformat.reads(fh.read(), nbformat.NO_CONVERT)
  exporter = PythonExporter()
  source, meta = exporter.from_notebook_node(nb)
  with open(modulePath, 'w+') as fh:
    fh.writelines(source)
def trans_all():
    import os
    path = '.'
    list_dirs = os.listdir(path)
    for filename in list_dirs:
        if filename.endswith('.ipynb'):
            print(filename, filename[:-5] + 'py')
            convertNotebook(filename, filename[:-5] + 'py')
trans_all()