Articles on sangyx's Blog

udiff: Project Summary

sangyunxin@gmail.com (sangyx) — Fri, 28 Aug 2020 16:43:21 +0000

0. Github

https://github.com/Quansight-Labs/udiff

1. Describe my work briefly

Complete and package udiff.

2. What is done (commits)

Implement VJP: e23163c, 4038f61, 43147e0, b6c4550, 3c3360e, f6f0407
Implement jacobian: fc7bc9a, 9cd95d9
Add JVP: 5b4157e
Add documents: 75f2bcf, aed45d2, 1726b0d
Setup CI: 15db53b, 842d73f, bfb8151, d7058a4
Add test cases: 8ca34a0, 3047689, 5719c03, 015b4de, a348c46, 9f7e3b5

3. TODO

Merge the code in branch dev to master if the functions implemented in unumpy.
Implement JVP.
Add more test cases to improve test coverage to over 80%(70% now).
Publish udiff on pypi #25.
Fix bugs and issues in udiff.

[Week 12] Check-in

sangyunxin@gmail.com (sangyx) — Sat, 22 Aug 2020 08:00:55 +0000

1. What did you do this week?

Fix repeat_to_match_shape & grad_broadcast_to.
Clean code & move unimplement code to dev.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Publish udiff on pypi.
Complete jvp.
Add linalg.
Add more document.

[Week 11] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 16 Aug 2020 13:55:47 +0000

1. What did you do this week?

Add more diff funtions and test cases.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Publish a simple version of udiff on pypi.
Add jvp.

[Week 10] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 09 Aug 2020 13:18:25 +0000

1. What did you do this week?

Complete np.reshape and np.stack.
Split raw_functions & nograd_functions
Fix higher-order derivatives.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Publish a simple version of udiff on pypi.
Add more testcases.

[Week 9] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 02 Aug 2020 13:31:20 +0000

1. What did you do this week?

Control the base of the differentiation.
High-order derivatives support.
Cache diff in dict.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Publish a simple version of udiff on pypi.
Complete np.reshape and np.stack.

[Week 8] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 26 Jul 2020 12:19:21 +0000

1. What did you do this week?

Control the base of the differentiation.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Publish a simple version of udiff on pypi.
Complete more functions and testcases.

[Week 7] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 19 Jul 2020 04:03:45 +0000

1. What did you do this week?

Fix np.sum.
Merge pipelines into master.

2. Difficulty

Compatibility issue between uarray and unumpy.

3. What is coming up next?

Publish a simple version of udiff on pypi.

[Week 6] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 12 Jul 2020 01:32:03 +0000

1. What did you do this week?

Use unumpy multimethods.
Improve documentation.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Publish a simple version of udiff on pypi.
Fix np.sum.

[Week 5] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 05 Jul 2020 14:21:24 +0000

1. What did you do this week?

Add more test cases to cover more functions.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Use unumpy multimethods.
Improve documentation.
Publish a simple version of udiff on pypi.

[Week 4] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 28 Jun 2020 10:13:50 +0000

1. What did you do this week?

This week's job is to implement jacobian and add test cases.

2. Difficulty

No difficulties this week.

3. What is coming up next?

Add more test cases to cover more functions.
Improve documentation.
Publish a simple version of udiff on pypi.

[Week 3] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 21 Jun 2020 08:58:29 +0000

1. What did you do this week?

This week's job is to add test cases and change the code as mentor's request.

2. Difficulty

No difficulties this week.

3. What is coming up next?

The work for the next week is to merge vjp and start to work on jacobian.

[Week 2] Check-in

sangyunxin@gmail.com (sangyx) — Sun, 14 Jun 2020 08:45:04 +0000

1. What did you do this week?

This week's main job is to implement the backward propagation. After that, I complete the whole vjp.

Because of the bad support for figure and code, more detail see: https://sangyx.com/1790

2. Difficulty

I complicated this problem at the beginning. Later I found that imitating pytorch's API to implement is more intuitive and simple.

In addition, because I am not very familiar with uarray, some implementations are not elegent.

3. What is coming up next?

The work for the next week is to test vjp and work with my mentor to rewrite the code more elegent.

[Week 1] Check-in

sangyunxin@gmail.com (sangyx) — Thu, 11 Jun 2020 07:12:10 +0000

1. What did you do this week?

This week's main job is to build a calculation graph. The core of the automatic differential system is vjp, which is composed of calculation graph construction and gradient calculation.

2. Difficulty

The computational graph construction is not as simple as I thought. The main problem encountered in the process is that some basic differential operators not only need to pass in the tensors, but also need to pass in some parameters of the function, such as np.sum. This requires that some parameters required by the differential operator be passed in advance when constructing the calculation graph. In addition, according to the different calculation paths, the parents of each node in the calculation graph should be marked appropriately, and then they can be calculated along the correct path during back propagation.

3. What is coming up next?

The work for the next week is to implement simple back propagation and complete a complete differential operation.

[Community Bonding Period] What is Automatic Differentiation?

sangyunxin@gmail.com (sangyx) — Mon, 25 May 2020 11:18:53 +0000

The optimization process of deep learning models is based on the gradient descent method. Deep learning frameworks such as PyTorch and Tensorflow can be divided into three parts: model api, gradient calculation and gpu acceleration. Gradient calculation plays an important role, and the core technology of this part is automatic differentiation.

1 Differential method

There are four differential methods:

Manual differentiation
Numerical differentiation
Sign differential
Automatic differentiation

Manual differentiation is to use the derivation formula to manually write the derivation formula. This method is accurate and effective, and the only disadvantage is that it takes effort.

Numerical differentiation uses the definition of derivative.This method is simple to implement, but there are two serious problems: truncation error and roundoff error. But this method can be a good way to check whether the gradient is accurate.

Another method is symbolic differentiation, which transfers the work we did in manual differentiation to the computer. The problem with this method is that the expression must be closed-form, that is, there cannot be loops and conditional expressions. So that the entire problem can be converted into a pure mathematical symbol problem can be solved using some algebraic software. However, when expressions are complex, the problem of "expression swell" is prone to occur.

The last is our protagonist: automatic differentiation. It is also the most widely used derivation method in programe.

2 Automatic differentiation

The automatic differentiation discovers the essence of differential calculation: Differential calculation is a combination of a limited series of differentiable operators.

We can regarded the formula: f(x1, x2)=ln(x1)+x1x2-sin(x2) as a calculation graph (What’s more, it can be regarded as a tree structure, too). In the process of forward calculation, we can obtain the value of each node.

Then we can express the derivation process of df/dx1 as a series of differential operator combinations. The calculation can be divided into two types: calculating the formula from forward to backward is called Forward Mode, and calculating the formula from backward to forward is called Reverse Mode.

The gradient values calculated by the two modes are the same, but for the calculation order is different, the calculation speed is different. Generally, if the Jacobian matrix is relatively high, then the forward mode is more efficient; if the Jacobian matrix is wider, then the reverse mode is more efficient.

3 JVP, VJP and vmap

If you have used pytorch, you will find that if y is a tensor instead of a scalar, you will be asked to pass a grad_variables in y.backward(). And the derivative result x.grad has the same shape as x. Where is the Jacobian matrix?

The reason is that deep learning frameworks such as Tensorflow and PyTorch prohibit the derivatives with tensor by tensor, but only retain scalar by tensor. When we call y.backward () and enter a grad_variables v. In fact, it actually converts y into a weighted sum l = torch.sum(y * v) , where l is a scalar, and then the gradient of x.grad is naturally of the same shape as x. The reason for this is that the loss of deep learning is definitely a scalar, and gradient descent requires that the gradient must be of the same type as x.

But what if we want to obtain the Jacobian matrix?

The answer is to derive x for each value of y.In addition, Google's new deep learning framework JAX uses a more advanced method, the vectorization operation vmap to speed up the calculation.

Articles on sangyx's Blog

udiff: Project Summary

0. Github

1. Describe my work briefly

2. What is done (commits)

3. TODO

[Week 12] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 11] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 10] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 9] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 8] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 7] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 6] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 5] Check-in

2. Difficulty

3. What is coming up next?

[Week 4] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 3] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 2] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Week 1] Check-in

1. What did you do this week?

2. Difficulty

3. What is coming up next?

[Community Bonding Period] What is Automatic Differentiation?

1 Differential method

2 Automatic differentiation

3 JVP, VJP and vmap

4 Reference