代数结构

这篇 wikipedia 讲得还是很清楚的,当年学数学的时候怎么就没这种资料好生的建立起一些宏观的概念呢?

这里列一些正在用和常见的代数结构。

简单结构(无两元算子)

  • set 集合,就这个东西就能写本集合论之类的书了
  • pointed set,也是集合,但其中存在一些特殊的元素,比如定义自然数集合需要 0 和 1,这就是一个 pointed set
  • unary set,包括一个一元运算的集合,比如 boolean 与非运算
  • pointed unary set,整数集合与取相反数这个运算

类似群的结构(一个两元算子)

  • magma/groupoid:集合与二元运算,仅要求二元运算具有 closure
  • semi-group,所谓“半群”指具有结合律的 magma
  • monoid 指具有单位元(幺元)的半群
  • group 群指可取逆的 monoid
  • Abelian group 阿贝尔群是具有交换律(commutative)的群
  • semilattice 半格,二元运算不仅仅具有交换律还是幂等(idempotent)的
  • quasi-group 拟群(其实已经不算是 group-like 了),具有“除法”的半群

这里提一句 monad 这个概念可以看出它拥有closure、结合率、幺元因此是 monoid 的特殊情况,换言之是定义在 endofunctor 上的 monoid

类似环的结构(两个两元算子)

通常这两个运算会和 + 和 * 比较,与 groupoid 类似,ringoid 指在这两个运算下闭包的结构。

  • semi-ring 半环,要求在两个运算下都是 monoid,其中一个(加法)要求具有交换律,(加法)单位元(0)对另一个运算(乘法)满足 0x = x0 = 0,(乘法)另一个运算对前者满足左右分配率(distributive law)
  • near ring,去掉半环中加法的交换律
  • ring 环是加法下为 Abelian group 的 semi-ring,也就是增加了可逆性
  • Lie ring 李环是 ringnoid,要求加法下为 Abelian group,乘法满足 Jacobi identity
  • boolean ring 是一个交换环,且乘法幂等
  • field 域是一个环,且乘法除去加法零元外具有可逆元
  • Kleene algebra(研究 regular expression 的人应该比较熟悉这个)除去它本身是加法幂等的半环以外,另外有 Kleene star 这个一元操作
  • *-algebra 是具有 * 这个一元操作的环

注意这里出现了 algebra,一般 algebra 定义在 field 上,可以看成是 field 上的线性空间(linear algebra 就是研究实数域上的 algebra,其实也有复数域的,对应辛几何什么的)。但是这个 algebra 的概念可以扩展到一般的环上。

类似格的结构(两个或更多的二元算子)

这种结构里面引入了 meet/join 运算,实际上是对偏序集取 supremum 和 infimum,但因为是偏序关系这两个运算不是一定能获得值的。在格结构里面,一般要求这两个操作满足 absorption law(吸收律)。

  • lattice 是 join semi-lattice 且 meet semi-lattice,* semi-lattice 就是指 semi-lattice 在该操作下任意一个 pair 都存在结果
  • complete lattice,是个 lattice 但更强的是任意集合上都存在 supremum 和 infimum
  • complemented lattice 带补操作的 lattice
  • modular lattice 满足 modular identity,特例之一是 distributive lattice,如果加上 complement 就是 boolean lattice 了

算术

无限集合上定义了加法和乘法的结构,如 Robinson arithmetics 和 Peano arithmetics,似乎用得比较多的是后者。

——————
And Jacob did separate the lambs, and set the faces of the flocks toward the ringstraked, and all the brown in the flock of Laban; and he put his own flocks by themselves, and put them not unto Laban’s cattle.

Advertisements
代数结构

初识 monad

搞 functional programming 的人最终都会接触到 monad 这个概念,其实这是一个来自范畴论(后面有机会也来学习一些基本的概念,这个部分很早就听说了,但是却没看懂)的概念,虽然范畴论里面也有 monad 这样一个名词,但这里讲的却仅仅是其一个特殊情况,我们在后面看看究竟是啥关系。

在编程语言里面,monad 这样一个概念也被认为是 programmable semicolon,我们知道 imperative programming language 诸如 C/C++ 和 Java 通常以分号结束一个语句,你也可以将其看成将语句 chain 起来。所谓 programmable semicolon 就在这个意义上,通过 chaining expression 获得类似 pipeline 的行为,但是我们知道 imperative programming 里面的分号并没有能力将前后的语句真正 chaining 起来,这里是的确赋予了程序员这个能力。

形式上解释 monad 需要一个 type system,monad 其实是一种“construction”(代数结构),它在此 type system 建立一类特殊的类型(monadic type),那么结合某种语言如 scala 来说,scala 本身的 type system 里面我们通过某种方式建立一类类型(很显然常用的手段需要 generics),它需要以下三点要求(我们以 Option 这个 monad 为例):

  • type constructor,对应每一个 type system 的类型,对应的 monadic type 是啥,很简单的做法就是使用泛型表示,比如 Option[T] 就表示了一个 monad type constructor
  • unit 映射将 type system 某个 type 的对象映射成为 monadic type 里的成员,比如 val t: T,那么 Option 需要的就是一个将 t 映射成为 Option[T] 的函数
  • binding 是一个将给定的 monadic type 映射成为另一个同类的 monadic type 的函数,它还需要一个从前者的 type 到后者 type 对应的 monadic type 的映射函数,如果写成一个 pure function 这是一个两元函数,如果为 monadic type 本身提供“成员函数”,这就成为了一个一元的函数。仍然以 Option 为例,简言之我们需要一个 Option[T] 到 Option[U] 这样一个操作,操作需要一个参数 t: T => Option[U]。

有了这三个基本的东西之后,我们要求他们满足以下定律(是否觉得跟定义群、环之类的很像了?):

  • 结合率(associtivity):binding 满足结合率,如果记 m 为 monadic type M[T] 的实例,给定一个 f: T =>  M[U] 和 g: U => M[W],且 . 为 binding,(m . f) . g == m . (t: T => f(t) . g)
  • unit 映射满足 unit (t) . f = f(t) 与 m . unit = m,这也就是说 unit 映射类似一个单位元,任意类型的实例被其映射到 monadic type 里面的赋值映射,另一方面因为这个映射可以看成是 binding 的定义域里面一个,binding 对其操作后仍然回到原先的 monadic type 实例自身。如果把 binding 理解成为类似乘法的一个运算,unit 就是这个里面的 1

结合 Option 来说,满足以上条件的映射:

  • unit 映射是 t: T => Success (t)
  • binding 就是其对应的 flatMap

可以很容易的验证这几点。这告诉我们在 scala 里面普遍存在的这类操作并不是偶然,这类操作的存在使得我们可以 chaining 各种操作,除了容器类,前面还介绍了有 Try(尽管严格来说这并不是 monad)。实际上还有一类定义 monad 的方式,他们使用 fmap (将 T=>U 映射到 M[T] => M[U])和 join(类似 flatten),这里不再赘述。

那么 monad 这类结构除了以上 Option/Maybe、Collection 还能处理一些什么样的问题呢?

  • writer monad,为每步 function 调用附加一个 side effect,如记录 log,比如将 T 映射到 M[T] = Pair[T, String],做 flatMap 时 (f: T => M[U]) val (u, second) = f (first) ; (u, this.second + second)
  • identity monad,也就是 M[T] 还是 T
  • state monad,如果令 S 表示状态的类型,对应的 monad 类型为 M[T] = S => (T, S),即表示一个函数类型,将给定状态映射成为返回值 T 和下一个状态,这里的 unit 是 unit (t) = s: S => (t, s),做 flatMap 时相当于将实际计算放在 f 中,返回 f(t) 的是类似状态迁移的函数(如果计算给定,S => (g(t), S) 中 g(t) 给定),这样一个 monad 可以让程序员为计算过程附加任意一个状态类型,参看这里
  • environment monad 也称 reader monad,作用在于为计算提供一个共享的上下文环境,对应的 monad 类型为 M[T] = E => T,其中 E 是表示上下文的类型,对应的 unit (t) = e: E => t,ms 可以用来替换掉 IoC container 实现 DI,见这里
  • continuation monad 传说中实现 call/cc 的一个 monad,例子见这里

for comprehension 与 do notion

scala 里面提供了 for comprehension 本质上是对以上 monad 结构的应用,而这其实是广为 functional programming 人士所知的 do notation 的实现。通过 for 来操纵 monad 可以大大简化嵌套 flatMap 这类操作,这也很自然的将我原先 for 似乎就是类似对 iterable 做的 syntactic sugar 进行了纠正。不过上面提到的几种 monad 了解甚少,需要强化。

——————
And he said, What shall I give thee? And Jacob said, Thou shalt not give me any thing: if thou wilt do this thing for me, I will again feed and keep thy flock.

初识 monad

椭球法

前面讨论过椭球法是第一个证明具有多项式时间求解线性规划问题的算法,尽管这个算法本身的常数项很大,但是还是有一些理论意义的,这里讨论一下相关的方法,参考这里

椭球法使用一系列的椭球框定最优值的范围,每次由梯度方向确定搜索的范围(梯度相当于是一个超平面的法方向),这等价于认为最优值在椭球的另一半中,我们计算出来包含另一半椭球的最小体积的椭球,这样就更新了对最优值的估计(新的椭球球心)。这样就涉及到这样一个问题,给定当前的椭球 E_t =\{ x\in\mathbb{R}^n \mid (x - x_t)^\top P_t^{-1} (x - x_t) \leq 1\},超平面划分出的半平面 F_t = \{ x \in \mathbb{R}^n \mid g_t^\top (x - x_t) \leq 0,确定 x_{t + 1}P_{t + 1}

wiki 上写了个更新公式,但是不清楚是怎么得到了:

  • 计算 g = \frac{1}{\sqrt{g_t^\top P_t g_t}} g_t
  • 计算新的中心 x_{t+1} = x_t - \frac{1}{n + 1} P_t g
  • 计算新的二次型 P_{t + 1} = \frac{n^2}{n^2 - 1} \Big( P_t - \frac{2}{n} P_t g g^\top P_t\Big)

显然收敛条件可以用 \sqrt{g_t P_t g_t} \leq \varepsilon。在具有约束条件(线性不等式)的情况下,似乎要去某个 subgradient,但是没看明白这个 subgradient 是干啥的 -,-b 看起来这个理论好办,看懂也不容易啊… 有空想想看看能想出来不,感觉还少个条件。

——————–
No, my lord, hear me: the field give I you, and the cave that is therein, I give it you; in the presence of the sons of my people give I it you: bury your dead.

椭球法