## Mathematical foundations

### Bag-of-words representation

- Representation for text
- Text is represented by a bag/multiset from predefined vocabulary
- Definition bag/multiset
	- Informal
		- Set with multiple instances for each element
		- Number of instances of an element is called *multiplicity* 
	- Formal
		- `$ (A, m) $`
		- `$ A $` underlying set
		- `$ m: A\rightarrow \mathbb{N}_{\geq 1} $`  (multiplicity)
		- Intersection, Union, Inclusion possible
- Can represented with an incidence vector
- Advantage
	- Simple set-theoretic
	- Efficient storage
- Disadvantage
	- Ignores word order
	- Ignores document structure
	- Different documents could have the same representation

### Fuzzy logic
- Zadeh, 1965
- Idea: Membership of item in set is not binary but continuous
- Desired properties
	- Commutativity
	- Associativity
	- Monotony
		- `$ a\leq c \land b\leq d \Rightarrow T(a,b)\leq T(c,d) $`
	- Continuity
- Formal
	- `$ \mu(A) \in [0,1] $` (truth value of formula `$ A $`)
- Operators
	- Conjunction: `$ \mu(A\land B) = \min(\mu(A), \mu(B)) $`
	- Disjunction: `$ \mu(A\lor B) = \max(\mu(A), \mu(B)) $`
	- Negation: `$ \mu(\neg A) = 1 - \mu(A) $`
- Interpretation
	- Describes the degree of truth
	- Different from probability
		- Probability makes exact statements about events
		- Possibility makes fuzzy statements about events


### Jaccard Index
- Called *Intersection over union*
- Called *Jaccard similarity coefficient*
- Measure similarity/diversity of sets
- Definition (measure similarity)
	- `$ A\cup B\neq\emptyset: J(A,B) = \frac{|A\cap B|}{|A\cup B|} $`
	- `$ A\cup B=\emptyset: J(A,B)=1 $`
- Definition *Jaccard distance* (measure dissimilarity)
	- `$ d_J(A,B)=1-J(A,B) $`

### Metric
- Metric `$ d: X\times X \rightarrow \mathbb{R} $`
- Properties
	- Non-negativity: `$ \forall x,y\in X: d(x,y)\geq 0 $`
	- Identity: `$ \forall x,y\in X: x=y \Rightarrow d(x,y)= 0 $`
	- Symmetry: `$ \forall x,y\in X: d(x,y)=d(y,x) $`
	- Triangle equality: `$ \forall x,y,z\in X: d(x,z)\leq d(x,y)+d(y,z) $`
- Example: Euclidean distance

### Pareto principle
- Called `$ 80/20 $` rule
- Based on *Power law*
- Roughly 80 % of the effects come from 20 % of the causes
- Examples
	- 80 % of sales come from 20 % of the clients
	- 80 % of land in Italy was owned by 20 % of population
- Computing
	- Microsoft: Fixing 20 % of most-reported bugs, 80 % of related errors were eliminated

### Power law
- Relationship between two quantities
- *Long tail*: Part of distribution with low occurrences (see Pareto principle)
- `$ f(x)=ax^{-k} $`
- Log-log plots: Power law has straight line (necessary but insufficient)

### Probability theory
- Independence of events
	- Implies `$ P(A \land B) = P(A) * P(B) $`
- Conditional probability
	- `$ P(A\mid B) = \frac{P(A \land B)}{P(B)} $`
- Bayes' theorem
	- `$ P(A\mid B) = \frac{P(A)}{P(B)} P(B\mid A) $`
	- *Prior probability of A*: `$ P(A) $`
	- *Posterior probability of A*: `$ P(A\mid B) $`
	- Idea: `$ P(A) $` gets update after observing B
- Interpretations
	- Frequentist: Limit of relative frequency
	- Bayesian: Degree of belief / Knowledge can be updated


### Lagrange multipliers
- Optimization problem
	- Maximize `$ f(x_1,...,x_n) $`
	- Condition `$ g(x_1,...,x_n) = 0 $`
- Lagrange function `$ \mathcal{L}(x_1,...,x_n,\lambda) = f(x_1,...,x_n) - \lambda g(x_1,....,x_n) $`
- Maximum of `$ f(x_1,...,x_n) $` is stationary point of `$ \mathcal{L}(x_1,...,x_n,\lambda) $`
- Yields only local maxima

### Linear algebra
- Considering `$ C \in \mathbb{R}^{M\times N} $`
- Application
	- Information retrieval
	- Data compression

#### Frobenius Norm
- Frobenius norm `$ ||C||_F^2 = \sum_{i=1}^M \sum_{j=1}^N c_{ij}^2 = \sum_{i=1}^r \sigma_i^2 $` 

#### Linear independence
- `$ A = \{v_1,...,v_k\}\in \mathbb{R}^N $`
- Linearly dependent vectors: `$ \lambda_1 x_1 +...+\lambda_k x_k = 0 $`
- Theorem: If `$ k>n $` the set is linearly dependent

#### Rank
- Number of linearly independent rows/columns
- Dimension of the image
- `$ rank(C) \leq min(M,N) $`
- `$ rank(C) = dim(Cx \mid x\in \mathbb{R}^N) $`

#### Linear span
- All points expressed by linear combinations
- `$ span(x_1, ..., x_k) = \{a_1 x_1 +...+a_k x_k\mid a_1,...,a_k\in \mathbb{R} \} $`

#### Basis
- Set of linearly independent vectors
- `$ B=\{x_1,...,x_k\} $`
- `$ span(B) $` is k-dimensional subspace of `$ \mathbb{R}^n $`
- Theorem: Each point in `$ span(x_1,...,x_k) $` has a unique linear combination 
- Theorem: Given two basis `$ A, B $` of the same subspace, there is a unique transformation T such that `$ Ta_i = b_I $` 

#### Eigenvalue
- `$ x\in \mathbb{R}^N $`
- `$ C\in \mathbb{R}^{n \times n} $`
- `$ Cx_i=\lambda_i x_i $`
- Eigenvalue: `$ \lambda_i $`
- Right Eigenvector: `$ x_i $`
- Principal eigenvector
	- Eigenvector with largest corresponding eigenvalue
	- Highest variance in data
- Characteristic equation: `$ det(C-\lambda I_M) = 0 $`
- Observation: Contribution of small eigenvalue to matrix-vector product is small
- Eigenvectors from distinct eigenvalues from square matrix are orthogonal

#### Eigenbasis
- Matrix of eigenvectors as new basis
- `$ S\in \mathbb{R}^{M\times M} $`
- `$ U\in \mathbb{R}^{M\times M} $` eigenvectors
- `$ \Lambda = diag(\lambda_1,...,\lambda_n) $` eigenvalues
- `$ U^{-1} * S * U = \Lambda $`

#### Matrix decomposition

##### Matrix diagonalization theorem
- Preconditions
	- `$ S\in \mathbb{R}^{M\times M} $`
	- `$ rank(S) = M $`
- Then there exists an eigen decomposition `$ S=U \Lambda U^{-1} $`
- `$ U $`: Columns are eigenvectors
- `$ \Lambda\in diag(\lambda_1, ...,\lambda_M) $`: Diagonal matrix, eigenvalues in decreasing order
- `$ SU = U \Lambda $`, so `$ S = U \Lambda U^{-1} $`


##### Symmetric diagonalization theorem
- Preconditions
	- `$ S \in \mathbb{R}^{M\times M} $`
	- `$ rank(S) = M $`
	- `$ S = S^T $` (symmetric)
- Then there exists an symmetric diagonal decomposition `$ S=Q\Lambda Q^T $`
- `$ Q $`: Columns are orthogonal and normalized eigenvectors of S
- `$ Q^{-1} = Q^T $`
- `$ \Lambda\in diag(\lambda_1, ...,\lambda_M) $`: Diagonal matrix


##### Singular value decomposition
- Preconditions
	- `$ S\in \mathbb{R}^{M\times N} $`
	- `$ rank(S) = r $`
- `$ S=U\Sigma V^T $` (unique)
- Eigenvalues `$ \lambda_1,...,\lambda_r $` of `$ SS^T $` are the same as the eigenvalues of `$ S^TS $`
- `$ \Sigma = diag(\sigma_1,...,\sigma_r) $` with `$ \sigma_i=\sqrt{\lambda_i} $` and `$ \lambda_i>\lambda_{i+1} $`
- `$ U \in \mathbb{R}^{M\times M} $`
	- Columns are eigenvectors of `$ SS^T $`
	- *Left singular vectors*
	- Column-orthonormal
	- Right-most `$ M-r $` columns are zero
- `$ V \in \mathbb{R}^{N\times N} $`
	- Columns are eigenvectors of `$ S^TS $`
	- *Right singular vectors*
	- Column-orthonormal
	- Right-most `$ M-r $` columns are zero 
- *Reduced SVD*
	- `$ U \in \mathbb{R}^{M\times r} $`
	- `$ \Sigma \in \mathbb{R}^{r\times r} $`
	- `$ V \in \mathbb{R}^{N\times r} $`
- Linear map `$ Sx = U\Sigma V^Tx $`
	- `$ V^Tx $` map into space `$ \mathbb{R}^N $`
	- `$ \Sigma $` scales `$ Vx $`
	- `$ U $` map into space `$ \mathbb{R}^M $`

##### Low rank approximation
- Workflow
	1. Construct `$ C=U\Sigma V^T $`
	2. Create `$ \Sigma_k $`: Replace the `$ r-k $` smallest values in `$ \Sigma $` with `$ 0 $`
	3. Compute `$ C_k=U\Sigma_k V^T $` (low rank approximation)
- Approximate `$ C $` with `$ C_k $` by replacing the smallest `$ r-k $` singular values with `$ 0 $` (small eigenvalues have small impact)
- Minimize `$ ||C-C_k||_F $`
- `$ C_k $` has rank at most `$ k $`
- `$ C_k = U\Sigma_k V^T = \sum_{i=1}^k \sigma_i u_i v_i^T $`: Sum of rank-1 matrices weighted by `$ \sigma_i $`
- Theorem of Eckart and Young
	- Error of rank-k approximation is `$ d_F(C, C_k) = ||\sum_{i=k+1}^r \sigma_i u_i v_i^T||_F \leq \sqrt{r-k} \sigma_{k+1} $`
	- `$ C_k $` is the optimal rank-k approximation of `$ C $`


#### Markov chains
- Probability vector
	- `$ p\in [0,1]^{n} $`
	- Non-negative entries
	- Sum of entries equals 1
- Stochastic matrix
	- `$ T\in [0,1]^{n \times n} $`
	- Non-negative entries
	- Sum of each row equals 1
- Markov chains
	- Probabilistic finite state machine
	- `$ n $` states
	- Stochastic matrix `$ T\in [0,1]^{n \times n} $`
	- `$ T $` models state transistions
	- Exactly one state
	- Discrete time
	- `$ t_{ij} = P(\text{state}_{t+1}(j) \mid \text{state}_t(i)) $`
- *Perron-Frobenius theorem*:
	- Stochastic matrix with only positive entries has `$ \lambda_{max}=1 $`
	- Only one eigenvector to `$ \lambda_{max}=1 $`