Numerical Computation: Overflow, Underflow & Conditioning

Chapter 4: Numerical Computation

4.1 Overflow and Underflow

• Underflow happens when numbers near zero are rounded to zero, causing potential problems like division by zero or taking the logarithm of zero.
• Overflow arises when numbers with large magnitudes are approximated as infinity, leading to non-numerical results in further calculations.
• Softmax function is provided: $\operatorname{softmax}(x){i}=\frac{\exp \left(x{i}\right)}{\sum_{j=1}^{n} \exp \left(x_{j}\right)}$.
• With softmax, if $x_i$ is very negative, $\exp(x_i)$ underflows to zero; if $x_i$ is very large, $\exp(x_i)$ overflows.
• Normalizing the input to the softmax function, where $z = x - \max_i x_i$, combats overflow and underflow.
• The normalized softmax function is equivalent to the original function and stabilizes computation.

4.2 Poor Conditioning

• Condition number signifies how much a function's output changes with small input changes, defined by $\frac{|\delta f|}{|f|} \leq \text { condition number } \frac{|\delta x|}{|x|}$.
• A large condition number indicating high sensitivity to input errors.

4.3 Gradient-Based Optimization

• Most deep learning algorithms aim at minimizing an objective function $J(\theta)$ with parameters $\theta$.
• Gradient descent updates parameters $\theta$ in the opposite direction of the gradient: $\theta \leftarrow \theta-\epsilon \nabla_{\theta} J(\theta)$, where $\epsilon$ is the learning rate.
• Jacobian matrix contains all the partial derivatives of a function with multiple inputs and outputs, defined by $\boldsymbol{J}{i, j}=\frac{\partial f(\boldsymbol{x}){i}}{\partial x_{j}}$.
• Hessian matrix contains all second derivatives of a function, defined by $\boldsymbol{H}(f)(\boldsymbol{x}){i, j}=\frac{\partial^{2} f(\boldsymbol{x})}{\partial x{i} \partial x_{j}}$.
• Negative gradient indicates steepest descent and positive gradient indicates steepest ascent.

4.4 Constrained Optimization

• Optimization with constraints means minimizing or maximizing a function under specific conditions, such as $\underset{\boldsymbol{x}}{\operatorname{minimize}} f(\boldsymbol{x})$ subject to $g(\boldsymbol{x})=0$.
• Karush-Kuhn-Tucker (KKT) approach solves these problems using Lagrangian function: $L(\boldsymbol{x}, \lambda)=f(\boldsymbol{x})+\lambda g(\boldsymbol{x})$.
• $\lambda$ are the KKT multipliers in KKT approach.

4.5 Example: Linear Least Squares

• Seeks to minimize squared error in a system of equations $\mathbf{A}\mathbf{x} = \mathbf{b}$.
• Objective function is $J(\boldsymbol{x})=\frac{1}{2}|\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b}|_{2}^{2}$.
• Gradient is $\nabla_{\boldsymbol{x}} J(\boldsymbol{x})=\boldsymbol{A}^{\top}(\boldsymbol{A} \boldsymbol{x}-\boldsymbol{b})$.
• Normal equations are given by $\boldsymbol{A}^{\top} \boldsymbol{A} \boldsymbol{x}=\boldsymbol{A}^{\top} \boldsymbol{b}$.
• Solution: $\boldsymbol{x}=\left(\boldsymbol{A}^{\top} \boldsymbol{A}\right)^{-1} \boldsymbol{A}^{\top} \boldsymbol{b}$.
• $\boldsymbol{A}^{\top} \boldsymbol{A}$ may not always be invertible.

Lecture 26: Complexity Classes P and NP

The Complexity Class P

• P is the set of languages decidable in polynomial time on a deterministic single-tape Turing machine, represented as $P = \bigcup_{k} TIME(n^k)$.

• Polynomial time is robust against changes in the computation model and is "nice".

• "Nice" means, $n^{100}$ is polynomial and not polynomial like $2^{\log^2 n}$ (quasi-polynomial)

• Examples of Problems in P:

  • PATH: Determining if a directed graph has a directed path from s to t.
  • Connected: Determining if an undirected graph is connected.
  • SORT: Ordering a list of orderable items.
  • PRIMES: Determining if an integer represents a prime number.
  • MAXIMUM MATCHING: Determining if a bipartite graph has a matching of size at least k.

The Complexity Class NP

• NP is defined using verifiers, where intuition suggests that while finding a solution may be hard, recognizing one is easy.
• A verifier $V$ for a language $A$ defined as $A = {w | V \text{ accepts } \text{ for some string } c }$.
• The maximum length of certificate $c$ is polynomial in the length of $w$.
• A polynomial time verifier runs in polynomial time in the length of $w$.
• NP is the class of languages with polynomial time verifiers.
• NP is "nondeterministic polynomial time" because a nondeterministic Turing machine can guess and verify the certificate c.
• P vs NP question questions whether polynomial time verifiability implies polynomial time solvability.

Algorithmes de Hachage (Hashing Algorithms)

Définition (Definition)

• Hashing algorithms are functions that transform arbitrary-sized input into a fixed-size output, also known as a hash or fingerprint.

Objectifs (Goals/Objectives)

• Condenser l'information: Transform long documents into a short fingerprint.
• Vérifier l'intégrité des données: Detect unintentional data modification.
• Signatures numériques: More efficient to sign a hash (instead of signing the document entirely).
• Stockage de mots de passe: Store password hashes instead of passwords.

Propriétés Essentielles (Essential Properties)

• Efficacité: Hashing needs to be quick.
• Résistance à la préimage: Given a hash, it should be hard to find any input that hashes to that value.
• Résistance à la seconde préimage: Given an input, it should be hard to find a different input that hashes to the same value.
• Résistance aux collisions: It should be hard to find two different inputs that hash to the same value (a "collision").

Attaques (Attacks)

• Attaque par force brute: Trying all possible inputs until you get a target hash.
• Attaque d'anniversaire: Exploit the birthday paradox to find collisions more quickly.
• Attaques cryptanalytiques: Exploit specific weaknesses to the algorithm.

Exemples d'Algorithmes (Examples)

MD5 (Message Digest Algorithm 5)

• Taille du haché (Hash Size): 128 bits.
• Vulnérabilités (Vulnerabilities): Seriously vulnerable to collision attacks.
• Utilisation (Usage): Obsolete, should not be used when security is needed.

SHA-1 (Secure Hash Algorithm 1)

• Taille du haché (Hash Size): 160 bits.
• Vulnérabilités (Vulnerabilities): Vulnerable to collision attacks.
• Utilisation (Usage): Deprecated, should not be used for new development.

SHA-2 (Secure Hash Algorithm 2)

• Famille (Family): SHA-224, SHA-256, SHA-384, SHA-512.
• Tailles de haché (Hash Sizes): 224, 256, 384, 512 bits.
• Sécurité (Security): Considered generally secure, but SHA-3 is preferred for new applications.
• Utilisation (Usage): Heavily used for various application security.

SHA-3 (Secure Hash Algorithm 3)

• Basé sur (Based on): Keccak Algorithm.
• Tailles de haché (Hash Sizes): 224, 256, 384, 512 bits.
• Sécurité (Security): Designed to be an alternative if SHA-2 is attacked.
• Utilisation (Usage): Gaining popularity.

Conclusion (Conclusion)

• The hash algorithm depends on security.
• Stay informed about new findings from security experts.

Lecture 19: Transient Response

First Order Circuits

• This discusses the transient response of circuits.

Definition of Time Constant

• For an RC or RL circuit, the time constant $\tau$ is the time it will take for the response to decay to $e^{-1}$ or 36.8% of its first value.
• For RC Circuit: $$\tau = RC$$
• For RL Circuit:$$\tau = \frac{L}{R}$$

Procedure to Determine Transient Response

1. Determine the final initial condition
   • $x(0)$
2. Determine the final value
   • $x(\infty)$
3. Time constant
   • $\tau$

• Then use:
  • $$x(t) = x(\infty) + [x(0) - x(\infty)]e^{-t/\tau}, \quad t \geq 0$$
  • Where $x(t)$ can be $v(t)$ or $i(t)$.

Example 1

• Switch is opened at $t = 0$ and, $v(t)$ must be found for $t > 0$.
• the capacitor is charged to 15v.
• Initial Condition: $v(0) = 15V$.
• Final Value: $v(\infty) = 0V$.
• Time Constant: $\tau = RC = (50k\Omega)(2\mu F) = 0.1s$.
• $$v(t) = 0 + (15 - 0)e^{-t/0.1} = 15e^{-10t}V, \quad t > 0$$

Example 2

• Close Switch at $t=0$ to find $i_L(t)$ for $t > 0$.
• The current cannot change instantaneously.
• Initial Condition:* $i_L(0) = 0A$.
• Final Value:* $i_L(\infty) = \frac{20V}{(4+6)\Omega} = 2A$.
• Time Constant:* $\tau = \frac{L}{R} = \frac{0.5H}{10\Omega} = 0.05s$.
• Therefore: $$i_L(t) = 2 + (0 - 2)e^{-t/0.05} = 2 - 2e^{-20t}A, \quad t > 0$$

Summary

• The transient response can be found by finding the initial condition, final value, and time constant, then using the general equation $$x(t) = x(\infty) + [x(0) - x(\infty)]e^{-t/\tau}$$.

This content discusses overflow and underflow issues in numerical computation, particularly in the context of the softmax function. It explains how these issues can arise and provides a normalization technique to stabilize computation. Additionally, it touches on poor conditioning and its impact on function outputs.