Как указывает комментарий Уилла Несса, правильная абстракция для AD - это категория, а не график. К сожалению, стандартный Category класс на самом деле не помогает, потому что требует стрелок между любыми Haskell типами, но различие имеет смысл только между гладкими коллекторами . Большинство библиотек не знают о многообразиях и ограничивают их еще евклидовыми векторными пространствами (которые они представляют как «векторы» или «тензоры», которые представляют собой просто массивы). На самом деле нет веских причин для того, чтобы было ограничительным - любое аффинное пространство подойдет для AD прямого режима; для обратного режима вам также потребуется понятие двойного пробела для векторов разностей.
data FwAD x y = FwAD (x -> (y, Diff x -> Diff y))
data RvAD x y = RvAD (x -> (y, DualVector (Diff y) -> DualVector (Diff x)))
где функция Diff x -> Diff y должна быть линейной функцией . (Вы можете использовать специальный тип стрелки для таких функций , или вы можете просто использовать (->) функции, которые оказываются линейными.) Единственное, что отличается в обратном режиме, - это то, что сопряженный этой линейной карты отображается вместо самой карты. (В реализации матрицы с действительным знаком линейное отображение - это матрица Якоби , а сопряженная версия - ее транспонирование, но не используйте матрицы, они ужасно неэффективны для этого. )
Аккуратно, правда? Вся эта ерунда про графики / обход / мутации / обратный проход, о которой люди продолжают говорить, на самом деле не нужна. (См. статью Конала.)
Итак, чтобы сделать это полезным в Haskell, вам необходимо реализовать комбинаторы категорий. Это в значительной степени именно то, для чего я написал пакет ограниченных категорий . Вот схематичный экземпляр того, что вам нужно:
import qualified Prelude as Hask
import Control.Category.Constrained.Prelude
import Control.Arrow.Constrained
import Data.AffineSpace
import Data.AdditiveGroup
import Data.VectorSpace
instance Category FwAD where
type Object FwAD a
= (AffineSpace a, VectorSpace (Diff a), Scalar (Diff a) ~ Double)
id = FwAD $ \x -> (x, id)
FwAD f . FwAD g = FwAD $ \x -> case g x of
(gx, dg) -> case f gx of
(fgx, df) -> (fgx, df . dg)
instance Cartesian FwAD where
...
instance Morphism FwAD where
...
instance PreArrow FwAD where
...
instance WellPointed FwAD where
...
Все экземпляры просты и почти однозначны, позвольте сообщениям компилятора направлять вас ( типизированные дыры _ чрезвычайно полезны). По сути, всякий раз, когда требуется переменная типа, находящегося в области видимости, используйте ее; когда требуется переменная типа векторного пространства, имеющая не в области видимости, используйте zeroV.
В этот момент у вас действительно будет все фундаментальное дифференцируемые функции набор инструментов, но для фактического определения таких функций вам потребуется использовать стиль без точек с множеством комбинаторов ., &&& и *** и жестко заданных числовых примитивов, что выглядит нетрадиционный и довольно запутанный. Чтобы избежать этого, вы можете использовать значения агента : значения, которые в основном притворяются простыми числовыми переменными, но на самом деле содержат целую стрелку категории из некоторого фиксированного типа домена. (По сути, это будет часть упражнения «построение графика».) Вы можете просто использовать предоставленную GenericAgent оболочку.
instance HasAgent FwAD where
type AgentVal FwAD a v = GenericAgent FwAD a v
alg = genericAlg
($~) = genericAgentMap
instance CartesianAgent FwAD where
alg1to2 = genericAlg1to2
alg2to1 = genericAlg2to1
alg2to2 = genericAlg2to2
instance PointAgent (GenericAgent FwAD) FwAD a x where
point = genericPoint
instance ( Num v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
, Scalar a ~ v )
=> Num (GenericAgent FwAD a v) where
fromInteger = point . fromInteger
(+) = genericAgentCombine . FwAD $ \(x,y) -> (x+y, \(dx,dy) -> dx+dy)
(*) = genericAgentCombine . FwAD $ \(x,y) -> (x*y, \(dx,dy) -> y*dx+x*dy)
abs = genericAgentMap . FwAD $ \x -> (abs x, \dx -> if x<0 then -dx else dx)
...
instance ( Fractional v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
, Scalar a ~ v )
=> Fractional (GenericAgent FwAD a v) where
...
instance (...) => Floating (...) where
...
Если у вас есть все эти экземпляры полный и, возможно, простой помощник для извлечения результатов
evalWithGrad :: FwAD Double Double -> Double -> (Double, Double)
evalWithGrad (FwAD f) x = case f x of
(fx, df) -> (fx, df 1)
, тогда вы можете написать такой код, как
> evalWithGrad (alg (\x -> x^2 + x) 3)
(12.0, 7.0)
> evalWithGrad (alg sin 0)
(0.0, 1.0)
Под капотом эти алгебраические c выражения создают композицию из FwAD стрелок с &&& «разделением» потока данных и *** составлением параллельно, т.е. даже если входные и конечные результаты простые Double, тогда промежуточные результаты будут извлечены из кортежа подходящего типа. [Это, я думаю, было бы ответом на ваш заглавный вопрос: ориентированный граф в некотором смысле представлен как разветвленная цепочка композиций, в принципе то же самое, что вы найдете в тех пояснениях диаграмм Arrow s .]