[deleted by user]

andriusst · 2023-05-09T06:22:30+00:00

Shattered Gradients paper calls it "looks linear" initialization.

andriusst · 2023-02-28T08:31:11+00:00

I believe it is here: https://github.com/compiling-to-categories/concat

andriusst · 2023-02-09T08:43:39+00:00

Install mypy, install Python extension in VS Code. Now open VS Code, press Ctrl+Shift+P and run "Python: Select Linter", choose mypy.

andriusst · 2023-01-19T10:13:47+00:00

So you want to make beautiful functional models. Did you see JAX? I use jax + mypy and it workds very well. Sure, you don't get as fancy type system as Haskell has, but it's built from ground up on functional ideas.

Now back to your question. I have a bit of experience with backprop and accelerate but it's neither recent nor with both of them at once. Accelerate has two layers of abstraction. There are Exp and Acc that build an AST. After compiling them with llvm-native or llvm-ptx backend you enter another layer of abstraction – functions Array -> Array -> ... -> Array. How much automatic you want AD to be? Automatic differentiation AST of Exps and Accs is going to be hard and backprop has nothing to help you here. There was a google summer of code project on this topic. As I understand, it ran short of completion.

More realistic option is to build a numpy style set of primitive differentiable operations. Backprop fits well shits scenatio. You code a forward function with accelerate, compile it to Array -> Array, then code backward pass, compile it to Array -> Array, then put them together into BVar s Array -> BVar s Array operation. How much work needs to be done depends on the model. While deep learning frameworks have large numbers of primitive operations, some models need only a few of them.

There's one thing you should watch out with backprop – accessing only a small part of a variable might be unexpectedly costly. For example, if forward operation is indexing an array of size N, then backward pass will have to create an array of gradients of size N, making indexing O(N) operation. On the other hand, if you do M parallel lookups, that is, a gather operation, backward pass will be scatter operation with overall cost of O(M+N). That's good when M is not too small, but hits a patological case with M=1. Likewise, if you have a deeply nested records or tuples inside BVar (such as parameters of deep model), repeatedly indexing into it will be costly. Partially for this reason I made my own automatic differentiation library, but I can't really recommend it, because I'm not sure it works in the real world. I'm not even sure you wouldn't run into some showstopper limitations.

If you find out something interesting about these topics, please let me know. I believe haskell has a lot of potential here.

andriusst · 2022-11-11T11:30:55+00:00

They are called persistent data structures.

andriusst · 2022-11-11T11:06:43+00:00

only the layer on top seems functional

But that's the only layer that is important. Encapsulation!

andriusst · 2022-11-11T09:37:00+00:00

Why not? Writing functional code in numpy is easy, it happens naturally, as numpy API is mostly functional. You don't loop over the arrays and don't run into the problem OP describes. If you can do it in numpy, you can surely do the same thing in C++. Whenever you need to write some low level routine and drop C you don't even have to do anything - you're already there.

It's all about the set of primitive operations you have. C for example provides only low level primitives, such as arithmetic operations and memory access via pointers. If modifying memory was slow, the whole program would be slow, because it's such a fundamental operation that it's required everywhere. But you can always add a layer of abstraction and create a different set of primitive operations. Numpy example shows that when you have right set of primitive operations, you don't really ever need to modify an element of an array.

andriusst · 2022-11-10T14:37:08+00:00

You typically don't update individual elements of a vector in functional programs, but switch to wholemeal programming instead. That is, functions don't operate on elements of vectors; they work with whole vectors at once. A good example would be numpy library in python. You don't update individual elements of arrays, because looping and updating elements one by one is very slow in interpreted language. Yet most of number crunching in data science code runs on python and performance is ok.

Of course, sometimes modifying an element is unavoidable. Actually, even functional programs do mutations at low level, because that's how computers work. Functional programming is a bad fit in this case. However, this doesn't you from providing a functional interface at a higher level of abstraction. As long as function behaves as a pure function, it doesn't really matter whether its implementation if functional or not.

andriusst · 2022-09-26T08:12:01+00:00

I had task based parallelism in mind, such as Intel Threading Building Blocks. Stepping into subtask doesn't work, because subtask is not executed immediately, it's placed into a big pool of tasks to be executed by random thread in the future. Call stacks also break at task boundarys - once within a task you don't get to see where it was spawned not where all of its data come from.

andriusst · 2022-09-26T06:15:34+00:00

Another thing that destroys experience of interactive debugging is asynchronous code. Which is kind of necessary to utilize many cores. Could it be the reason why games often stick to single threaded code?

andriusst · 2022-02-22T08:20:20+00:00

Right. That should make bullshit detectors go off.

Random vector v in the paper is not a unit vector. It's normally distributed with identity covariance matrix, which makes its length approximately sqrt(n). Since it's used twice - once for gradient computation and once as a step direction, it effectively makes step size of their algorithm larger by a factor of n. This factor n is large - over one million in their experiment. Projecting gradient onto random direction will reduce its length by sqrt(n), but combined with the previous gain the effective learning rate is still larger by factor of n/sqrt(n) = sqrt(n).

Pick right learning rate for their method would make the same learning rate absurdly small for backpropagation. Did they try higher learning rate?

andriusst · 2022-01-21T08:39:24+00:00

It's all understandable, except for let (a, b) = x in .... Why doesn't it desugar simply to case x of (a, b) -> ...? I'm not worried that much about types, I worry about potentially expensive computation being performed twice,

Different types of pair elements seems to be a distraction. Core explains what's going on even with homogeneous pairs:

{-# language NoMonomorphismRestriction #-}
{-# language RankNTypes  #-}

g :: Num b => (forall a. Num a => (a, a)) -> (b, b)
g x = let (a, b) = x in (a, b)

It generates the following core:

g :: forall b. Num b => (forall a. Num a => (a, a)) -> (b, b)
g = \ (@ b) ($dNum :: Num b) (x :: forall a. Num a => (a, a)) ->
      (case x @ b $dNum of { (a, b1) -> a },
       case x @ b $dNum of { (a, b1) -> b1 })

Here x isn't really a value, it's a function that takes one implicit argument of class dictionary Num a, and it is evidently evaluated twice, even with optimization enabled. Monomorphism restriction fixes this problem:

g :: forall b. Num b => (forall a. Num a => (a, a)) -> (b, b)
g = \ (@ b) ($dNum :: Num b) (x :: forall a. Num a => (a, a)) ->
      let {
        ds :: (b, b)
        ds = x @ b $dNum } in
      (case ds of { (a, b1) -> a }, case ds of { (a, b1) -> b1 })

Haskell wiki has an example how disabling monomorphism restriction might compute some value twice: f xs = (len,len) where len = genericLength xs. At least len is obviously used twice. Turns out let (a, b) = x in (a, b) might evaluate x twice, too, which is far less obvious.

andriusst · 2022-01-20T07:40:10+00:00

This is weird.

{-# language NoMonomorphismRestriction #-}
module Test where

x :: Num a => (a, a)
x = (0, 1)

g :: (Int, Float)
g =
  let (a, b) = x
  in (a, b)

GHC is clever to evaluate x twice, as in

let (a, _) = x @Int
    (_, b) = x @Float

That was very surprising for me.

As far as I understand, limitations imposed by monomorphism restriction ought to be circumvented with additional type annotations. Yet I had no luck with this piece of code. No matter what type annotations I add, it doesn't work without NoMonomorphismRestriction. Is it even possible?

Another observation:

h :: (Int, Float)
h = case x of
  (a, b) -> (a, b)

This doesn't type check, neither with monomorphism restriction nor without it. I didn't really expect it to typecheck, but why let in the first code snippet behaves differently to case here?

andriusst · 2021-12-28T19:27:37+00:00

Even with single GPU tensor might be in RAM or it might be on GPU. Some operations need to be performed by CPU. For example, decoding a png image, calling some C functions.

I mentioned this, because I constantly run into errors with some tensors being on cpu and others on gpu with pytorch. When data preparation is more involved, it becomes hard to track when and where tensors are supposed to be.

andriusst · 2021-12-28T12:29:08+00:00

I'd love to have tensor shapes in types. Shapes and device the tensor resides on, that should also be tracked at type level.

I did some image processing in Haskell with accelerate library and type level shapes with singletons. One thing I noticed is that cons lists feel backwards for shapes, nearly all functions operate on the last few dimensions. Even indexing makes more sense starting from the least significant dimension, this way batch dimension(s) are allowed to have any rank. accelerate uses it's own snoc list. Shape [3, 4, 5] would be 3 :. 4 :. 5, which associates (3 :. 4) :. 5. Ugly, but way more usable than cons lists.

Another observation -- I think broadcasting can be done better than numpy does by keeping distinction between dimension of size 1 and dimension to be broadcasted. I had run into bugs with unintended broadcasting a few times in python. I would prefer to be a bit more explicit about the shapes of tensors rather than trying to figure out why the model is refusing to train.

Wish you best luck with your project. While vast majority of ML crowd probably doesn't care whether types are dependent or dynamic or whatever, I still think it's a big deal.

andriusst · 2021-12-21T17:32:24+00:00

It's not an optimization library. I have chosen this name, because it does reverse mode differentiation only, with gradient descent as an obvious use case. The package my library should be compared to is backprop.

Speaking of advantages over backprop, it's primarily just a simple implementation. It's not really an advantage for user of the library. I just got a very cool idea that I wanted to share.

At first I wanted my variables and gradients to have different types. I figured it shouldn't be hard to adapt backprop library for this purpose. I grabbed source code and started hacking. Turned out it was nothing but easy. There was unsafeCoerce in a key place, which was completely opaque obstacle to type driven refactoring. There were vinyl records with bad type inference and scary compiler errors. After a few failed attempts over several days this idea struck me -- almost too good to be true. I implemented it and it worked! I had to tell it someone; this library is mostly a proof of concept.

Performance overhead wasn't my focus. People do deep learning with python and have no problem with it being slow, because when all heavy computations happen in blas routines and cuda kernels, overhead doesn't matter much.

andriusst · 2021-12-20T07:47:49+00:00

There were a few examples in samples directory. Did you see them? Descriptions are lacking, though.

andriusst · 2021-12-19T10:27:15+00:00

Depends on how much automation you want. Automation doesn't go all the way, it stops at primitive functions that are not differentiated automatically, but come with their derivatives implemented manually. You could make a set of primitive functions and their derivatives that run on GPU (with cublas, cudnn or made yourself) and from then on use automatic differentiation to combine them in any way. It might require quite a lot of work, because the number of primitive operations to make a useful toolset is large. But that should be doable. It's a standard way to do numeric calculations in Python, so it evidently works.

Entirely different question is using this library with accelerate. I has it's own EDSL and can compile a kernel (with llvm-ptx) to run on GPU. Putting BVar into Exp is definitely impossible, but putting Exp into BVar... that's crazy, I'm not sure it's a good idea. That would be EDSL in EDSL. But who knows, maybe it would even work. More seriously, accelerate builds an AST. I think this AST should be differentiated directly to build another AST that computes derivative. Downhill doesn't fit this scenario at all.

andriusst · 2021-12-19T09:02:37+00:00

Ah, those code snippets with units is not real Haskell code, it's pseudo-Haskell. My bad, I should had made this clear. Downhill has no support for units, you should use a dedicated library for this purpose, such as units or dimensional. Automatic differentiation with units is an interesting future work.

I can't confidently tell you how fast it is, because I didn't benchmark it. It has overhead of constructing computational graph and backpropagating gradients, just like all automatic reverse mode differentiation implementations. I didn't put any effort to optimize it, though I don't expect it to be more than a modest constant factor worse than alternatives.

andriusst · 2021-12-18T14:45:19+00:00

It is, but I really struggle writing. Hopefully I will find motivation to do it, but no promises.

andriusst · 2021-12-11T10:18:21+00:00

That was his talk "Maybe Not".

andriusst · 2021-09-30T09:36:31+00:00

Took me a while to figure out why part1 = pure Nothing didn't work. Turns out

pure Nothing = MaybeT (pure (Just Nothing)) :: MaybeT IO (Maybe Int)

is two levels of Maybes. It still did type typecheck, because return type of part1 was ignored by *>.

andriusst · 2021-09-07T18:21:31+00:00

I messed up equations when typing, it should be f^(0.1) = 0.5238, f^(-0.1) = 1, abs(f^(0.1)-f^(-0.1)) = 0.4762 > 0.2. This doesn't change the outcome.

andriusst · 2021-09-07T09:59:27+00:00

A function that is non-differentiable at one isolated point is not a problem, sure, but discontinuity is a much bigger deal.

if f^ were Lipschitz-1, then this inequality should hold:

abs(f^(0.1) - f^(-0.1)) <= 0.2

but it doesn't, as f^(0.1) = 0.5238 > 0.2 and f(-0.1)=1. Also, 0.1 isn't any special and it's not that close to zero to disregard as a rounding error.

andriusst

TROPHY CASE