#### 1) Neural Network ##### General: - structure determines function, parallel distributed, generalization - for each node(=neuron) $j$ at iteration $k$: Input signals (from prev layer) $y_i, i \in [n] \\ \qquad \downarrow$ Linear weighted sum $v_j(k) = \sum_{i=0}^n w_{ji}(k) y_i(k) = \vec w \cdot \vec x \\ \qquad \downarrow$ Function (output) signal $y_j(k) = \Phi_j(v_j(k))$ - bias is just set as $w_0(k)$ with constant "input" $y_0:=1$ - activation function $\Phi$: differentiable, monotone-increasing, bounded (and continuous), e.g.: - hardlim/threshold/heaviside: $v \geq 0$ - sigmoid: logistic $(1+e^{-av})^{-1} \in (0;1)$ , signum, tanh $\in (-1; 1)$ - layers: input > hidden(s) > output - **T 3.1 Universal Approximation Theory**: any continuous function can be approximated with DNN ##### Training: - **Backpropagation**: - **given**: training set $\ell = \{x(k), d(k)\}_{k=1}^K$, $\alpha$, network with reasonble random configs - **find**: optimal weights to mimic training set - error signal $e_j(k) = d_j(k) - y_j(k)$ - error energy $E_j(k) = \frac{1}{2}e_j^2(k)$ whole network $E(k) = \sum_{j} E_j(k)$ avg risk: $\bar E(k) = \frac{1}{K} \sum_{k=1}^K E(k)$ 1. for each weight from $i$ to $j$ (and next layer $l$) in each layer *backwards*: $\delta_j(k) = -\frac{\partial E(k)}{\partial v_j(k)} = \begin{cases} e_j(k) & \cdot & \Phi_j'(v_j(k)) & \text{if j output layer} \\ \sum_l w_{lj}(k) \delta_l(k) & \cdot & \Phi_j'(v_j(k)) & \text{if j hidden layer} \end{cases}$ $\Delta w_{ji}(k) = \alpha \delta_j(k) y_i(k)$ 2. repeat step 1 until $\bar E(k)$ below specified threshold - **with momentum:** - combines the advantages of low and high learning rate: stablizes the trajectory in the weight space and speeds up the learning speed towards steady directions: $\qquad \Delta w_{ji}(k) = \beta \Delta w_{ji}(k-1) + \alpha \delta_j(k) y_i(k)$ - *Batch* learning (offline): all K samples is 1 epoch, update weights once per epoch - *Online* learning: update weights for *each* sample datapoint (stochastic) - Cross-Validation: - training set (90%): - estimation subset (90%) for actual training - validation subset (10%) for picking best model (tune hyperparameters) - test set (10%) for evaluating the *final* model ##### Binary Classifier (Rosenblatt's Perceptron): - single-layer (0 hidden layers) with only 1 binary output node - $\Phi(v) = hardlim(v)$ (1 if v>0, otherwise 0) - can only classify linearly separable patterns (i.e. there exists a hyperplane that seperates the classes) - **Perceptron Training Algorithm**: - **given**: training set $D = \{(\vec x(k),d(k)) | k \in [s]\}$ (with k-th sample input $\vec x(k)$, desired output $d(k)$ and $x_0(k) = 1$ for bias) and learning rate $0 < \alpha \le 1$ - **find**: weights $\vec w(k)$ (with bias $w_0(k)$) at time $k$ that best mimic training set - **intuition**: $\vec w$ is perpendicular to the boundary, so if output for $k$ is wrong, nudge $\vec w$ towards $\aleph_1$ and away from $\aleph_0$ by adding or subtracting $x(k)$: 1) randomize initial weight $\vec w(0)$ 2) for $k \in [1; s]: \\ \qquad y(k) := \Phi(\vec w(t) \cdot \vec x(k)) \\ \qquad w_i(k+1) := w_i(k) + \alpha (d_i(k) - y_i(k))x_i(k)$ - this converges always (weights won't change) *if training set is linearly separable* (T2.1 Perceptron Convergence Theorem)! ##### Radial-Basis Function Networks - **Radial-basis function:** real-valued function only dependent on the distance from origin $c$: $\Phi(\vec x, c) = \varphi(\|x - c\|)$ where $\|\vec x\|_2 := \sqrt {\sum_i x_i^2}$ - i.e.: Multiquadrics $\Phi(x) = \sqrt{x^2+c^2}$ Inverse multiquadrics $\Phi(x) = \sqrt{x^2+c^2}^{-1}$ Guassian functions $\Phi(x) = exp(-\frac{x^2}{2\sigma^2}), \sigma > 0$ - essentially calculates $F(x) = \sum_{i=1}^K w_i \Phi(\|x-x^i\|)$ that *universally* and locally (as opposed to globally) approximate continuous function $f: \R^n \rightarrow \R$ given $K$ data points $(\vec x^i, d_i)$ on $f$ - single *hidden* layer with $n$ inputs and 1 output neuron, $S$ many neurons in the hidden layer where $S \leq K$ number of clusters with the centroids on the clusters becoming the interpolation points $\vec x^i$ - hidden layer usually non-linear activation function, output layer identity function or linear - step 1: k-means clustering algorithm to determine S step 2: backpropagation to train weights like normal - **k-means clustering:** **(1)** choose random $S$ centers $\vec c_j(0)$, **(2)** pick random sample $\vec x$, **(3)** the closest centroid $j(\vec x)$ is moved towards it: $\vec c_j(k+1) \mathrel{+}\mathrel{=} \alpha_c (\vec x(k) - \vec c_j(k))$, **(4)** repeat from *step (2)* until centers don't move much - **standard width of gaussian RBFs:** $\sigma = \frac{d_{max}}{\sqrt{2S}}$ where $d_{max}$ max distance between any two clusters ##### Recurrent Neural Networks: - dynamic neural network by giving it short/long-term memory through feedback - local feedback: single neuron inside the network global feedback: multiple hidden layers or whole network - the internal state $y_t$ is put back into the network as input in the next timestep, thus output $h_t = f(y_{t-1}, x_t)$ - **Lyapunov stability:** equilibrium state $\bar x$ is *(uniformly) stable*, if $\forall \varepsilon>0: \exists \delta>0: (\| x(0)-\bar x \| < \delta \implies \forall t>0: \| x(t)-\bar x \| < \varepsilon)$, i.e. for any bound $\varepsilon$, there is the *region of attraction* $\delta$, within which any initial state will stay bounded by $\varepsilon$ forever - **asymptotic stability:** if both stable *and* convergent ($x(t) \rarr \bar x$ as $t \rarr \infin$) within the ROA $\delta$ - if a **Lyapunov function** $V(x): \R^n \rarr \R$ is *positive-definite* in a small neighbourhood of $\bar x$, and $\frac{\partial V(x)}{\partial t}$ is *negative semidefinite* in that region, then $\bar x$ is stable (even *asymptotically* stable if derivative is *negative definite*) - **positive-definite**: has continuous partial derivatives of each state variable and $V(\bar x) = 0$ and $V(x) > 0$ if $x \neq \bar x$ (*semi-*: $\geq$, *negative-*: $<$) - **Hopfield Network**: $\vec x(k+1) = \Phi(W \vec x(k) + \vec b)$, usually $\Phi = satlins$ linear capped in $[-1; 1]$, converges always! #### 2) Fuzzy Logic ##### Fuzzy Sets and Membership Functions: - given universe set $X$, its subset can be defined by its **characteristic function** $A: X \rarr \{0, 1\}$ which, given $x \in X$ returns whether its in $A$ or not - **fuzzy set** has characteristic function $A: X \rarr [0, 1]$, returns the degree of membership (= **membership function**) - fuzzy set $A$ is *normal* if $sup_{x \in X}A(x) = 1$, otherwise *subnormal* - standard operators: - $A^c(x) = 1-A(x)$, does *not* satisfy Law of Contardiction/Excluded Middle - $(A \cup B)(x) = max\{A(x), B(x)\} = A(x) \lor B(x)$, commutative, distributive - $(A \cap B)(x) = min\{A(x), B(x)\} = A(x) \land B(x)$ - alt def (*Yager's connectives*) with $w \in (0, \infin)$: - $A^c(x) = (1-A(x)^w)^{1/w}$ - $(A \cup_w B)(x) = min\{1, (A(x)^w + B(x)^w)^{1/w}\}$ - $(A \cap_w B)(x) = 1 - min\{ 1, ((1-A(x))^w + (1 - B(x))^w)^{1/w} \}$ - $\alpha$-cut: fuzzy set to crisp set $^{\alpha}A=\{x|A(x) \geq \alpha \}$ or $^{\alpha+}A=\{x|A(x) > \alpha \}$ - **decomposition**: define $_{\alpha}A(x) = \alpha \cdot {^{\alpha}A(x)}$ which creates a horizontal & vertical slice at $\alpha$, then $A = \bigcup_{\alpha \in [0, 1]} {_{\alpha}A} = sup_{\alpha}\{ {_{\alpha}A(x)} \}$ ##### Fuzzy Relations and Propositions: - a (crisp) relation $R: X \rarr Y$ can be defined by its **characteristic function** $R: X \times Y \rarr \{0, 1\}$, so a **fuzzy relation** is $R: X \times Y \rarr [0, 1]$ - **proposition**: given linguistic variables $U, V$ (nouns e.g. AGE), values (=fuzzy set) $A, B$ (adj. e.g. Young), and optionally hedges $H$ (adv. e.g. very, not): "U is H A" - **conjunction** (with $U_i$ ling. var. over domains $X_i$): $A_1 \times A_2(x_1, x_2) = A_1(x_1) \land A_2(x_2)$ (matrix representation possible) - **condition proposition/implication**: "IF U is A, then V is B" *Lukasiewicz(Zadeh):* $R_Z(x,y) = min(1, 1-A(x)+B(y))$ *Correlation min*: $R_{cm}(x,y) = min(A(x),B(y))$ *Correlation product*: $R_{cp}(x,y) = A(x) * B(y)$ - matrix representation: express $A$ and $B$ as row vectors over their domains, then $R = A^T \cdot B$ with operator being $R(x,y)$ - **Inference**: *modus ponens*: $(P \Rightarrow Q) \land P = Q$, *modus tollens*: $(P \Rightarrow Q) = (\neg Q \Rightarrow \neg P)$ - single inference: **given:** Rule "IF $U$ is $A$, THEN $V$ is $B$" and Fact "$U$ is $A'$": **conclusion:** $B'(y) = A'(x) \circ R(x,y) = sup_{x \in X} min \{A'(x), R(x,y) \}$ (matr. mul. with row vector and matrix, $(*) \mathrel{:=} min$ and $(+) \mathrel{:=} max$ ) - $n$ antecedents and $k$ rules: **given:** Rules $R_i(x_1, ..., x_n, y)$ and Fact "$U_1$ is $A_1'$ and ... and $U_n$ is $A_n'$" **$k$ conclusions:** $B_i'(y) = A_{i1}' \times ... \times A_{in}' (x_1, ..., x_n) \circ R_i(x_1, ..., x_n, y)$ **aggregated conclusion:** $B'(y) = \sum_i B_i'(y)$ or $max_i\{B_i'(y)\}$ - **Defuzzification:** centroid $\bar y = (\sum_y y \cdot B'(y)) / (\sum_y B'(y))$ ##### T-S Fuzzy Model: - universal approximators that model a nonlinear plant $\rarr$ TSFM $\rarr$ local-linear fuzzy rules $\rarr$ defuzzify and control plant - Continuous FS: "IF $z_1(t)$ is $M_{i1}$ and ... and $z_p(t)$ is $M_{ip}$, THEN $\dot x(t) = A_i x(t)+B_i u(t), y(t) = C_i x(t)$" (for DFS: $\dot x(t) \rarr x(t+1)$) - disc. lin. system $x(t+1) = Ax(t)$ is locally stable if $\forall \lambda \in eig(A): |\lambda|<1$ within unit circle - cont. lin. system $\dot x(t) = Ax(t)$ is locally stable if $\forall \lambda \in eig(A): Re(\lambda)<0$ - (eigenvalues: solve $det(A-\lambda I) = (a-\lambda)(d-\lambda)-bc=0$) - DFS: globally asymp. stable if a common positive definite matrix P exists such that $A_i^T P A_i - P < 0, i=1,2,...,r$ ##### Evolutionary Algorithms: - iterative search prodecure that generates a *population* of candidate solutions (rather than 1 point like gradient), select best solutions and generates new random solutions based off of them - selection: - $(\mu + \lambda)$: $\mu$ parents create $\lambda$ offspring and best $\mu$ from $\mu + \lambda$ become next parents - $(\mu, \lambda)$: best $\mu$ from only $\lambda$ become next parents - proportional/roulette: probability of getting picked is their relative fitness - tournament: select $q$ random, pick best, repeat until full - variation: - mutation: binary/gaussian mutation - 1-point crossover: two parents $x, y \in \R^n$ at point $p$ produce two new offsprings $x' = (x_1, x_2, ..., x_{p-1}, y_p, ..., y_n)$ $y' = (y_1, y_2, ..., y_{p-1}, x_p, ..., x_n)$ - n-point crossover: at each crossover point swap the rest - PMX: pick mappings $x_i \leftrightarrow y_i$ for $i \in \{\text{random indices}\}$, swap values according to mappings, rest stays same - blending: average each components