2 posts tagged with "RL"

Sequential Decision Making​

• A sequence is a series of events or actions that occur in a specific order over time.
• Goal: select actions that maximize total expected future reward.
• It may require balancing immediate and long-term rewards.
• It may be better to sacrifice short-term gains for long-term benefits.
• It may require strategic behavior to achieve high rewards.

Example of SDM​

• Web Ads
  • Agent AdBot
    1. Choose and Ad $A_t$.
    2. Receives View time $O_t$
    3. Receives Click on Ad $R_t$
  • Environment
    1. Receives the Chosen Ad $A_t$.
    2. Provides the View time $O_{t+1}$.
    3. Provides the Click on Ad $R_{t+1}$.
• Robot picking trash
  • Agent Robot
    1. Moves arms to pickup trash $A_t$.
    2. Receives Camera image of the room $O_t$.
    3. Receives Reward if no trash on the floor $R_t$
  • Environment
    1. Receives robots action/arm movements $A_t$.
    2. Provides Camera Image of the room $O_{t+1}$.
    3. Provide reward of +1 $R_{t+1}$
• Robot making Pizza.
  • Agent Robot
    1. Makes an action from Action space $A_t$ (a range of possible actions, Arm Movements, Get Pizz from Oven, Place Pizza on Tray, Cut Pizza...).
    2. Receives Camera image of the kitchen $O_t$.
    3. Receives Reward if pizza is made correctly $R_t$
  • Environment
    1. Receives robots action/arm movements $A_t$.
    2. Provides Camera Image of the kitchen $O_{t+1}$.
    3. Provide reward appropriate to the action $R_{t+1}$.
  • Reward space
    • +10 Successfully made pizza.
    • +1 Get Pizza from oven.
    • +1 Place Pizza on tray.
    • +1 Get Packing box.
    • +1 Cut Pizza successfully.

Rewards​

• a scalar signal that indicates how well the agent is doing at time step $t$. (agent's performance)
• Examples of rewards:
  • Robot play soccor:
    • $+ve$ reward for scoring a goal.
    • $-ve$ reward for kicking the ball out of bounds.
  • Chess
    • $+ve$ reward for winning the game.
  • Autonomous drone flying stunt:
    • $+ve$ reward for following the intended trajectory.
    • $-ve$ reward for crashing into an obstacle.

History​

$H_t = \{O_1, A_1, R_1, O_2, A_2, R_2, ..., O_t, A_t, R_t\}$

• a sequence of past Observations, Actions, and Rewards up to time step $t$.
• Agent selects actions base on history.
• Environment selects observations and reward.

State​

$S_t = f(H_t)$

• The information used to determine what happens next.
• A function of the history that captures all relevant information for decision-making.

Environment State​

• $S_t^e$: the environment's private representation of the current state.
• It used to generate next observation and reward.
• It is not directly accessible to the agent (Invisible to the agent).
• If it is visible to the agent, it may contain information not required by the agent to make decisions (e.g., the internal state of a robot's motors).

Agent State​

• $S_t^a$: the agent's private representation of its state.
• Information used to pick next action and used by RL algorithms to learn from experience.
• It can be a function of the history: $S_t^a = f(H_t)$

Information State​

$P[S_{t+1} | S_t] = P[S_{t+1} | S_1, \cdots, S_t]$

• It contains all useful information from the history as known as the Markov State.
• Probability[next state | current state] = Probability[next state | given the whole history]
• The future is independent of the past given the present.
• The dog example illustrates a situation where the agent needs to remember past signals in order to receive a food reward.
• Possible definitions of the agent state:
  • Last 3 events in the sequence
    • Example: bell ring → light → bell press
    • Useful when recent observations are enough to predict the reward
  • Counts of events
    • Example: number of lights, bell rings, and bell presses
    • Useful for compressing information, but it loses the order of events
  • Complete sequence
    • Example: bell ring → light → bell press → bell ring → ...
    • Contains all past information, but can become too large and difficult to learn from
• Each state definition involves a trade-off between the amount of information stored and the complexity of learning.
• A good state should contain enough information to predict the next state and reward.

Markov assumption​

• Markov assumption is popular because it simplifies decision-making in RL.
• A Markov state can always be created by defining the state as the full history:
  • $S_t = H_t$
  • This includes all past observations, actions, and rewards.
  • It satisfies the Markov property because no extra past information is needed.
• However, using the full history creates a very large state space.
  • More computation
  • More memory
  • More data required
  • Harder learning
• Ideally, the current observation is enough:
  • $S_t = O_t$
  • This means the current observation is a sufficient statistic of the history.
  • The agent does not need to remember the full past.
• Smaller state spaces are preferred because they reduce computational complexity and data requirements.
• The choice of state representation affects:
  • Computational complexity
  • Amount of data required
  • Final performance
• Main idea: A good state should be small, but still contain enough information to predict the next state and reward.

Markov Property​

• The current state contains all relevant information from the history needed to predict the future.
• The future is independent of the past given the present state.

Full Observable Environments, MCPs​

$O_t = S_t^a = S_t^e$

• Full observable: Agent is able to directly observe the environment.
• Agent State = Environment State = Information State
• Known as Markov Decision Process

Partially Observable Environments, POMDPs​

• Partially observable: Agent only observes partial information about the environment.
• Agent State != Environment State
• Agent must construct its own internal state (S_t^a)
• Ways to construct agent state:
  • Complete history:
    • (S_t^a = H_t)
  • Belief state:
    • (S_t^a = b(S_t^e))
    • Probabilities over possible environment states
  • RNN hidden state:
    • previous hidden state + current observation → new hidden state
• Known as Partially Observable Markov Decision Process, POMDP.
• Examples:
  • Soccer-playing robot with a camera and limited information about its exact location.
  • Share trading agent that observes current share price but not full market trends or company history.
  • Card games where opponent cards and deck order are hidden.

Exploration vs Exploitation​

• Exploration: Learn more about the environment, may lose immediate reward
• Exploitation: Exploit known information to maximize rewards
• Discover a good policy, while interacting with the environment, the agent must balance exploration and exploitation.
• These are key aspects of RL learning, due to trial-and-error learning and the need to maximize long-term rewards.
• Examples:
  • Playing Chess
    • Exploitation: Use familiar opening lines that have won in the past.
    • Exploration: Try a new opening sequence.
  • Online Advertisements
    • Exploitation: Show ads with the highest past click rate.
    • Exploration: Show different ads and collect feedback such as clicks or view time.
  • Gold Mining
    • Exploitation: Mine at the best-known location.
    • Exploration: Mine at a new location.

Bandits​

• Actions that are taken has no influence on next observations. (Slot machines)
• No delayed rewards.
• RL problem with one state.
• Examples:
  • Design of Clinical trials
  • Online ad suggestion, placement
  • Games
  • Web page personalization
• Action now, Reward now.
• Single State $(S_t = S_1)$.
• Set of Actions = $\{A_1, A_2, ..., A_n\}$.
• Reward space = $[0, 1]$.
• Learn a Stochastic Reward Function: Reward probabilities for actions are unknown in advance, so they must be learned stochastically through trial and error.

Online Ad suggestion​

$\text{PayOff} = \text{CTR} \times \text{Payment Rate}$

• How to maximize PayOff among hundreds thousands of ads?
• CTR, ClickThroughRate: Probability that users click on the ad.
• Payment Rate: Money paid by the advertiser for each click.
• Arms: $\{Ad_1, Ad_2, ..., Ad_n\}$
• Rewards: $\{ 0: \text{No Click}, 1: \text{Click} \}$
  • Assuming a uniform payment of $1 for all ads, maximizing revenue simplifies to accurately estimating the Click-Through Rate (CTR).
• Exploration vs. Exploitation: Should we display new ads with unknown CTRs to test them (Exploration), or continuously show top-performing ads with the highest historical CTR (Exploitation)?
  • No known optimal solution, but there are many heuristic approaches to balance exploration and exploitation.

$\epsilon$-Greedy​

• a common exploration strategy to balence getween exploiting the current best action and exploring new actions in order to learn an optimal policy.
• Select the Arm with highest average reward so far
• May get struck with no exploration.
• $\epsilon$: The probability of selecting a random arm and used a greedy selection.

Init, for Arm = 1 to k:
  Q(Arm) = 0
  N(Arm) = 0

Loop:
  # Explore
  A = Random action with probability 𝜖
  # Exploit
  A = argmax(Q(Arm)) with probability (1 - 𝜖)

  R = bandit(A)
  N(A) += 1
  Q(A) = Q(A) + (1 / N(A)) * (R - Q(A))

• Q: Estimated reward for each Arm
• N: Number of time each Arm is pulled.
• A: Action
• R: Reward

NewEstimate = OldEstimate + StepSize[Target - OldEstimate]

UCB​

$UCBValue = Q(A) + \sqrt{\frac{2 \ln(t)}{N(A)}}$

• used to balance between exploiting known good actions and exploring potentially better actions.
• Optimism in the face of uncertaintiy: It will choose actions systematically that have a high potential for being optimal based on both their estimated value and their uncertatity.
  • The uncertainty bonus represents the value of exploring that arm.

Init, for Arm = 1 to k:
  Q(Arm) = 0
  N(Arm) = 0

Loop:
  UCBValue = Q(A) + sqrt((2 * log(t)) / N(A))
  A = argmax(UCBValue)
  R = bandit(A)

  N(A) += 1
  Q(A) = Q(A) + (1 / N(A)) * (R - Q(A))

• t: Time step
• Q: Estimated reward for each Arm
• N: Number of time each Arm is pulled
• A: Action
• R: Reward

General Update Rule same as $\epsilon$-Greedy.

Reinforcement Learning​

• Learn how to make a good sequence of decisions by interacting with the environment.

Characteristics of RL​

• Trial and Error: Based learning approach.
• Optimization: Find good sequences of actions or decisions.
• Delayed Consequences/Rewards: Takes time to relize the actions or decisions are good or bad.
• Exploration: Learn by making decisions or forming actions or through experiences. Trying new actions to discover their effects.
• Exploitation: Choosing actions with the highest expected reward, based on current knowledge.
• Generalization: Use previous experiences or knowledge to new or unseen situations effectively.

Framwork of RL​

• OpenAI Gym
• Torch RL
• AWS DeepRacer

RL Math​

Probability​

• Sample Space ($\Omega$): The set of all possible outcomes of a random experiment.

Bonferroni's Inequality​

$P(A \cap B) \geq P(A) + P(B) - 1$ $P(\cap^{n}_{i=1} A_i) \geq \sum_{i=1}^{n} P(A_i) - (n-1)$

• Gives a lower bound on the intersection probability which is useful when this probability is difficult to compute directly.
• It is useful when the probabilities of individual events are sufficiently large.

Boole's Inequality​

$P(\cup^{n}_{i=1} A_i) \leq \sum_{i=1}^{n} P(A_i)$

for any sets $A_1, A_2, ..., A_n$.

• It is useful when finding an upper bound for the probabilities of the union of events.

Bayes' Rule​

$P(A|B) = \frac{P(A \cap B)}{P(B)}$ $P(A\cap B) = P(B|A) P(A) = P(A|B) P(B)$ $P(A|B)P(B) = P(B|A)P(A)$ $P(A|B) = \frac{P(B|A) P(A)}{P(B)}$

• It allows us to compute the conditional probability $P(A|B)$ from the inverse conditional probability $P(B|A)$.
• Let $A_1, A_2, ..., A_n$ be a partition of the sample space $S$. Then let $B$ be any subset of $S$ we have:

$P(A_i|B) = \frac{P(B|A_i) P(A_i)}{\sum_{j=1}^{\infty} P(B|A_j) P(A_j)}$

Independent Events​

$P(A \cap B) = P(A) P(B)$

• A family $A_i :i \in I$ of events is independent if for every finite subset $J \subseteq I$ we have: $P\left(\bigcap_{i \in J} A_i\right) = \prod_{i \in J} P(A_i)$

• The pair-wise independence of events does not imply their mutual independence.

Conditional Independence​

$P(A \cap B|C) = P(A|C) P(B|C)$

• where $P(C) > 0$.
• or equivalently, $P(A|B \cap C) = P(A|C)$ and $P(B|A \cap C) = P(B|C)$.

Induced Probability Function​

$P_X(x_i) = P\big(\{w_j \in \Omega : X(w_j) = x_i\}\big)$

• $\Omega = \{w_1, w_2, ..., w_m\}$ is the sample space.
• $X$ is a random variable with range $X = \{x_1, x_2, ..., x_n\}$.
• The result set $\{w_j \in \Omega : X(w_j) = x_i\}$ is the set of all outcomes in the sample space that map to the value $x_i$ under the random variable $X$.

Cumulative Distribution Function (CDF)​

$F_X(x) = P_X(X \leq x) \quad \forall x \in \mathbb{R}$

• $F_X(x)$ is a cdf $\iff$ the following conditions hold:
  • Monotonicity: $F_X(x)$ is non-decreasing.
  • Limiting values: $\lim_{x \to -\infty} F_X(x) = 0$ and $\lim_{x \to \infty} F_X(x) = 1$.
  • Right-Continuity: $\lim_{y \downarrow x} F_X(y) = F_X(x) \quad \forall x \in \mathbb{R}$.

F_X(t)

1.0 |                         ●────────────
    |                         ↑  ↑  ↑
    |                      3.001 3.01 3.1
0.7 |              ●─────────○
    |              ↑  ↑  ↑
    |           2.001 2.01 2.1
0.3 |     ●────────○
    |     ↑  ↑  ↑
    |  1.001 1.01 1.1
0.0 |─────○
    +-------------------------------------- t
          1         2         3
          x         x         x

Continuous & Discrete Random Variables​

• if $X$ is continuous, then $F_X(x)$ is continuous and differentiable almost everywhere. The probability density function (pdf) is defined as: $f_X(x) = \frac{d}{dx} F_X(x)$
• if $X$ is discrete, then $F_X(x)$ is a step function and the probability mass function (pmf) is defined as: $p_X(x_i) = P(X = x_i)$

1 ────────────────────────━━━━━━━━
                        ╱
                      ╱
                    ╱
                  ╱
0 ━━━━━━━━━━━━━━━───────────────── x

1 ─────────────────────────●━━━━━━
                           │
0.7 ─────────────●━━━━━━━━━○
                 │
0.3 ─────●━━━━━━━○
         │
0 ━━━━━━━○──────────────────────── x
         1         2         3

1 ──────────────────────────━━━━━━
                          ╱
                        ╱
0.7 ───────────●━━━━━━━
               │
0.5 ───────────○
             ╱
           ╱
0 ━━━━━━━━──────────────────────── x
               a

Probability Mass Function (PMF)​

• A discrete random variable $X$ is given by $f_X(x) = P(X=x)$ for $x \in \mathbb{R}$.
• It represents the probability that the first success occurs exactly on the $x$-th trial in a sequence of independent trials.

Probability Density Function (PDF)​

• A continuous random variable $X$ is given by $f_X(x)$ for $x \in \mathbb{R}$.
• The probability is calculated as the area under the probability density function over a specific interval.

Expectation​

$E[X] = \sum x P(X=x) \quad \text{if } X \text{ is discrete}$

$E[X] = \int_{-\infty}^{\infty} x f_X(x) dx \quad \text{if } X \text{ is continuous}$

• Linearity: $E[aX + bY + c] = aE[X] + bE[Y] + c$ for any constants $a$, $b$, and $c$.
• Non-negativity: If $X \geq 0$ then $E[X] \geq 0$ because it is a weighted average of non-negative values.
• Monotonicity: If $X \geq Y$ then $E[X] \geq E[Y]$ because it is a weighted average of values that are greater than or equal to the corresponding values of $Y$.
• Boundedness: If $a \leq X \leq b$ then $a \leq E[X] \leq b$ because it is a weighted average of values that are bounded by $a$ and $b$.

a ●──────────────●──────────────● b
       가능한 값들    평균
                   E[X]

Moments​

$\mu'_n = E[X^n] \quad \forall n \in \mathbb{N}$

• The $n^{th}$ central moment of $X$ is: $\mu_n = E[(X - E[X])^n] = E(X - \mu)^n$

• 1th central moment is the mean, $\mu_1 = E[X]$.

• 2th central moment is the variance, $\mu_2 = E[(X - E[X])^2] = \text{Var}(X)$.

  • It emphasizes the variability of the distribution.
  • $\text{Var}(aX + b) = a^2 \text{Var}(X)$ for any constants $a$ and $b$.

• 3th central moment is the skewness, $\mu_3 = E[(X - E[X])^3]$.

  • It emphasizes the skewness of the distribution.

• 4th central moment is the kurtosis, $\mu_4 = E[(X - E[X])^4]$.

  • It emphasizes the tail behavior and extreme values of the distribution.

Covariance​

$\text{cov(X, Y)} = E[(X - E[X])(Y - E[Y])]$

• It measures how muc htwo random variables change together.
• Negative Covariance
• Near Zero Covariance
• Positive Covariance

Y: 시험 점수

높음  |                ●
     |          ●  ●
     |       ●
     |    ●
낮음  | ●
     +-------------------- X: 공부 시간
       적음             많음

       Cov(X,Y) > 0

Correlation​

$p(X, Y) = \frac{\text{cov(X, Y)}}{\sqrt{\text{Var}(X)\text{Var}(Y)}}$

• Individual variances must be non-zero.
• $p(X, Y)$ lies in the range $[-1, 1]$.

Joint Distributions​

$f_{X,Y}:\mathbb{R}^2\to[0,1], \\ f_{X,Y}(x,y) = P(X=x, Y=y) \quad \text{if } X, Y \text{ are discrete}$

• Joint Probability Mass Function (PMF) for discrete random variables $X$ and $Y$.

Y
1 ┤  ● 1/4       ● 1/4
  │ (0,1)       (1,1)
0 ┤  ● 1/4       ● 1/4
  │ (0,0)       (1,0)
  └──────────────────── X
      0           1

Marginal Distributions​

$f_X(x) = \sum_{y} f_{X,Y}(x,y) \\ f_Y(y) = \sum_{x} f_{X,Y}(x,y)$

• Fixing one variable and summing over the other variable gives the marginal distribution of the fixed variable.

             Y=0       Y=1       행의 합
X=0          0.10      0.20        0.30
X=1          0.30      0.40        0.70
             ─────────────────────────
열의 합       0.40      0.60        1.00

• $f_X(0) = 0.10 + 0.20 = 0.30$: sum of the first row.
• $f_X(1) = 0.30 + 0.40 = 0.70$: sum of the second row.
• $f_Y(0) = 0.10 + 0.30 = 0.40$: sum of the first column.
• $f_Y(1) = 0.20 + 0.40 = 0.60$: sum of the second column.
• Marginalization: It sums or integrates over all possible values of an unwanted variable to obtain the distribution of the variable of interest.

Conditional Distributions​

$f_{X|Y}(x|y) = P(X = x | Y = y) = \frac{f_{X,Y}(x,y)}{f_Y(y)} \quad \text{if } f_Y(y) > 0$

• It represents the probability distribution of $X$ given that $Y$ has a specific value.
• If $f_Y(y) = 0$, then $f_{X|Y}(x|y)$ is undefined.

Bernoulli Distribution​

$X = \begin{cases} 1, & \text{with probability } p \\ 0, & \text{with probability } 1-p \end{cases}$

• $E[X] = p$
• $\text{Var}(X) = p(1-p)$
• The outcome of a Bernoulli trial is either a success (1) or a failure (0).

Binomial Distribution​

• probability of success in a single trial: $p$
• probability of failure in a single trial: $q = 1 - p$

$P(X = x|n, p) = \binom{n}{x} p^x q^{n-x} \\ \text{where} \binom{n}{x} = \frac{n!}{x!(n-x)!}, \quad 0 \leq x \leq n$

• $E[X] = np$
• $\text{Var}(X) = npq = np(1-p)$
• The binomial distribution describes the number of successes in a fixed number of independent Bernoulli trials.
• $X \sim \text{Binomial}(10, 0.7)$
  • $P(X = 7) = \binom{10}{7} (0.7)^7 (0.3)^3 \approx 0.2668$

Geometric Distribution​

• probability of success in a single trial: $p$
• probability of failure in a single trial: $q = 1 - p$

$P(X = x|p) = (q^{x-1}) p \\ \text{where } x = 1, 2, 3, ...$

• $E[X] = \frac{1}{p}$
• $\text{Var}(X) = \frac{q}{p^2}$
• The geometric distribution describes the number of trials before the first success in a sequence of independent Bernoulli trials.
• $X \sim \text{Geometric}(0.7)$
  • $P(X = 3) = (0.3)^2 (0.7) \approx 0.063$

Uniform Distribution​

$f_X(x|a,b) = \begin{cases} \frac{1}{b-a}, & a \leq x \leq b \\ 0, & \text{otherwise} \end{cases}$

• $E[X] = \frac{a+b}{2}$
• $\text{Var}(X) = \frac{(b-a)^2}{12}$
• The uniform distribution describes a continuous random variable that has an equal probability of taking any value within a specified range.
• The probability depends on the length of the interval, not its location.

Normal Distribution​

$f_X(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}, \quad -\infty < x < \infty$

$X \sim N(\mu, \sigma^2)$

• Central Limit Theorem: the distribution of the sum (or average) of a large number of independent, identically distributed variables will be approximately normal, regardless of the underlying distribution.

$\bar{X} = \frac{1}{n} \sum_{i=1}^{n} X_i \approx N\left(\mu, \frac{\sigma^2}{n}\right)$

Multivariate Normal Distribution​

$N(x|\mu, \Sigma) = \frac{1}{\sqrt{(2\pi)^D |\Sigma|}} e^{-\frac{1}{2} (x-\mu)^T \Sigma^{-1} (x-\mu)}$

• $\mu$ is the $D$-dimensional mean vector.
• $\Sigma$ is the $D \times D$ covariance matrix.
• $|\Sigma|$ is the determinant of the covariance matrix.

Beta Distribution​

$f(x|\alpha, \beta) = \frac{\Gamma(\alpha + \beta)}{\Gamma(\alpha)\Gamma(\beta)} x^{\alpha - 1} (1 - x)^{\beta - 1}, \quad 0 < x < 1$

• $\Gamma(n) = (n-1)!$ is the gamma function.
• $E[X] = \frac{\alpha}{\alpha + \beta}$
• $\text{Var}(X) = \frac{\alpha \beta}{(\alpha + \beta)^2 (\alpha + \beta + 1)}$

α < β                  α = β                  α > β

높이                   높이                   높이
│╲                     │    ╭──╮             │        ╱
│ ╲___                 │  ╭─╯  ╰─╮           │    ___╱
└──────── x            └────────── x         └──────── x
0        1             0          1           0        1

0 쪽 강조              가운데 강조             1 쪽 강조

Beta(8,2)                 Beta(80,20)

       ╭────╮                    /\
     ╭─╯    ╰─╮                 /  \
─────╯        ╰───        ─────/────\─────
         0.8                      0.8

불확실성 큼                 불확실성 작음

• $p | \text{data} \sim \text{Beta}(\alpha + s, \beta + f)$
  • where new observations are $s$ successes and $f$ failures.
• The Beta distribution is a distribution of success probabilities for a Bernoulli or Binomial distribution.
• Application
  • Measuring uncertainty in the probability of success for a Bernoulli or Binomial distribution.
  • Conversion rate or click-through rate (CTR) in online advertising.
  • Defect rate in manufacturing.

Linear Algebra​

Axioms of Vector Spaces​

• Commutative Law: $u + v = v + u, \quad \forall u, v \in V$
• Associative Law: $(u + v) + w = u + (v + w), \quad \forall u, v, w \in V$
• Additive Identity: $\exists 0 \in V$ such that $v + 0 = v, \quad \forall v \in V$
• Additive Inverse: $\forall v \in V, \exists -v \in V$ such that $v + (-v) = 0$
• Distributive Law:
  • $a(u + v) = au + av, \quad \forall a \in F, u, v \in V$
  • $(a + b)v = av + bv, \quad \forall a, b \in F, v \in V$
• Associative Law: $(ab)v = a(bv), \quad \forall a, b \in F, v \in V$
• Unitary Law: $1v = v, \quad \forall v \in V$

Subspace​

• $x + \alpha y \in W, \quad \forall x, y \in W, \forall \alpha \in \mathbb{R}$

Norm​

$f: \mathbb{R}^n \to \mathbb{R}$

• It outputs a real number that represents the length or size of a vector in a vector space.

$x=(x_1,x_2,\ldots,x_n) \mapsto f(x)=\lVert x\rVert$

• Non-negativity: $\forall x \in \mathbb{R}^n, \quad \lVert x\rVert \geq 0$
• Definiteness: $f(x) = 0 \iff x = 0$
• Homogeneity: $\forall x \in \mathbb{R}^n, \quad \forall t \in \mathbb{R}, f(tx) = |t| f(x)$
• Triangle inequality: $\forall x,y \in \mathbb{R}^n, \quad f(x+y) \leq f(x) + f(y)$
  • $\lVert x + y \rVert \leq \lVert x \rVert + \lVert y \rVert$
• A norm is non-negative, only the zero vector has a norm of zero, scaling a vector by two doubles its norm, and the direct distance cannot be greater than the detoured distance.

$\lVert x \rVert_p = (\sum_{i=1}^{n} |x_i|^p)^{\frac{1}{p}}, \quad p \geq 1$

• L1 norm: $\lVert x \rVert_1 = \sum_{i=1}^{n} |x_i|$
  • Manhattan distance.
• L2 norm: $\lVert x \rVert_2 = \sqrt{\sum_{i=1}^{n} |x_i|^2}$
  • Euclidean distance.
• L-infinity norm: $\lVert x \rVert_\infty = \max_i|x_i|$
  • $\lVert (3, 4) \rVert_\infty = \max\{3, 4\} = 4$

$\lVert A \rVert_F = \sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}|^2} = \sqrt{\text{tr}(A^T A)}$

• Frobenius norm: $A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$
  • $\lVert A \rVert_F = \sqrt{1^2 + 2^2 + 3^2 + 4^2} = \sqrt{30}$
  • It is the square root of the sum of the absolute squares of its elements.

Span​

$span\{x_1, x_2, ..., x_n\} = \{ \alpha_1 x_1 + \alpha_2 x_2 + ... + \alpha_n x_n : \alpha_n \in \mathbb{R}\}$

• A set of vertors $X = \{x_1, x_2, ..., x_n\}$ in a vector space $V$ is said to span $V$ if every vector in $V$ can be expressed as a linear combination of the vectors in $X$.
• Span is the entire region that can be reached by scaling and adding the given vectors.

Range​

$R(A) = \{\alpha_1 a_1 + \alpha_2 a_2 + ... + \alpha_n a_n : \alpha_n \in \mathbb{R}\}$

• The range of a matrix $A$ is the set of all possible linear combinations of its column vectors.
• Same as the columnspace of the matrix $A$.

Nullspace​

$N(A) = \{x \in \mathbb{R}^n : Ax = 0\}$

• A set of all vectors that equal 0 when multiplied by the matrix $A$.
• The dimensionality of the nullspace is called the nullity of the matrix $A$.

Linear Independence​

• A set of vectors $\{v_1, v_2, ..., v_n\}$ is said to be linearly independent if the only solution to the equation $\alpha_1 v_1 + \alpha_2 v_2 + ... + \alpha_n v_n = 0$ is $\alpha_1 = \alpha_2 = ... = \alpha_n = 0$.
• Column rank: The maximum number of linearly independent column vectors in a matrix.
• Row rank: The maximum number of linearly independent row vectors in a matrix.
• If one row vector is a combination of other row vectors, then it is linearly dependent.
• The number of rows that are removed due to redundancy is the Rank of the matrix.
• Due to the redundancy, the number of directions which is vanishing is the Nullity of the matrix.

Rank​

$Rank(A) = \text{dim}(R(A)), \quad A \in \mathbb{R}^{m \times n}$

• $rank(A) \leq \min(m, n), \quad A \in \mathbb{R}^{m \times n}$
  • if $rank(A) = min(m, n)$, then $A$ is said to be full rank.
  • Rank cannot exceed the number of rows or columns in the matrix.
• $rank(A) = rank(A^T), \quad A \in \mathbb{R}^{m \times n}$
  • The rank of a matrix is equal to the rank of its transpose.
  • The amount of independent information in the rows is equal to the amount of independent information in the columns.
• $rank(AB) \leq \min(rank(A), rank(B)), \quad A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times p}$
  • The information content of the product of two matrices cannot exceed the information content of either matrix.
• $rank(A + B) \leq rank(A) + rank(B), \quad A, B \in \mathbb{R}^{m \times n}$
  • The information content of the sum of two matrices cannot exceed the sum of the information content of each matrix.

Orthogonal Matrices​

$U \in \mathbb{R}^{n \times n} \text{ is orthogonal } \iff v_i^T v_j = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \neq j \end{cases}$

• $UU^T = U^TU = I_n$
• $\lVert Ux \rVert_2 = \lVert x \rVert_2, \quad \forall x \in \mathbb{R}^n$
• Orthonormal: A set of vectors is orthonormal if they are all unit vectors and orthogonal to each other.
• Rotation: $R(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$
• Reflection: $R = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$

Quadratic Form​

$Q(x) = x^T A x, \quad A \in \mathbb{R}^{n \times n}$

• The quadratic form $x^TAx$ gives a scalar value that measures the cost, energy, or weighted magnitude of the vextor $x$, according to the quadratic surface defined by the matrix $A$.
  • Positive definite: $Q(x) > 0, \quad \forall x \neq 0$
  • Positive semi-definite: $Q(x) \geq 0, \quad \forall x \neq 0$
  • Negative definite: $Q(x) < 0, \quad \forall x \neq 0$
  • Negative semi-definite: $Q(x) \leq 0, \quad \forall x \neq 0$
  • Indefinite: $Q(x)$ can be positive or negative for different $x \neq 0$

• 행렬의 정부호성(양의 정부호, 양의 준정부호, 음의 정부호, 음의 준정부호, 부정정부호)

$A^TA = A^TA \implies Q(x) = x^T A^T A x = (Ax)^T (Ax) = \lVert Ax \rVert^2 \geq 0$

• Always positive semi-definite because it is the square of the norm of the vector $Ax$.

Eigenvalues & Eigenvectors​

$\lambda \in \mathbb{R} \text{ is an eigenvalue of } A \in \mathbb{R}^{n \times n} \iff A\vec{x} = \lambda \vec{x} , \quad \vec{x} \in \mathbb{R}^n, \vec{x} \neq 0$

• An eigenvector is a nonzero vector that remains on the same line when transformed by a matrix.
• Its eigenvalue tells us how much the vector is scaled and whether its direction is reversed.

$\text{det}(A - \lambda I) = 0$

• $A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix}$
• $A - \lambda I = \begin{bmatrix} 4 - \lambda & 1 \\ 2 & 3 - \lambda \end{bmatrix}$
• $\text{det}(A - \lambda I) = (4 - \lambda)(3 - \lambda) - 2 = \lambda^2 - 7\lambda + 10 = (\lambda - 5)(\lambda - 2) = 0$
• $\lambda_1 = 5, \quad \lambda_2 = 2$

$\text{tr}(A) = \sum_{i=1}^{n} \lambda_i$

• The trace is the sum of the scaling factors along all eigenvector directions.

$\text{det}(A) = \prod_{i=1}^{n} \lambda_i$

• The determinant is the product of the eigenvalues, representing the overall signed scaling factor for area or volume.

$rank(A) = \text{number of non-zero eigenvalues of } A$

• For a diagonalizable matrix, the rank equals the number of nonzero eigenvalues, counted with multiplicity.

$\lambda_i (A^{-1}) = \frac{1}{\lambda_i(A)}$

• The eigenvalues of the inverse of a matrix are the reciprocals of the eigenvalues of the original matrix.

$A \vec{x} = \lambda \vec{x} \\ \implies A^{-1} A \vec{x} = A^{-1} \lambda \vec{x} \\ \implies \vec{x} = \lambda A^{-1} \vec{x} \\ \implies A^{-1} \vec{x} = \frac{1}{\lambda} \vec{x}$

Diagonalization​

$S = \begin{bmatrix} \vdots & \vdots & \cdots & \vdots \\ \vec{v_1} & \vec{v_2} & \cdots & \vec{v_n} \\ \vdots & \vdots & \cdots & \vdots \end{bmatrix}$ $AS = \begin{bmatrix} \vdots & \vdots & \cdots & \vdots \\ \lambda_1\vec{v_1} & \lambda_2\vec{v_2} & \cdots & \lambda_n\vec{v_n} \\ \vdots & \vdots & \cdots & \vdots \end{bmatrix} \\ = \begin{bmatrix} \vdots & \vdots & \cdots & \vdots \\ \vec{v_1} & \vec{v_2} & \cdots & \vec{v_n} \\ \vdots & \vdots & \cdots & \vdots \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{bmatrix} \\ = S\Lambda$

• $S^{-1}AS = \Lambda$
  • $AS = S\Lambda$
  • $S^{-1}AS = S^{-1}S\Lambda = \mathbb{I}\Lambda = \Lambda$
  • A matrix $A$ that appears complicated in the original coordinate system becomes the diagonal matrix $\Lambda$ when expressed in the eigenvector coordinate system.
• $A = S\Lambda S^{-1}$
  • In the eigenvector basis, the matrix $A$ becomes the diagonal matrix $\Lambda$.

Symmetric Matrices​

• A real symmetric matrix satisfies $A=A^T$.
• All eigenvalues of a real symmetric matrix are real.
• A real symmetric matrix has a complete set of orthonormal eigenvectors.
• Therefore, the eigenvector matrix $S$ is orthogonal.

• The diagonalization of a symmetric matrix is

• $S$ contains the orthonormal eigenvectors of $A$.
• $\Lambda$ contains the corresponding eigenvalues.
• $S^T$ converts $x$ into the eigenvector basis.
• $\Lambda$ scales each eigenvector direction by its corresponding eigenvalue.
• $S$ converts the result back to the original basis.

Definiteness of Symmetric Matrices​

• Using $A=S\Lambda S^T$ and $y=S^Tx$,

• $y_i$ is the component of $x$ along the $i$-th eigenvector.

• Since $y_i^2\geq0$, the sign of $x^TAx$ depends entirely on the signs of the eigenvalues.

• If all eigenvalues are positive, $A$ is positive definite.

• If all eigenvalues are non-negative, $A$ is positive semidefinite (PSD).

• If all eigenvalues are negative, $A$ is negative definite.

• If all eigenvalues are non-positive, $A$ is negative semidefinite (NSD).

• If $A$ has both positive and negative eigenvalues, $A$ is indefinite.
• The eigenvectors determine the principal directions of the quadratic surface.
• The eigenvalues determine the curvature and sign along those directions.
• The definiteness of a symmetric matrix is determined entirely by the signs of its eigenvalues.

Eigenvalues of a Positive Semidefinite Matrix​

• If $A$ is positive semidefinite, then

• For an eigenvector $\vec{x}\neq\vec{0}$ with eigenvalue $\lambda$,

• Since $\vec{x}\neq\vec{0}$,

• Therefore,

• Hence, all eigenvalues of a positive semidefinite matrix are non-negative.
• A zero eigenvalue means that the corresponding eigenvector direction is collapsed to the zero vector.

Singular Value Decomposition​

• Diagonalization is generally defined for square matrices, while singular value decomposition can be applied to any rectangular or square matrix.

• For $A\in\mathbb{R}^{m\times n}$,

• The columns of $V$ are the right singular vectors and represent orthonormal directions in the input space.
• The columns of $U$ are the left singular vectors and represent orthonormal directions in the output space.
• The diagonal entries of $\Sigma$ are the singular values.

• For each singular-vector pair,

• $\vec{v_i}$ is an input direction.

• $\sigma_i$ is the scaling factor.

• $\vec{u_i}$ is the corresponding output direction.

• The transformation $A$ can be interpreted as three steps:

  • $V^T$ expresses the input in the right singular-vector basis.
  • $\Sigma$ scales each direction by its singular value.
  • $U$ maps the scaled result into the output space.

• $U$ and $V$ are orthogonal matrices.

• The singular vectors and singular values are related to the eigenvectors and eigenvalues of $A^TA$ and $AA^T$.

• The rank of $A$ equals the number of nonzero singular values.
• SVD is commonly used for dimensionality reduction, data compression, noise reduction, pseudoinverses, and latent-factor analysis.

• $U$ is such that the $m$ columns of $U$ are the eigenvectors of $AA^T$, known as the left singular vectors of $A$.
• $V$ is such that the $n$ columns of $V$ are the eigenvectors of $A^TA$, known as the right singular vectors of $A$.
• $\Sigma$ is a rectangular diagonal matrix with each element being the square root of an eigenvalue of $AA^T$ or $A^TA$.
• SVD allows us to construct a lower rank approximation of a rectangular matrix.
  • Choose only the top $r$ singular values in $\Sigma$.
  • The corresponding columns in $U$ and rows in $V^T$ are also selected.
• $V$ represents the principal directions in the input space, $U$ shows where those directions are mapped in the output space, and $\Sigma$ shows how much each direction is scaled.

Gradient​

• The gradient with respect to $A$ is a matrix that shows how the function $f(A)$ changes with respect to each element of $A$.