2

Haskell で簡単な自動微分パッケージを作成しようとしています。

Haskellでタイプセーフな(有向)計算グラフを表現する効率的な方法は何ですか? 広告パッケージがそのために「data-reify」メソッドを使用していることは知っていますが、よく知りません。誰かが私にいくつかの洞察を提供できますか? ありがとう！

4

1 に答える 1

5

Will Ness のコメントが示すように、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でなければなりません。(そのような関数専用の矢印タイプを使用するか、たまたま線形である関数を使用することができます。) リバース モードで異なる唯一のことは、マップ自体ではなく、この線形マップの随伴が表されることです。 . (実数値行列の実装では、線形マッピングはヤコビ行列であり、随伴バージョンはその転置ですが、行列を使用しないでください。これには非常に非効率的です。) いいですね。人々が話し続けているグラフ/トラバーサル/ミューテーション/バックワードパスのナンセンスはすべて、実際には必要ありません。(詳細については、 Conal の論文を参照してください。)(->)

したがって、Haskell でこれを有効にするには、カテゴリ コンビネータを実装する必要があります。これは、 constrained-categories パッケージを書いたものとほとんど同じです。必要なもののインスタンス化の概要は次のとおりです。

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)

内部的には、これらの代数式は、データ フローを「分割」して並列に構成するFwAD矢印の構成を構築します。つまり、入力と最終結果が単純であっても、中間結果は適切なタプル型を介してプルされます。[それがタイトルの質問への答えになると思います。有向グラフは、ある意味で、分岐した構成チェーンとして表されます。原則として、 s の図の説明で見られるものと同じです。]&&&***DoubleArrow

于 2020-08-06T12:43:50.000 に答える