技术博客:用导数翻转理解自动微分实现
来源标题:Derivative Flipping
一篇技术博客提出用 Brzozowski 导数思路来理解自动微分(AD)的实现,并给出 Haskell 代码示例。文章先从正则表达式匹配的导数方法讲起,说明如何通过逐字母剥离和代数化简判断匹配,再引申到 AD 算法的实现思路。文中并未给出完整的 AD 算法,而是强调这是一种便于理解已有工作的思考方式。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
{-# OPTIONS_GHC -Wincomplete-patterns #-} 我想换一个角度来思考自动微分。我不打算给出一个实际的 AD 算法,而是要展示如何实现某些 AD 算法——这也许是理解一些已发表工作的一种更简单的方式。 不过首先我想谈谈用 Brzozowski 导数做正则表达式匹配。这一段你可以跳过,但它正是我写下面代码时的思路来源。 我们定义尖括号算子 (\langle\cdot,\cdot\rangle):若 (R) 是匹配字符串 (S) 的正则表达式,则 (\langle R,S\rangle=1),否则为 0。我会照抄 Wikipedia 上的定义,但稍微改一下记号(以及 Wikipedia 上的一些辅助定义)。 如果你以前没见过,这个定义看起来挺吓人,但它归根结底只依赖于一个关键性质: 所以,要判断一个正则表达式是否匹配字符串 (S),我们可以把 (S) 的字母从前往后逐个剥下来,并对 (R) 施加相应的导数算子。我们还需要在正则表达式代数中做代数化简。如果最终得到一个匹配空串的正则表达式,那么原正则表达式就匹配原字符串。关于如何让它实用化的更多细节,参见 Scott Owens、John Reppy 和 Aaron Turon 的 Regular-expression derivatives reexamined。 尽管我们可能以为不断求导会得到各种各样中间表达式,但真正互不相同的表达式只有有限多个(把匹配相同字符串集合的两个正则表达式视为等价)。它们构成识别该正则表达式目标语言的有限状态自动机的状态。 让我们对普通微积分做类似的模仿。给定一对多元多项式 (p) 和 (q),定义 我们可以直接在 Haskell 里实现它。最终我会定义 pair p q,也就是由尖括号定义的配对。 首先我定义由 v 中元素在 a 上生成的环中的表达式: data Expr v a = Var v | Expr v a :+: Expr v a | Expr v a :: Expr v a | Lit a deriving (Eq, Show) 现在可以给它 Num 接口: instance Num a => Num (Expr v a) where fromInteger = Lit . fromInteger (+) = (:+:) () = (::) negate x = Lit (negate 1) * x signum = undefined abs = undefined 我应该加上化简,但这段代码纯粹是教学性质的,并没有这个必要。接下来我们实现把 p 解释为作用于 q 的微分算子的规则。 apply :: (Eq v, Num a) => Expr v a -> Expr v a -> Expr v a 这表示 (\partial_i x_j=\delta_{ij}): apply (Var v) (Var w) | v == w = 1 apply (Var v) (Var w) = 0 线性性: apply (a :+: b) c = apply a c + apply b c 我觉得这很有意思。在 (\langle\cdot,\cdot\rangle) 的右边是普通的多项式乘法,但在左边则是微分算子的复合: apply (a :: b) c = (apply a . apply b) c apply a@(Lit _) b = a * b apply a (b :+: c) = apply a b + apply a c 通常的 Leibniz 法则: apply v@(Var _) (b :: c) = apply v b * c + b * apply v c apply v@(Var _) (Lit _) = 0 现在我们取零处求值。注意,这对应于正则表达式的情形:你问残余表达式是否匹配空串: atZero :: (Num a, Eq v) => Expr v a -> a atZero (Lit a) = a atZero (Var _) = 0 atZero (a :+: b) = atZero a + atZero b atZero (a :: b) = atZero a * atZero b 最后是配对: pair a b = atZero (apply a b) 接下来就是神奇的部分了。我们有两个定理: 而且更令人惊讶的是(考虑到左边多项式的解释与右边多项式如此不同):
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。