Artificial Intelligence UIUC CS 440

Formula Sheet

Probability:

$P(X = x) = \text{Pr}(X = x)$ or $P(X = x) = \frac{d}{dx} \text{Pr}(X \leq x)$

$$P(X, Y) = P(X|Y)P(Y)$$ $$E[f(X,Y)] = \sum_{x,y} f(x,y)P(X = x, Y = y)$$

MAP Decision:

$$f(x) = \arg \max_{y} P(Y = y|X = x)$$

Bayes Error Rate:

$$E = \sum_{x} P(X = x) \min_{y} P(Y = y|X = x)$$

Precision:

$$\text{Precision} = \frac{P(Y = 1|f(X) = 1)}{TP} = \frac{TP}{TP + FP}$$

Recall-Sensitivity:

$$\text{Recall} = P(f(X) = 1|Y = 1) = \frac{TP}{TP + FN}$$

Specificity:

$$\text{Specificity} = P(f(X) = 0|Y = 0) = \frac{TN}{TN + FP}$$

Naive Bayes:

$$f(x) = \arg \max_{y} \left[ \ln P(Y = y) + \sum_{i=1}^{n} \ln P(W = w_i|Y = y) \right]$$

Laplace Smoothing:

$$P(W = w_i|Y = y) = \frac{k + \text{Count}(w_i,y)}{k + \sum_{v} \text{Count}(v,y)}$$

HMM:

$$v_1(j) = \pi(j)b_j(x_1)$$ $$v_t(j) = \max_{v-1} (i)a_{ij}b_j(x_t)$$ $$\psi_t(j) = \arg \max_{v-1} (i)a_{ij}b_j(x_t)$$ $$y^*(T) = \arg \max_{v}(T)(i)$$ $$y^*(t) = \psi_{t+1}(y^*(t+1))$$

Demographic Parity:

$$P(f(X)|A = 1) = P(f(X)|A = 0)$$

Equal Odds:

$$P(f(X)|Y, A = 1) = P(f(X)|Y, A = 0)$$

Predictive Parity:

$$P(Y|f(X), A = 1) = P(Y|f(X), A = 0)$$

Learning:

$$\mathcal{L} = E[\ell(Y, f(X))], \ell_{\text{emp}} = \frac{1}{n} \sum_{i=1}^{n} \ell(y_i, f(x_i))$$

Linear Regression:

$$f(x) = w^T x + b$$ $$\mathcal{L} = \frac{1}{n} \sum_{i=1}^{n} \mathcal{L}_i, \mathcal{L}_i = \frac{1}{2} (e_i^2), e_i = f(x_i) - y_i$$

Linear Classifier:

$$f(x) = \arg \max (Wx + b)$$

Perceptron:

$$w_c = \begin{cases} w_c - \eta x & c = \arg \max (Wx + b) \\ w_c + \eta x & c = y \\ w_c & \text{otherwise} \end{cases}$$

Softmax:

$$f_c(x) = \frac{\exp(w_c^T x + b_c)}{\sum_{k=1}^{K} \exp(w_k^T x + b_k)} \quad \text{as } P(Y = c|x)$$

Sigmoid:

$$\sigma(w^T x + b) = \frac{1}{1 + e^{-(w^T x + b)}} \quad \text{as } P(Y = 1|x)$$

Cross Entropy:

$$\mathcal{L} = -\ln f_y(x), \quad \frac{\partial \mathcal{L}}{\partial f_c(x)} = \begin{cases} \frac{-1}{f_y(x)} & c = y \\ 0 & \text{otherwise} \end{cases}$$

SGD (Stochastic Gradient Descent):

$$w_c = w_c - \eta \frac{\partial \mathcal{L}}{\partial w_c} = \begin{cases} w_c - \eta (f_c(x) - 1)x & c = y \\ w_c - \eta f_c(x)x & \text{otherwise} \end{cases}$$

Pinhole Camera:

$$x' = \frac{x}{z}, \quad y' = \frac{y}{z}, \quad f' = \frac{f}{z}$$

Image Gradient:

$$h_x(x', y') = \frac{h(x' + 1, y') - h(x' - 1, y')}{2}$$ $$h_y(x', y') = \frac{h(x', y' + 1) - h(x', y' - 1)}{2}$$

Convolution:

$$y[k,l] = \sum_{i,j} x[k-i,l-j] \cdot h[i,j], \quad \frac{\partial h[i,j]}{\partial x[k-i,l-j]}$$

Max Pooling:

$$z[m] = \max \{ y[k] | (m-1)p+1 \leq k \leq mp \}, \quad \frac{\partial z[m]}{\partial y[j]} = \begin{cases} 1 & j = \arg \max \{ y[k] \} \\ 0 & \text{otherwise} \end{cases}$$

Admissible:

$$h(n) \leq h(n)$$

Consistent:

$$h(n) - h(m) \leq h(n,m)$$

Value Iteration:

$$u_i(s) = r(s) + \gamma \max_a \sum_{s'} P(s'|s, a)u_{i-1}(s')$$

Policy Evaluation:

$$u_t(s) = r(s) + \gamma \sum_{s'} P(s'|s, t)u_t(s')$$

Policy Improvement:

$$\pi_{t+1}(s) = \arg \max_a \sum_{s'} P(s'|s, a)u_t(s')$$

Alpha-Beta Max Node:

$$v = \max_{\text{child}}(v, \text{child}); \quad \alpha = \max(\alpha, \text{child})$$

Alpha-Beta Min Node:

$$v = \min_{\text{child}}(v, \text{child}); \quad \beta = \min(\beta, \text{child})$$

Expectiminimax:

$$u(s) = \begin{cases} \max_a \sum_{s'} P(s'|a, u(s')) & s \in \text{max states} \\ \min_a \sum_{s'} P(s'|a, u(s')) & s \in \text{min states} \end{cases}$$

Mixed Nash Equilibrium:

$$P(A = 0) = \frac{0.8}{0.0}, P(A = 1) = \frac{1.0}{1.0}, P(B = 0) = \frac{1.0}{1.0}, P(B = 1) = \frac{1.0}{1.0}$$

Unification:

$$\mathcal{S}: \{T_p, V_p\} \rightarrow \{T_v, V_v\} \text{ such that } S(P) = S(Q) = U$$

CBOW Generative:

$$\mathcal{L} = -\frac{1}{T} \sum_{t=1}^T \sum_{c \neq 0} \ln \frac{\exp(v'_{T_v})}{\sum \exp(v'_{T_v+j})}$$

Skip-gram Contrastive:

$$\mathcal{L} = -\frac{1}{T} \sum_{t=1}^T \left( \sum_{v \in V_{s_t}(w)} \ln \frac{1}{1+e^{-v'}} + \sum_{v \in V_{s_t}(w)} \ln \frac{1}{1+e^{v'}} \right)$$

Transformer:

$$c_t = \sum_{s} \alpha(t, s)V_s$$

Attention:

$$\alpha(t, s) = \frac{\exp(q_t' k_s)}{\sum_s \exp(q_t' k_s)}$$

Model-based Learning:

$$P(S_{t+1}|s_t, a) = \frac{\text{Count}(s_t, a, S_{t+1}) + k}{\sum_s \text{Count}(s_t, a, s') + k}$$

On-policy learning:

$$W_a \leftarrow W_a + \eta \nabla_W \ln P(S_{t+1}|s_t, a)$$

Off-policy learning:

$$W \leftarrow W + \eta \nabla_W \ln P(S_{t+1}|s_t, a)$$

Epsilon-first:

$$N_{\text{first}} = \frac{1}{\epsilon}$$

Epsilon-greedy:

$$\text{If } z \leq \epsilon \text{ then explore,} z \in (0, 1)$$

TD-learning:

$$q_{\text{local}}(s_t, a) = r_t + \gamma \max_{a'} q(s_{t+1}, a')$$

SARSA:

$$q_{\text{local}}(s_t, a) = r_t + \gamma q(s_{t+1}, a+1)$$

Q-learning:

$$q_{t+1}(s_t, a) = q(s_t, a) + \eta \left[ \gamma q(s_{t+1}, a) - q(s_t, a) \right]$$

Deep Q:

$$\theta_{t+1} = \theta_t - \eta \frac{1}{2} \delta^2 (q(s_t, a) - q_{\text{local}}(s_t, a))^2$$

Policy Gradient:

$$\frac{\partial U(s)}{\partial \theta} = \mathbb{E} \left[ \frac{\partial P(\tau)}{\partial \theta} \frac{\partial \ln P(\tau)}{\partial \theta} v(\tau) \right] = \mathbb{E} \left[ \frac{\partial \ln P(\tau)}{\partial \theta} v(\tau) \right]$$

Standard Error:

$$M = \frac{1}{n} \sum_{i=1}^n Y_i, \quad \text{stdev}(M) = \frac{\sigma}{\sqrt{n}}$$