INCOMING TRANSMISSION

二叉树结构 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None 递归 时间复杂度： \(O(n)\) ， \(n\) 为节点数，访问每个节点恰好一次。 空间复杂度：空间复杂度： \(O(h)\) ， \(h\) 为树的高度。最坏情况下需要空间 \(O(n)\) ，平均情况为 \(O(logn)\) 递归1: 二叉树遍历最易理解和实现版本 class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] # 前序递归 return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) ...

48. 旋转图像 题目 给定一个 \(n × n\) 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]] 示例 2： 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] 提示： n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 题解 这是一个经典的矩阵操作问题。要在原地（In-place）将图像顺时针旋转 90 度，我们可以利用矩阵的几何性质。 最直观且易于实现的方法是将...

三维深度学习简介 多视角（multi-view）：通过多视角二维图片组合为三维物体，此方法将传统CNN应用于多张二维视角的图片，特征被view pooling procedure聚合起来形成三维物体； 体素（volumetric）：通过将物体表现为空间中的体素进行类似于二维的三维卷积（例如，卷积核大小为5x5x5），是规律化的并且易于类比二维的，但同时因为多了一个维度出来，时间和空间复杂度都非常高，目前已经不是主流的方法了； 点云（point clouds）：直接将三维点云抛入网络进行训练，数据量小。主要任务有分类、分割以及大场景下语义分割； 非欧式（manifold，graph）：在流形或图的结构上进行卷积，三维点云可以表现为mesh结构，可以通过点对之间临接关系表现为图的结构。 点云的特性 无序性...

概括 这篇文章将卷积比较自然地拓展到点云的情形，思路很赞！ 文章的主要创新点：“weight function”和“density function”，并能实现translation-invariance和permutation-invariance，可以实现层级化特征提取，而且能自然推广到其deconvolution的情形实现分割，在二维CIFAR-10图像分类任务中精度堪比CNN（表明能够充分近似卷积网络），达到了SOTA的性能。 缺点：每个kernel都需要由“kernel function”生成，而“kernel function”实质上是一个CNN网络，计算量比较大。 思想 察觉到：二维卷积中pixel的相对centroid位置与kernel vector的生成方式有关。 以二维卷积为例说明一下如何将卷积拓展到点云。这里只考虑使用一个kernel在一个location的一次卷积操作。 对于二维图像，我们可以将图像的pixels看作是一个点，那么图像就是整齐排列的点阵。每个point都有维度为 \(C_{in}\)...

Hough Voting 本文的标题是Deep Hough Voting，先来说一下Hough Voting。 用Hough变换检测直线大家想必都听过：对于一条直线，可以使用 \((r,θ)\) 两个参数进行描述，那么对于图像中的一点，过这个点的直线有很多条，可以生成一系列的 \((r,θ)\) ，在参数平面内就是一条曲线，也就是说，一个点对应着参数平面内的一个曲线。那如果有很多个点，则会在参数平面内生成很多曲线。那么，如果这些点是能构成一条直线的，那么这条直线的参数 \((r,θ)\) 就在每条曲线中都存在，所以看起来就像是多条曲线相交在 \((r,θ)\) 。可以用多条曲线投票的方式来看，其他点都是很少的票数，而 \((r,θ)\) 则票数很多，所以直线的参数就是 \((r,θ)\) 。 所以Hough变换的思想就是在于，在参数空间内进行投票，投票得数高的就是要得到的值。 文中提到的Hough Voting如下： A traditional Hough voting 2D detector comprises an offline and an online step....

生成器 什么是生成器？ 通过列表生成式，我们可以直接创建一个列表，但是，受到内存限制，列表容量肯定是有限的，而且创建一个包含100万个元素的列表，不仅占用很大的存储空间，如果我们仅仅需要访问前面几个元素，那后面绝大多数元素占用的空间都白白浪费了。 所以，如果列表元素可以按照某种算法推算出来，那我们是否可以在循环的过程中不断推算出后续的元素呢？这样就不必创建完整的list，从而节省大量的空间，在Python中， 这种一边循环一边计算的机制，称为生成器：generator 生成器是一个特殊的程序，可以被用作控制循环的迭代行为，python中生成器是迭代器的一种，使用 yield 返回值函数，每次调用 yield 会暂停，而可以使用 next() 函数和 send() 函数恢复生成器。 生成器类似于返回值为数组的一个函数，这个函数可以接受参数，可以被调用，但是，不同于一般的函数会一次性返回包括了所有数值的数组，生成器一次只能产生一个值，这样消耗的内存数量将大大减小，而且允许调用函数可以很快的处理前几个返回值，因此生成器看起来像是一个函数，但是表现得却像是迭代器 python中的生成器...

列表和元组总结 列表和元组都是 一个可以放置任意数据类型的有序集合 ，他们有以下共同点 列表和元组中的元素可以任意，并且都可以嵌套。 列表和元组都支持索引，且都支持负数索引，-1表示最后一个元素，-2表示倒数第二个元素 列表和元组都支持切片操作 都支持in关键词 都可以使用 .index() 、 .count() 、 sorted() 和 enumerate() 等方法 两者之间的相互转换，list()和tuple() 但是他们也是有区别 列表是动态的，长度大小不固定，可以随意地增加、删减或者改变元素（mutable） 元组是静态的，长度大小不固定，无法增删改，想要对已有的元组做任何“改变”，就只能开辟一块内存，创建新的元组 列表和元组存储方式的差异 由于列表是动态的；元组是静态的，不可变的。这样的差异，势必会影响两者存储方式。我们可以来看下面的例子： >>> l = [1, 2, 3] >>> l.__sizeof__() 64 >>> tup = (1, 2, 3) >>> tup.__sizeof__() 48...

概述 python采用的是 引用计数 机制为主， 标记-清除 和 分代收集 两种机制为辅的策略。 引用计数 Python语言默认采用的垃圾收集机制是『引用计数法 Reference Counting 』，该算法最早George E. Collins在1960的时候首次提出，50年后的今天，该算法依然被很多编程语言使用。 『引用计数法』的原理是：每个对象维护一个 ob_ref 字段，用来记录该对象当前被引用的次数，每当新的引用指向该对象时，它的引用计数 ob_ref 加 1 ，每当该对象的引用失效时计数 ob_ref 减 1 ，一旦对象的引用计数为 0 ，该对象立即被回收，对象占用的内存空间将被释放。 它的缺点是需要额外的空间维护引用计数，这个问题是其次的，不过最主要的问题是它不能解决对象的“循环引用”，因此，也有很多语言比如Java并没有采用该算法做来垃圾的收集机制。 引用计数案例 import sys class A(): def __init__(self): '''初始化对象''' print('object born id:%s'...

引言 强化学习中，找到最优策略是核心目标。本文详细介绍三种能够找到最优策略的基础算法： 价值迭代、策略迭代和截断策略迭代 。这些算法属于动态规划范畴，需要系统模型，是后续无模型强化学习算法的重要基础。 在强化学习的发展路线中，这些算法处于"基础工具"到"算法/方法"的过渡阶段，是从"有模型"到"无模型"学习的重要桥梁。 价值迭代（Value iteration） 价值迭代算法 基于收缩映射定理求解贝尔曼最优方程 。其核心迭代公式为： \[\begin{equation}v_{k+1} = \max_{\pi \in \Pi} (r_\pi + \gamma P_\pi v_k), k = 0, 1, 2, ...\tag{1}\end{equation}\] 根据收缩映射定理，当 \(k \to \infty\) 时， \(v_k\) 和 \(\pi_k\) 分别收敛到最优状态值和最优策略。 每次迭代包含两个步骤： 策略更新步骤 （policy update step） ：找到能解决以下优化问题的策略 \[\pi_{k+1} = \arg\max_\pi (r_\pi +...

引言与背景 随机逼近（Stochastic Approximation）是一类用于求解寻根或优化问题的随机迭代算法，其特点是不需要知道目标函数或其导数的表达式。 随机逼近的核心优势在于： 能够处理带有随机噪声的观测数据 不需要目标函数的解析表达式 可以在线学习，每获得一个新样本就更新估计值 均值估计问题 考虑一个随机变量 \(X\) ，其取值来自有限集合 \(\mathcal{X}\) 。我们的目标是估计 \(E[X]\) 。假设我们有一个独立同分布的样本序列 \(\{x_i\}_{i=1}^n\) ，那么 \(X\) 的期望值可以近似为： \[E[X] \approx \bar{x} = \frac{1}{n}\sum_{i=1}^n x_i\] 非增量方法与增量方法 非增量方法 ：先收集所有样本，然后计算平均值。缺点是如果样本数量很大，可能需要等待很长时间。 增量方法 ：定义 \[w_{k+1} = \frac{1}{k}\sum_{i=1}^k x_i, k = 1, 2, ...\] 可以推导出递归公式： \[{w}_{k + 1} =...

引言与背景 蒙特卡洛方法是强化学习中的重要算法类别，它标志着从基于模型到无模型算法的转变。这类算法不依赖环境模型，而是通过与环境的直接交互获取经验数据来学习最优策略。 蒙特卡洛方法在强化学习算法谱系中处于"无模型"方法的起始位置，是从基于模型的方法（如值迭代和策略迭代）向无模型方法过渡的第一步。 无模型强化学习的核心理念可以简述为： 如果没有模型，我们必须有数据；如果没有数据，我们必须有模型；如果两者都没有，我们就无法找到最优策略。在强化学习中，"数据"通常指智能体与环境交互的经验 。 均值估计问题 在介绍蒙特卡洛强化学习算法之前，我们首先需要理解均值估计问题，这是理解从数据而非模型中学习的基础。 考虑一个可以取有限实数集合 \(X\) 中值的随机变量 \(X\) ，我们的任务是计算 \(X\) 的均值或期望值： \(E[X]\) 有两种方法可以计算 \(E[X]\) ： 基于模型的方法 ：当已知随机变量的概率分布时，可以直接根据期望值的定义计算： \[E[X] = \sum_{x \in X} p(x) \cdot x\] 其中 \(p(x)\) 是 \(X\) 取值为 \(x\)...

引言 DDPG同样使用了Actor-Critic的结构，Deterministic的确定性策略是和随机策略相对而言的，对于某一些动作集合来说，它可能是连续值，或者非常高维的离散值，这样动作的空间维度极大。如果我们使用随机策略，即像DQN一样研究它所有的可能动作的概率，并计算各个可能的动作的价值的话，那需要的样本量是非常大才可行的。于是有人就想出使用确定性策略来简化这个问题。 作为随机策略，在相同的策略，在同一个状态 \(s\) 处，采用的动作 \(\pi_\theta(a|s)\) 是基于一个概率分布的，即是不确定的。而确定性策略则决定简单点，虽然在同一个状态处，采用的动作概率不同，但是最大概率只有一个，如果我们只取最大概率的动作，去掉这个概率分布，那么就简单多了。即作为确定性策略，相同的策略，在同一个状态处，动作是唯一确定的，即策略变成 \[a = \mu(s, \theta)\] 所以DDPG基于确定性策略梯度(DPG)算法，结合了DQN的成功经验。 使用回放缓冲区中的样本进行离策略训练，以减少样本之间的相关性 使用目标Q网络在时序差分更新过程中提供一致的目标...