Developing Lifespan 1 (pt 1)

Simplex Method

• Focuses on efficiently searching corner points to find optimal linear programming (LP) solutions.

Road Map for the Simplex Method

• LPs can be converted to standard form.
• If an LP has an optimal solution, it also has an optimal Basic Feasible Solution (BFS).
• BFSs correspond to corner points in the feasible region.
• The simplex method helps efficiently find these corner points.

Standard Form Requirements

• Constraints must be equality constraints.
• All variables must be nonnegative.
• The right-hand side (RHS) of each constraint must be nonnegative.

Transforming an LP into Standard Form

• For constraints like $\sum_{j=1}^n a_{ij}x_j \leq b_i$ with $b_i \geq 0$, add a slack variable $s_i$:
  • $\sum_{j=1}^n a_{ij}x_j + s_i = b_i$, with $s_i \geq 0$.
• For constraints like $\sum_{j=1}^n a_{ij}x_j \geq b_i$ with $b_i \geq 0$, subtract a surplus variable $e_i$:
  • $\sum_{j=1}^n a_{ij}x_j - e_i = b_i$, with $e_i \geq 0$.
• If $b_i < 0$ in constraints like $\sum_{j=1}^n a_{ij}x_j \leq b_i$, multiply by -1:
  • $-\sum_{j=1}^n a_{ij}x_j \geq -b_i > 0$, then subtract surplus variable $e_i$:
    • $-\sum_{j=1}^n a_{ij}x_j - e_i = -b_i$, with $e_i \geq 0$.
• If $b_i < 0$ in constraints like $\sum_{j=1}^n a_{ij}x_j \geq b_i$, multiply by -1:
  • $-\sum_{j=1}^n a_{ij}x_j \leq -b_i > 0$, then add a slack variable $s_i$:
    • $-\sum_{j=1}^n a_{ij}x_j + s_i = -b_i$, with $s_i \geq 0$.
• If $x_i$ is unrestricted in sign, replace it with $x_i' - x_i''$ where $x_i', x_i'' \geq 0$.

Example: Farmer Leary's Land Allocation

• Problem: Farmer Leary has 10 acres to plant with wheat or corn, aiming to maximize profit with limited labor. Wheat yields $200 profit/acre, corn yields $300 profit/acre. Wheat requires 3 hours labor/acre, corn requires 2 hours labor/acre. Total labor available: 27 hours.
• Decision Variables: $x_1$ (acres of wheat), $x_2$ (acres of corn).
• LP Formulation:
  • Maximize: $200x_1 + 300x_2$
  • Subject to: $x_1 + x_2 \leq 10$, $3x_1 + 2x_2 \leq 27$, $x_1, x_2 \geq 0$
• Standard Form:
  • Maximize: $200x_1 + 300x_2$
  • Subject to: $x_1 + x_2 + s_1 = 10$, $3x_1 + 2x_2 + s_2 = 27$, $x_1, x_2, s_1, s_2 \geq 0$

Basic Feasible Solutions (BFS)

• Consider system of equations $Ax = b$ where $A$ is an $m \times n$ matrix with $m < n$ and $x \geq 0$.
• Set $n-m$ variables to 0. These are nonbasic variables.
• The remaining $m$ variables are basic variables.
• Remarks:
  • Setting $n-m$ variables to 0 results in $m$ equations with $m$ variables.
  • If unique solution exists, the solution is a basic solution.
  • If a basic solution has all nonnegative variables, it’s a BFS.
  • Corner points and BFSs correspond in standard form LPs.

Finding BFSs

• Consider:
  • $x_1 + x_2 + s_1 = 10$, $3x_1 + 2x_2 + s_2 = 27$, $x_1, x_2, s_1, s_2 \geq 0$
• $m = 2$, $n = 4$, so $n - m = 2$.
• Set $x_1 = x_2 = 0$, then $s_1 = 10$, $s_2 = 27$, giving BFS (0, 0, 10, 27).
• Set $x_1 = s_1 = 0$, then $x_2 = 10$, $s_2 = 7$, giving BFS (0, 10, 0, 7).
• Set $x_1 = s_2 = 0$, then $x_2 = 13.5$, $s_1 = -3.5$, which is not a BFS.
• Set $x_2 = s_1 = 0$, then $x_1 = 10$, $s_2 = -3$, which is not a BFS.
• Set $x_2 = s_2 = 0$, then $x_1 = 9$, $s_1 = 1$, giving BFS (9, 0, 1, 0).
• Set $s_1 = s_2 = 0$, then $x_1 = 7$, $x_2 = 3$, giving BFS (7, 3, 0, 0).

Simplex Method: Iterative Optimization

• Starts with a BFS and improves the objective value by changing the basis.
• Entering Variable: Nonbasic variable that increases the objective value most rapidly.
• Leaving Variable: Basic variable that first becomes 0 when entering variable increases.
• Consider BFS $(0, 0, 10, 27)$ with nonbasic variables $x_1$ and $x_2$.
  • Increase $x_1$ to 1: $s_1 = 9$, $s_2 = 24$, Objective Value = 200.
  • Increase $x_2$ to 1: $s_1 = 9$, $s_2 = 25$, Objective Value = 300.
• $x_2$ enters the basis as it has a larger effect on the objective function.
• Given $x_1 + x_2 + s_1 = 10$ and $3x_1 + 2x_2 + s_2 = 27$ with $x_1 = 0$:
  • $x_2 + s_1 = 10$ implies $s_1$ becomes 0 when $x_2$ increases to 10.
  • $2x_2 + s_2 = 27$ implies $s_2$ becomes 0 when $x_2$ increases to 13.5.
• $s_1$ leaves the basis because it becomes 0 first.
• To find new BFS, solve for $x_2$ and substitute:
  • $x_2 = 10 - x_1 - s_1$ goes to $3x_1 + 2(10 - x_1 - s_1) + s_2 = 27$, simplified to $x_1 - 2s_1 + s_2 = 7$.
• New set of equations: $x_2 + x_1 + s_1 = 10$ and $x_1 - 2s_1 + s_2 = 7$.

Summary of the Simplex Method

• Start with standard form LP.
• Find a BFS.
• Check if the current BFS is optimal.
• If not optimal, determine entering and leaving variables.
• Use Elementary Row Operations (EROs) to find the new BFS.
• Repeat from step 3.

Numerical Integration

• Approximates the definite integral of a function.

Newton-Cotes Formulae

• The approach replaces $f(x)$ with an interpolating polynomial $P(x)$.
• $P(x)$ is integrated exactly.
• $\int_a^b f(x) dx \approx \int_a^b P(x) dx$

Trapezoidal Rule

• Uses linear interpolation.
• $\int_{x_0}^{x_1} f(x) dx \approx \int_{x_0}^{x_1} P(x) dx$.
• $P(x) = f(x_0) + \frac{x - x_0}{x_1 - x_0} [f(x_1) - f(x_0)]$.
• This simplifies to $\int_{x_0}^{x_1} f(x) dx \approx \frac{h}{2} [f(x_0) + f(x_1)]$, where $h = x_1 - x_0$.

Simpson's Rule

• Uses quadratic interpolation.
• $\int_{x_0}^{x_2} f(x) dx \approx \int_{x_0}^{x_2} P(x) dx$.
• $P(x) = f(x_0) + \frac{x - x_0}{x_1 - x_0} [f(x_1) - f(x_0)] + \frac{(x - x_0)(x - x_1)}{(x_2 - x_0)(x_2 - x_1)} [f(x_0) - 2f(x_1) + f(x_2)]$.
• It is approximated as $\int_{x_0}^{x_2} f(x) dx \approx \frac{h}{3} [f(x_0) + 4f(x_1) + f(x_2)]$, where $h = x_1 - x_0 = x_2 - x_1$.

Error Analysis

• Error analysis involves understanding the error introduced by approximation.

Taylor Expansion

• $f(x)$ is expanded about the midpoint $x_m = (x_0 + x_1) / 2$.
• Expansion: $f(x) = f(x_m) + f'(x_m)(x - x_m) + \frac{f''(\x_m)}{2!} (x - x_m)^2 + \frac{f'''(\x_m)}{3!} (x - x_m)^3 +...$.
• Integration from $x_0$ to $x_1$ yields terms involving derivatives of $f(x)$.
• It simplifies to $\int_{x_0}^{x_1} f(x) dx = f(x_m) h + \frac{f''(x_m)}{24} h^3 + \frac{f''''(x_m)}{1920} h^5 +...$, where $h = x_1 - x_0$.

Trapezoidal Rule Error

• $\int_{x_0}^{x_1} f(x) dx - \frac{h}{2} [f(x_0) + f(x_1)] = -f''(x_m) \frac{h^3}{12} + f''''(x_m) \frac{h^5}{480} +...$.
• The error is $\int_{x_0}^{x_1} f(x) dx = \frac{h}{2} [f(x_0) + f(x_1)] -f''(\xi) \frac{h^3}{12}$, where $x_0 < \xi < x_1$.

Simpson's Rule Error

• Error Term: $\int_{x_0}^{x_2} f(x) dx = \frac{h}{3} [f(x_0) + 4f(x_1) + f(x_2)] -f''''(\xi) \frac{h^5}{90}, x_0 < \xi < x_2$.

Composite Rules

• $[a, b]$ is divided into $n$ subintervals of equal length $h = (b-a) / n$.

Composite Trapezoidal Rule

• The integral is $\int_a^b f(x) dx = \frac{h}{2} [f(a) + 2 \sum_{j = 1}^{n-1} f(a + jh) + f(b)] - \frac{(b - a)}{12} h^2 f''(\xi)$.

Composite Simpson's Rule

• The integral is $\int_a^b f(x) dx = \frac{h}{3} [f(a) + 2 \sum_{j = 1}^{n/2 - 1} f(a + 2jh) + 4 \sum_{j = 1}^{n/2} f(a + (2j - 1)h) + f(b)] - \frac{(b - a)}{180} h^4 f''''( \xi)$.

Gaussian Quadrature

• Points are chosen to optimize accuracy, rather than being equally spaced.
• Approximation: $\int_{-1}^1 f(x) dx \approx \sum_{i = 1}^n w_i f(x_i)$.
• $2n$ parameters are weights ($w_i$) and points ($x_i$). Choose them to integrate a polynomial of degree $2n-1$ exactly.

Gaussian Quadrature Example: $n = 2$

• Approximation: $\int_{-1}^1 f(x) dx \approx w_1 f(x_1) + w_2 f(x_2)$.
• Four parameters: $w_1, w_2, x_1, x_2$.
• Solution: $w_1 = w_2 = 1, x_1 = -\frac{1}{\sqrt{3}}, x_2 = \frac{1}{\sqrt{3}}$.
• Integral evaluation: $\int_{-1}^1 f(x) dx \approx f(-\frac{1}{\sqrt{3}}) + f(\frac{1}{\sqrt{3}})$.

Gaussian Quadrature General Interval

• Perform a change of variable for use on $[a, b]$: $x = \frac{b - a}{2} t + \frac{a + b}{2}$.
• Approximation: $\int_a^b f(x) dx = \frac{b - a}{2} \int_{-1}^1 f(\frac{b - a}{2} t + \frac{a + b}{2}) dt \approx \frac{b - a}{2} \sum_{i = 1}^n w_i f(\frac{b - a}{2} t_i + \frac{a + b}{2})$.

Gaussian Quadrature Points and Weights

• Table provides points and weights for different n values.

Gaussian Quadrature Error

• Error term: $\int_a^b f(x) dx = \sum_{i = 1}^n w_i f(x_i) + \frac{f^{(2n)}(\xi)}{(2n)!} \int_a^b \prod_{i = 1}^n (x - x_i)^2 dx$.

Quantum Mechanics Intro: Failures of Classical Physics

• Classical physics couldn't explain: black body radiation, photoelectric effect, and atom stability.

Blackbody Radiation

• Blackbody absorbs all EM radiation.
• Classically, energy radiated should increase infinitely with frequency (ultraviolet catastrophe), which contradicts experimental results.
• Explained by Planck ($E = hf = \hbar \omega$).

Photoelectric Effect

• Electrons emitted from metal when light shines on it.
• Classical prediction: Kinetic energy increases with light intensity.
• Experimental result: Kinetic energy depends on frequency; threshold frequency exists.
• Explained by Einstein ($E = hf = \phi + KE$).

Atom Stability

• Classical prediction: Orbiting electrons emit radiation and spiral into the nucleus.
• Bohr's Model: Predicted discrete energy levels of hydrogen ($E_n = -13.6 eV/n^2$).

Wave-Particle Duality

• Light and matter exhibit both wave and particle characteristics.

de Broglie Wavelength

• $\lambda = h/p$, where $p$ is momentum.

Heisenberg Uncertainty Principle

• Position and momentum uncertainty: $\Delta x \Delta p \ge \hbar/2$.
• Energy and time uncertainty: $\Delta E \Delta t \ge \hbar/2$.

Schrödinger Equation

• Time-Dependent: $i\hbar \frac{\partial}{\partial t} \Psi(x,t) = \hat{H} \Psi(x,t)$.
• Time-Independent: $\hat{H} \psi(x) = E \psi(x)$.

Probabilistic Interpretation

• Probability in region $a \le x \le b$ is $P(a \le x \le b) = \int_a^b |\Psi(x,t)|^2 dx$.
• Normalization: $\int_{-\infty}^{\infty} |\Psi(x,t)|^2 dx = 1$.

Expectation Values

• Expectation value of operator $\hat{A}$: $\langle A \rangle = \int_{-\infty}^{\infty} \Psi^*(x,t) \hat{A} \Psi(x,t) dx$.

Organizational Regulations for Small/Medium Enterprises

• Document outlines organization and operation of the Office of the Spokesperson for Small and Medium-Sized Enterprises.

General Provisions

• This document defines organization and functioning rules.
• Definitions: "Rzecznik" means Spokesperson, "Zastępca Rzecznika" means Deputy Spokesperson, "Dyrektor Generalny" means Director General of the Office.
• Spokesperson directs the office with help from Deputy and Director General.
• Spokesperson can assign tasks.

Organizational Structure

• Teams: Communication/External Relations, Analysis/Strategy, Legal, Intervention, Internal Services.
• Teams are led by managers hired/fired by the Director General.
• Organizational chart is attached to the regulations.

Scope of Operations

• Communication and External Relations Team: plans communications, media, website, social media, promotion of entrepreneur rights through NGOs, and event organization.
• Analysis and Strategy Team: Monitors legal/economic environment, creates reports, prepares legislation, and cooperates with research institutions.
• Legal Team: Reviews laws, prepares legal opinions, represents Spokesperson in court, and advises entrepreneurs.
• Intervention Team: Handles complaints, investigates rights violations, appeals to authorities, and mediates disputes.
• Internal Service Team: Provides admin support, HR, finance, IT, and manages archives.

Rules for Signing Documents

• Spokesperson signs important documents.
• Deputy signs as assigned by Spokesperson.
• Director General signs on office operations.
• Team managers sign for their team issues.
• Spokesperson can authorize other employees to sign.

Final Provisions

• Amendments follow the same process as initial regulation.
• Regulations take effect on signing date.

Hidden Markov Models (HMMs) vs. Recurrent Neural Networks (RNNs) for Online Handwriting Recognition

Summary

• Compares HMMs and RNNs for online handwriting recognition.
• RNNs outperform HMMs in recognition accuracy but HMMs are more interpretable and easier to train.

Introduction

• Online handwriting recognition converts handwriting to digital text.
• HMMs and RNNs are popular approaches.

Hidden Markov Models (HMMs)

• Probabilistic models represent handwriting as a sequence of hidden states.
• Hidden states represent writing units (letters/strokes).
• Observations are ink point coordinates.
• HMM parameters: N (states), M (observation symbols), A (transition matrix), B (emission matrix), π (initial state vector).
• Viterbi algorithm finds the most probable hidden state sequence.
• Baum-Welch algorithm estimates HMM parameters from training data.

Recurrent Neural Networks (RNNs)

• Neural networks that learn temporal relationships in data.
• RNNs consist of recurrent cells that receive input and hidden state from previous cells.
• Each cell generates an output and new hidden state (the memory).
• RNNs can be trained with backpropagation through time.

Experimental Results

• Evaluated HMMs and RNNs using the IAM online handwriting dataset.
• RNNs outperformed HMMs in recognition accuracy.
• RNNs achieved a 10.2% word error rate (WER), while HMMs achieved 15.4%.

Conclusion

• RNNs are more accurate, but HMMs are more interpretable and easier to train.
• HMMs suit applications where interpretability is crucial.
• RNNs are better where accuracy is paramount.

Table 1: HMM vs. RNN

Includes a table summarizing HMM vs RNN.

• Accuracy: HMM Lower, RNN Higher.
• Interpretability: HMM Superior, RNN Lower.
• Training: HMM Easier, RNN More Difficult.
• Complexity: HMM Less Complex, RNN More Complex.