Latex Maths

Wednesday, March 25, 2015

什么是张量?(What are tensors?)

向量 = vector
向量空间 = vector space

两个向量空间 U, V 之间的线性变换,可以用 matrix 表示。

如果 U 的维数是 m,V 的维数是 n,则 $T: U \rightarrow V$ 的矩阵形式是 $m \times n$。

矩阵应该正确地理解为: 两个向量空间之间的线性变换。  矩阵只是线性方程组简写;  是「线性」这性质 逼使 这些变换成为矩阵。

张量

张量是 双线性变换 (bi-linear form) 的 universal form (万有形式)。  首先要了解什么是 bi-linear form,然后了解什么是 universal form。


Bi-linear form

Linear map (or transformation) 的意思是,一个由向量空间 U 到 V 的变换,服从:

$T: U \rightarrow V$

$T(v_1 + v_2) = T(v_1) + T(v_2)$

$T(k v) = k T(v) $

Bi-linear map 是 linear map 的推广,由向量空间 U,V 到 W 的变换,使其对 U 和对 V 也是线性变换:

$T: U \times V \rightarrow W$

$T(a v_1 + b v_2, u) = a T(v_1, u) + b T(v_2, u)$

$T(v, a u_1 + b u_2) = a T(v, u_1) + b T(v, u_2)$


Universal form

Universal form 用来表达某种结构的「最一般形式」,这个 idea 来自 category theory。

In our case,首先考虑两个向量空间之间的 tensor product,⨂:


那 $\times$ 代表 Cartesian product,即是 U,V 里面各取一个向量的任意组合。

By definition,那 tensor product 当然是 bi-linear 的。

但这时,如果有另一个 bi-linear map 射向 X:


注意,这 bi-linear map 未必是 tensor product,它只需要是任何 bi-linear map。 

而我们要求存在第三个唯一的 map,通常用 ! 号标记:



它使得「从 U x V 到 W 再到 X」,和「从 U x V 直接到 X」是一样的。  换句话说,就是这个由箭头表示的 diagram 是「可交换的」,即 "commutes" 。

实际的意思,是因为那 tensor product 保存了所有关於 bi-linear forms 的「资讯」,所以由 W 可以「重构」任何 U,V 之间的 bi-linear maps。  而且,这个万有形式是最 minimal 的,没有多馀的重复,所以只能有一个 unique map 由 W 射向 X。

所以说: tensor product 是所有 bi-linear forms 的 universal form

Bi-linear maps 可以有很多例子,但它们未必是 ⨂ 的模型 (models)。  例如: 两个向量的 inner product、cross product、两个矩阵的 matrix product、两个复数的乘积、 都是 bi-linear 的,但它们都不是 tensor product 的模型,理由是因为它们把双线性变换后的资讯萎缩了 (collapsed)。  但两个矩阵的 Kronecker product 是 tensor product,还有另一个模型是最常见的,利用 dual space V* 来描述。 

关於张量的代数,还有很多特性,但其抽象意义就是这个。  我暂时还没有学懂张量的详细性质,这里只能简介。


Remark:


最后解释一下:

两个向量空间的 direct sum 就是它们的 笛卡儿 乘积 U x V。  如果 U 是三度空间,V 是两度空间,则 U x V 有 3 + 2 = 5 度,它的 vectors 是像: $(v_1, v_2, v_3, u_1, u_2)$ 那样的元素。

但在张量积的空间 (tensor product space),$U \otimes V$ 的度数是 3 x 2 = 6。  一般来说它的度数可以大很多。  为什么张量积的空间可以大过两个向量空间的笛卡儿积?  那是因为我们在谈论两个空间之间的变换的空间。  如果我们考虑非线性变换(例如多项式变换 )、或是可微分变换,那些空间甚至是无穷维的!


Reference:

Guo, Hongyu 2014:  Modern mathematics and applications in computer graphics and vision  这本书很易懂 ,我從這書中抄了一些內容 :


Monday, March 16, 2015

什么是遗传/进化算法? (What are evolutionary algorithms?)

这是基於 进化论 而启发出来的一种很特别的 机器学习 技巧。  我最近渐渐明白到它可能是破解 strong AI 的关键。  Ben Goertzel 和我见面的谈话中也特别注重这一方向。  原来 Alan Turing 很早就看到 进化 和 machine learning 之间有明显关系,而现时机器学习的一个很有名的研究者 Leslie Valiant 也在新书 (English version) 中谈论这课题。

进化论


首先,要理解什么是进化论。  举例来说,假设某只动物的基因变异 令牠比同伴有更锋利的爪和牙齿,那么那牠就能吃到同伴吃不到的食物,也能抢到更多异性去交配。  久之,牠的同伴会较少后裔、甚至绝种,而牠的后裔则会越来越强盛。  这就是「物竞天择 适者生存」。

人类的情况有些不同,因为人类有文化 (意即靠语言传授下来的那些知识),所以有些优点不是纯粹由基因可以看出来。  说到这个问题很具争议性,因为涉及优生学等道德议题。  人们喜欢举反例,例如说『这个男生长得不好看 却有很多女朋友』等等,我不想扯得太远。  想想看,人类最强烈的感情,莫过於找不到伴侣传宗接代,而我们得不到异性的青睐 就会很痛苦,或者看到别人有更多「资源 resource」会妒忌,这些都是进化很有力的证据。 人类的感情通常可以用进化解释,这科目叫 evolutionary psychology (进化心理学)。

我个人认为,竞争是生物界以至人类社会的基本状况,我们必须接受并习惯它。  人类在商业、战争、体育、文艺、甚至下棋也是在竞争。   「天行健 君子以自强不息」,那是很好的勉励。

进化学习

以前说过,机器学习的目的就是要在浩瀚的 假设空间 (hypothesis space) 中寻找那些能正确地解释现实的语句。  例如婴孩可能用「有胡子就是爸爸」 来解释身边出现的人。

问题是假设空间太大,我们如同「在禾秆推里找一只针」,单靠 brute force 不是办法。

进化算法就是在很大的空间里 寻找某个 最佳答案 (optimal solution) 的一个很强的技巧。 它把需要寻找的 candidates 模拟成一个「人口」population,任由这些 candidates 在某个人工的环境下竞争, 然后,每次选取得分最高的一小撮样本,让它们「交配」,即 基因重组 (genetic recombination),那样产生新一批的  candidates, 如此逐步推向越来越优秀的 solutions。

举个例子,研究者用进化算法进化出一些电子电路,例如用於音响的滤波器 (filter) ,其 performance 甚至比人手设计的还要优越。  而且,那电路很不规则而且难理解,人们不知道它是如何运作的,有些部分甚至有多馀的元件存在。  那是因为进化的过程中,有时一些表面上没用的「器官」在组合之后或许变有用,所以进化的结果也常保留很多「废物 junk」。

我就是想用这方法去写 Genifer 的学习功能(我们要进化的 candidates 就是那些逻辑句子 logic formulas)。


Algorithm


具体的算法怎样?


  1. 初始时,预备一个 population,可以是随机产生的。
  2. 对每个 candidate 进行 估值 (evaluation),即是让这个 candidate 在人工的世界里生存。  例如我们测试它在所需的功能的表现如何。  那计分的方法叫 objective function 「目的函数」。
  3. 选取表现最好的 N 个 candidates,进行 变种 mutation重组 recombination。  变种是作用在单个 candidate 上的,重组则需要一对 candidates。  那就涉及到我们怎样将设计空间的元素表示为「基因」,於是有所谓 表述 (representation) 的问题。  这编码是要由研究者设计的。
  4. 在评分的时候,可以容许那些 candidates 在环境中互相合作亦同时竞争,那叫 cooperative evolution。   我觉得 Genifer 有需要用这方法,因为在知识库中的每个知识片段,是要和其他知识互相作用,那逻辑系统才能推导出有意思的结果。  

这本书(作者的网站免费提供在线阅读)深入浅出地介绍了几个「nature-inspired」算法:


例如这个 基因算法 的程式,用 Ruby 写成,只需短短一页。


实习


那个例子叫 "OneMax",每个个体是一串 0 和 1 的字串,目标是全部变成 "1"。

这个例子特别简单,因为「基因」就是个体的 显形 (phenotype),省略了 基因表述 (gene expression) 这步骤,便於学习。

实际运行时,发生了有趣的现象。  我先试 Ruby,然后把它翻译成 Scala,但奇怪地 Scala 版本的运行没有收敛到完美的结果,而 Ruby 版本很快就达到了。

我把 Ruby 和 Scala 进化的两个 populations 用图像显示出来,每一横列是一个个体。  第一片段是 Ruby「正常」的进化(到结尾时已经进化出第一个完美的纯 "1" 个体):


第二个是我写的 Scala 「不正常」进化:


可见在病态版本,那些孩子逐渐变成一模一样,而且每个也有同样的缺陷(因而显示成垂直线) 。

为什么呢?  Debug 了整整两天,才发现一个把 0 写作 1 的错误,令到那个 point mutation 的函数形同虚设,亦即是说 病态版本 根本缺乏 point mutations。

那是一个非常有启发性的 bug,使我学到了,单是 sexual reproduction 还不能做到高效率的进化,原来个体的 point mutations 也有关键的重要性,而我一直误以为 有性生殖 是产生 多样性 (diversity) 的唯一途径。  我依稀记得文献里曾提及这点,但不记得了。  有趣吗?  :)