对数算法

当我们的神经回路、行为特征甚至生理反应遵循对数性质时，在人工智能算法中使用对数优化难道不自然吗?当算法的执行时间与输入大小的对数成比例时，称为对数算法。

让我们用流行的O(log n)时间算法，即二分法检索，来解决一个有趣的问题(AGGRCOW)，以更新您的理解。此外，我们还将快速了解这个概念在机器学习和深度学习中的应用。

二叉树和二分法检索

在二分法检索中，我们反复将“排序数据”分成两半，直到我们只剩下一个元素，或找到搜索元素。

二叉树是一种数据结构，每个节点最多有两个子节点，一个在左边，另一个在右边。如果这样的树满足“二分查找属性”，即左节点中的所有元素都小于或等于根节点，并且右节点中的所有元素都大于或等于根节点，则称为“二叉搜索树”(BST)。

排序数组可以转换为BST数据结构，特定键可以递归或迭代搜索。

排序数组到二叉搜索树的转换

对数时间算法的优点

二分法检索在每一步都可以忽略一半的元素，这是它最大的计算优势。在BST中，我们可以选择节点的左子节点或右子节点，从而在每个步骤中完全丢弃一半的值。

线性搜索（10个步骤）与二分法检索（3个步骤）

O(log n)算法具有最小平均用例时间复杂度

由于二分法检索的概念是基本的，让我们仔细研究一下如何使用二分法检索来解决一个有名称为AGGRCOW的问题。稍后我们将探讨这个想法是如何在人工智能领域被借用的。

AGGRCOW 问题定义：

农夫约翰建造了一个新的长谷仓，有N个畜栏。畜栏沿直线设置。他的奶牛不喜欢这种谷仓布局，一旦放入畜栏就会变得咄咄逼人。为了防止奶牛互相伤害，他希望将奶牛分配到畜栏，以使其中任何两头奶牛之间的最小距离尽可能大。找到最大的最小距离。

a）输入和输出：

• 输入：牛栏位置数和奶牛数量
• 输出：最大的最小距离

b）分析：

• 奶牛应尽可能远离彼此，以免它们受到伤害。并且所选择的畜栏之间的距离应该相同。这被称为最大的最小距离。

c）见解：

• 对于给定值'x'，如果不能将所有奶牛保持在任何两头母牛之间的最小距离为'x'的畜栏中，则所有y> x都不可能。
• 逻辑上，一步中消除了一半的值（y> x）。这就是二分法检索的想法。
• 找到排序的畜栏之间的距离变得单调，零到最大的最小值。

d）使用二分法检索实现逻辑：

首先，我们采取明显的假设，即最大距离的上限和下限在第一畜栏和最后一畜栏之间。在每一步，我们将间隙减半并检查是否可以容纳奶牛数量以获得该间隙值。如果无法减半，则此值以上任何值都不可能，因此，在节点的左侧搜索间隙值。如果可以减半，那么最大间隙值应该在节点的右侧。因此，找到最大的最小距离归结为可能的间隙值的二分法检索。

e）Python中的优化编码：

stalls = list(map(int, input('Enter Stall positions: ').strip().split()))
cows = int(input('Enter no. of cows: '))
def isPossible(stalls, gap):
 marker = 0
 c = 1
 for idx, val in enumerate(stalls):
 if val - stalls[marker] >= gap:
 marker = idx
 c += 1
 
 if (c < cows):
 return False
 else:
 return True
 
def compute_largest_min(stalls, mingap, maxgap):
 
 mid = int((mingap + maxgap)/2)
 
 if (maxgap - mid <= 1):
 if isPossible(stalls, maxgap):
 return maxgap
 elif isPossible(stalls, mid):
 return mid
 elif isPossible(stalls, mingap):
 return mingap
 else:
 return -1
 
 if (isPossible(stalls, mid)):
 #if here, then largest min gap is between mid and maxgap
 return compute_largest_min(stalls, mid, maxgap)
 else:
 #if here, then largest min gap is between mingap and mid
 #Reason: if largest min gap = mid is not possible then,
 # gap > mid also will not be possible logically.
 return compute_largest_min(stalls, mingap, mid)
 
stalls = sorted(stalls)
maxgap = stalls[len(stalls)-1] - stalls[0]
print(compute_largest_min(stalls, 1, maxgap))

样本输出：

使用二分法检索，我们已将120个可能的步骤减少到6个步骤。

遍历= {10,5,7,8,9}

在AI中的应用

由于“搜索操作”在时间和空间上的复杂性更多的体现在图中，而不是树中，因此树在人工智能中更常用。

Graph中的循环导致重复的节点搜索（时间）或存储搜索节点（空间）

树型数据结构的应用具有多领域的综合应用，特别是机器学习和深度学习。

1.KD树：

KNN算法中最昂贵的步骤是查找点的K最近邻。因此，为了降低KNN算法的时间复杂度，采用了一种有效处理k维数据的数据结构kd-tree。

kd树是BST到k维空间的泛化。将k维空间递归划分为两个半空间。当点为二维(即k=2)时，我们可以构建一个点的x- y坐标作为交替序列的键的BST，如下图所示。

kd树相对于BST的主要优点是它支持范围搜索和最近邻搜索的有效实现。

• a：范围搜索：查找给定查询矩形中包含的所有点
• b：最近邻搜索：查找到给定查询点的最近点

Recursive space-partioning of 2d-tree

在最佳情况下，使用kd树，找到最近邻的比较次数从O（n）减少到O（log n）。此外，kd-tree适合高维和聚类数据。

2.决策树/随机森林/ GBDT

与基于几何的Logistic回归或基于实例的KNN算法相反，决策树是嵌套的if-else条件分类器，如下所示。

类标签是布尔值

在决策树（DT）中，我们计算每个特征的“信息增益”（IG），并在树的每个级别基于具有最大信息增益的特征对机器学习数据集进行分区。在构建DT之后，我们必须进行'k'比较（k =树的深度），以便在运行时找到类标签。

由于DT中的数据分割基于局部最佳阈值（IG），因此DTs可能并不总是平衡的。但是，在最好的情况下，对于平衡树，树深度将为O（log N）。

同样的想法也适用于更受欢迎的梯度提升决策树（GBDT）和随机森林（RF），因为基础学习者分别是浅层和深层决策树。

3.层次Softmax（深度学习）

Word2Vec算法，即CBoW和Skip-gram，都有数百万个权重需要训练。利用二叉树的概念，我们可以优化Word2Vec算法中最难的运算，即softmax。

在Softmax中，我们需要计算所有的终端，找到最可能的单词

如果vocab size = ' v '，则每个' v '激活单元返回每个单词对应的概率，其中选择概率最大的单词。但是我们不需要计算所有的概率，我们可以构建一个二叉树来在log (v)步骤中找到最大可能的单词。

将softmax函数描述为树

在二叉树的每个节点上创建一个二元分类器(sigmoid单元)，而不是创建一个v-class分类器。sigmoid单元的输出表示输出单词属于左节点还是右节点。因此，我们不需要8个softmax units，我们只需要3个binary softmax units。

随着人工智能领域从大脑的真实功能中获得越来越多的线索，对数算法将来会发现越来越多的应用。