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

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

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 \( 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

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

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

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

Frobenius norm \( ||C||_F^2 = \sum_{i=1}^M \sum_{j=1}^N c_{ij}^2 = \sum_{i=1}^r \sigma_i^2 \)

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} \} \)

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 \)

\( 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

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} \)

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

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 \)

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 \)

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 \)