# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 2
#     language: python
#     name: python2
# ---

# + [markdown] id="R308Q42Etoca" colab_type="text"
# # Homework 1: Differentiation

# + [markdown] id="m8VIh_iDtoce" colab_type="text"
# Since it easy to google every task please please please try to undestand what's going on. The "just answer" thing will be not counted, make sure to present derivation of your solution. It is absolutely OK if you found an answer on web then just exercise in $\LaTeX$ copying it into here.

# + [markdown] id="ocbBPXq8toch" colab_type="text"
# Useful links: 
# [1](http://www.machinelearning.ru/wiki/images/2/2a/Matrix-Gauss.pdf)
# [2](http://www.atmos.washington.edu/~dennis/MatrixCalculus.pdf)
# [3](http://cal.cs.illinois.edu/~johannes/research/matrix%20calculus.pdf)
# [4](http://research.microsoft.com/en-us/um/people/cmbishop/prml/index.htm)

# + [markdown] id="-PpQc43Vtocj" colab_type="text"
# ## ex. 1

# + [markdown] id="uNBbxcTYtocl" colab_type="text"
# $$  
# y = x^Tx,  \quad x \in \mathbb{R}^N 
# $$

# + [markdown] id="9vHwr8yutocn" colab_type="text"
# $$
# \frac{dy}{dx} =  2 x 
# $$ 
#
# Потому что
#
# $$
# \left(\frac{dy}{dx}\right)_j = \frac{\partial x^i x_i}{\partial x_j} = \delta^i_j x_i + x^i \delta_{i j} = 2 x_j
# $$

# + [markdown] id="GvmaKwvptoc2" colab_type="text"
# ## ex. 2

# + [markdown] id="rrrhqioxtoc4" colab_type="text"
# $$ y = tr(AB) \quad A,B \in \mathbb{R}^{N \times N} $$ 

# + [markdown] id="7FWY4ZT9toc7" colab_type="text"
# $$
# \frac{dy}{dA} = B^T
# $$
#
# Потому что
#
# $$
# \left( \frac{dy}{dA} \right)^k_l = \frac{d A^i_j B^j_i}{dA^k_l} = \delta^i_k \delta^l_j B^j_i = B^l_k = \left( B^T \right)^k_l 
# $$
#
# где верхний индекс отвечает за строки, а нижний за столбцы.

# + id="MaFvEHrVtoc-" colab_type="code" colab={}


# + [markdown] id="ozmLJx8FtodI" colab_type="text"
# ## ex. 3

# + [markdown] id="yUwNSuk8todK" colab_type="text"
# $$  
# y = x^TAc , \quad A\in \mathbb{R}^{N \times N}, x\in \mathbb{R}^{N}, c\in \mathbb{R}^{N} 
# $$

# + [markdown] id="MjelU_GjtodN" colab_type="text"
# $$
# \frac{dy}{dx} = A c
# $$
#
# Потому что
#
# $$
# \left( \frac{dy}{dx} \right)_i = \frac{d x^j A^k_j c_k}{d x_i} = A^k_j c_k \delta^j_i = A^k_i c_k 
# $$

# + [markdown] id="DjANTVrLtodO" colab_type="text"
# $$
# \frac{dy}{dA} = x c^T
# $$
#
# Потому что
#
# $$
# \left( \frac{dy}{dx} \right)^k_l = \frac{d x^j A^m_j c_m}{d A^k_l} = x^j c_m \delta^m_k \delta^l_j = c_k  x^l = \left( x c^T \right)^k_l
# $$
#

# + [markdown] id="YgM4oIQZtodQ" colab_type="text"
# Hint for the latter (one of the ways): use *ex. 2* result and the fact 
# $$
# tr(ABC) = tr (CAB)
# $$

# + id="vWyI2v5ptodS" colab_type="code" colab={}


# + [markdown] id="MP7BMMZ_tode" colab_type="text"
# ## ex. 4

# + [markdown] id="smW9W7tEtodf" colab_type="text"
# Classic matrix factorization example. Given matrix $X$ you need to find $A$, $S$ to approximate $X$. This can be done by simple gradient descent iteratively alternating $A$ and $S$ updates.
# $$
# J = || X - AS ||_F^2  , \quad A\in \mathbb{R}^{N \times R} , \quad S\in \mathbb{R}^{R \times M}
# $$
# $$
# \frac{dJ}{dS} = ? 
# $$ 

# + [markdown] id="92x2EqEttodh" colab_type="text"
# ### First approach
# Using ex.2 and the fact:
# $$
# || X ||_F^2 = tr(XX^T) 
# $$ 
# it is easy to derive gradients (you can find it in one of the refs). 

# + [markdown] id="B1XVTx9btodj" colab_type="text"
# ### Second approach
# You can use *slightly different techniques* if they suits you. Take a look at this derivation:
# <img src="https://github.com/Bazheno/Practical_DL/blob/spring20/homework01/grad.png?raw=1">
# (excerpt from [Handbook of blind source separation, Jutten, page 517](https://books.google.ru/books?id=PTbj03bYH6kC&printsec=frontcover&dq=Handbook+of+Blind+Source+Separation&hl=en&sa=X&ved=0ahUKEwi-q_apiJDLAhULvXIKHVXJDWcQ6AEIHDAA#v=onepage&q=Handbook%20of%20Blind%20Source%20Separation&f=false), open for better picture).

# + [markdown] id="K6yXmA0btodl" colab_type="text"
# ### Third approach
# And finally we can use chain rule! **YOUR TURN** to do it.
# let $ F = AS $ 
#
# **Find**
# $$
# \frac{dJ}{dF} =  \frac{d (tr((X-F)(X-F)^T)}{dF} = \frac{d(tr(XX^T) - tr(FX^T) - tr(XF^T) + tr(FF^T))}{dF} = -2 \frac{d(tr(FX^T))}{dF} + \frac{d (tr(FF^T))}{dF} = 2F - 2X  
# $$ 
# and 
# $$
# \frac{dF_{i j}}{dS_{l m}} = \frac{dA_{i k} S_{k j}}{dS_{lm}} = A_{i k} \delta_{k l} \delta_{m j} = A_{i l} \delta_{m j} 
# $$ 
# (the shape should be $ NM \times RM )$.
#
# Now it is easy do get desired gradients:
# $$
# \left( \frac{dJ}{dS} \right)_{l m}  = \frac{dF_{i j}}{dS_{l m}} \frac{dJ}{dF_{i j}} = 2 A_{i l} \delta_{m j} (F - X)_{i j} = 2 (A^T)_{l i} (F-X)_{i m}  
# $$ 
#
# То есть
#
# $$
# \frac{dJ}{dS} = -2A^T(X - AS)
# $$

# + id="db7aKAtntodm" colab_type="code" colab={}


StarcoderdataJupyterScriptsDedupFiltered