- [Science](/nodes/Science)
- [Applied Science](/nodes/Applied_Science)
- [Business](/nodes/Business)

-Knowledge

A generalization of biparte maching to 3-partite hypergraphs. 

3-Dimensional Matching

Non-linear functions are used to model non-linear data. 
## Common Functions
 - [Rectified Linear Unit (ReLU)](/nodes/Rectified_Linear_Unit_(ReLU))
 - [Sigmoid](/nodes/Sigmoid)

Activation Function

## Choosing the Correct Algorithm
If you have a simple, local criterion to make a choice that leads to an optimal solution, use [Greedy Algorithm](/nodes/Greedy_Algorithm)
If you don't and subproblems overlap, use [Dynamic Programming](/nodes/Dynamic_Programming)
If subproblems don't overlap, use [Divide and Conquer](/nodes/Divide_and_Conquer)

Algorithm

## Client-Server Paradigm
### Server
- always-on host
- permanent IP address
- in data centers for scaling
### Clients
- may be intermittently connected
- may have dynamic IP address
- do not directly communicate with each other
## P2P Architecture
Peers request service from other peers, provide service in return to other peers. Peers intermittently connected and change IP addresses. 
## Processes
Client process initiates communication, server process waits to be contacted. Processes exchange messages. Within same host, two process communicate with inter-process communication (defined by OS). 
## Sockets
Processes send/receives messages to/from socket between application/session and transport layer. 
## App-layer Protocol Defines
- types of messages exchanged (e.g. request, response)
- message syntax and semantics (what fields, how delineated, mean of info in fields)
- rules for when/how processes send & respond to messages
- open protocols defined in RFCs, allowing for interoperability (e.g. HTTP, SMTP), as well as proprietary protocols (e.g. Skype)
## Topics
- [HTTP](/nodes/HTTP)
## Use Cases
- [Email](/nodes/Email)
- [Domain Name System (DNS)](/nodes/Domain_Name_System_(DNS))
- [Peer-to-Peer (P2P)](/nodes/Peer-to-Peer_(P2P))

Application Layer

An application-specific integrated circuit is an integrated circuit chip customized for a particular use, rather than intended for general-purpose use. 
## Examples
[Graphics Processing Unit (GPU)](/nodes/Graphics_Processing_Unit_(GPU))
[Tensor Processing Unit (TPU)](/nodes/Tensor_Processing_Unit_(TPU))

Application-Specific Integrated Circuit (ASIC)

## Data
Given a table of data with headers on the top, each row is an example/sample, and each column is a feature. More info at [Data](/nodes/Data). 
### Types
Categorical features, numerical features
### Cleaning
To remove noise, outliers, missing values, duplicate data
### Features
#### Aggregation
combine features (e.g. combine city data points into provinces), which reduces [Time Complexity](/nodes/Time_Complexity)/[Space Complexity](/nodes/Space_Complexity) but results in loss of data
#### Transformation
##### Discretization (Binning)
Turn numerical data into categorical (e.g. age groups)
#### Selection
Remove features not relevant to task
## Summary Statistics
More info at [Summary Statistics](/nodes/Summary_Statistics)
## Data Visualization
More info at [Data Visualization](/nodes/Data_Visualization). 
## Entropy
entropy $= -\sum_{c=1}^kp_c\log p_c$, where $p_c$ is the proportion of times you have value 'c'


Applications of Statistics in ML

- [Engineering](/nodes/Engineering)
- [Computation](/nodes/Computation)
- [Machine](/nodes/Machine)

Applied Science

Arithmetic

Arm Cortex A9

Perceiving, synthesizing, and inferring information - demonstrated by machines, as opposed to intelligence displayed by biological entities. 
Doing so without explicit instructions leads to [Machine Learning](/nodes/Machine_Learning)
## Problems
[Computer Vision](/nodes/Computer_Vision)
## Tools
[Decision Trees](/nodes/Decision_Trees)

Artificial Intelligence

Develops and implements  information and technology providing electrical, electronic, mechanical and computer-based all industrial systems to work intended and planned manner. 
[Microcomputer](/nodes/Microcomputer)s commonly interface with mechanical systems. 

Automation and Control

1. Construct a visual dictionary using [Visual Words](/nodes/Visual_Words) and [K-Means Clustering](/nodes/K-Means_Clustering)
2. Compute a histogram of the visual words for each image
3. Classify the visual word histograms with [Support Vector Machines (SVM)](/nodes/Support_Vector_Machines_(SVM))

## The Algorithm
1. Initialize an empty K-bin histogram, where K is the number of codewords
2. Extract local descriptors (e.g. SIFT) from the image
3. For each local descriptor $x$
	1. Map (Quantize) $x$ to its closest codeword -> $c(x)$
	2. Increment the histogram bin for $c(x)$
4. Return histogram
The histogram can then be classified using a trained classifier (e.g SVM or k-Nearnest Neighbour). 

Bag-of-Words

Random sampling with replacement. 
A parallel [Ensemble Methods](/nodes/Ensemble_Methods). 
Reduces variance. 

Bagging

Bayes' Theorem

A probalistic view of classificaiton that mdoels the likelihood of observing the data given a class/parameters. E.g. might assume distribution is gaussian. 
![Pasted image 20221210134120.png](/nodes/Pasted_image_20221210134120.png)
This idea can be extended to use [Gaussian Classifier](/nodes/Gaussian_Classifier). 

Bayesian Classification

## Related
- [Bayesian Classification](/nodes/Bayesian_Classification)
- [Bayes' Theorem](/nodes/Bayes'_Theorem)
- [Naive Bayes](/nodes/Naive_Bayes)

Bayesian Methods

Cluster the training examples and features to give feature relationship information

Biclustering

$p \iff q$ meaning "p if and only if q"
$p \iff q \equiv p \implies q \land q \implies p$ 

Biconditional

Based on the principle of [Boosting](/nodes/Boosting)
## Simple Features
Quite a few simple features that are computationally fast. For example, we have [Boxlet Features](/nodes/Boxlet_Features). 
## Viola Jones Face Detection
Initial stages have a high true positive rate, with high false positive rate, to reject non-faces quickly. Later stages use more processing to reduce false positives. 
To efficiently compute boxlet features, we can use an [Integral Image](/nodes/Integral_Image)s, to compute in $O(1)$ time. 

Boosting Forests

Base models are trained sequentially, and then combined  through majority voting or averaging. In boosting, we perform  “weighted” resampling, so observations that were misclassified by the  previously trained base model have a greater chance of being sampled. 
A sequential [Ensemble Methods](/nodes/Ensemble_Methods). 
Reduces both bias and variance. 

Boosting

## Types
- 2-rectangle: difference between equally sized regions
- 3-rectangle: difference between extremes and center region
- 4-rectangle: difference between diagonal pairs of rectangles
![Pasted image 20221211171224.png](/nodes/Pasted_image_20221211171224.png)
From this, we can build a simple classifier to takes a Harr Wavelet filter (top-left-most in above image) to see if response > 0.6, we have face, no face otherwise. 
## Boosting
Building a complex classifier using weighted combination of simple classifiers. 
How do we learn the parameters in $H(x)=\Sigma_j \alpha_j h_j (x)$? We can use [Boosting Forests](/nodes/Boosting_Forests)
- Randomly select a feature at a time
- Find the parameters for this feature that maximise classification performance using exponential loss, $J(\theta)=\sum_ke^{-y_kH(x_k)}$, with $\hat y_k=\text{sign}(H(x_k))$
- Mis-classified examples are weighted more strongly at each stage of classifier learning (the "boosting")

Boxlet Features

The Brave Sensor alerts you when someone stops moving or has been in a washroom or other isolated space long enough to cause concern.
Developed by [Brave Technology Coop](/nodes/Brave_Technology_Coop)
## Components
 - [Particle Boron](/nodes/Particle_Boron)
 - [Radar](/nodes/Radar)
 - [Door Sensor](/nodes/Door_Sensor)

Brave Sensor

Regression models that use the L-infinity norm as a measure of error or loss are sometimes also referred to as Chebyshev regression or maximum norm regression. Chebyshev regression can be useful in cases where the data contains outliers or extreme values that may have a disproportionate impact on the results of other types of regression models.
## Smoothing
[L-Infinity Norm](/nodes/L-Infinity_Norm) is convex but non-smooth, so we can use smooth approximate and fit it with gradient descent. The convex and smooth approximate to max function is [Log-Sum-Exp Function](/nodes/Log-Sum-Exp_Function), as $\max_i\{z_i\}\approx \log(\sum_i \exp(z_i))$. 

Brittle Regression

- [Financial Accounting](/nodes/Financial_Accounting)

Business

[Derivatives](/nodes/Derivatives)
[Integrals](/nodes/Integrals)


Calculus

## Demosaicing

Cameras use RGB channels, which when checkered, results in an uneven balance of the three colours, and there being unknown areas for a specific channel as there is a different channel sensor there.

Therefore bilinear interpolation is used, using the four neighbours. The more densely sampled green channel is often used for the edge detection.

## White Balancing

Humans good at adapting to global illumination conditions (e.g. white object looks white whether under blue sky or candle light. However, if the pictured is viewed later (e.g. on a monitor) the viewer no longer corrects for the environment and the illuminant colour appears too strong.

An example algorithm would be “greyworld”, which assumes the average pixel in an image is grey.

This is related to [Colour](/nodes/Colour)

## Gamma Correction

Equal steps in luminance $\ne$ perceived brightness (the brightness we see is not linear with the number of photons). Can be corrected with $L=V^\gamma$, where $L$ is the raw luminance, $V$ is gamma corrected encoding (which allocates more bits to smaller values), and $\gamma$ is the correction constant, usually $2.2$.

## Contrast Sensitivity

Human visual system is most sensitive to mid-frequencies. High amplitude high frequency, and high amplitude low frequency data can be discarded. Discrete cosine transform and coefficient quantisation can be used to improve algorithm efficiency and compression.

Cameras

The electronic circuitry that executes instructions comprising a computer program.
## Examples
 - [Nios II](/nodes/Nios_II)
 - [Arm Cortex A9](/nodes/Arm_Cortex_A9)

Central Processing Unit (CPU)

## Short Answers
Big punish for selecting incorrect options
Average-case for random algorithm is not dependent on input
Average-case for deterministic algorithm is dependent on input
## Prereqs
### Log Rules
$\log_a b^c = c \log_a b$; $\log_a b + \log_b c = \log_a c$ ; $\log_a b \cdot \log_b c = \log_a c$; $\frac{\log_a b}{\log_b c} = \log_c a$; $\log_a b^{-1} = - \log_a b$
### Exponential Rules
$a^{b + c} = a^b \cdot a^c$; ; $a^{b - c} = \frac{a^b}{a^c}$; $(a^b)^c = a^{b \cdot c}$; $a^{b \cdot c} = (a^b)^c$; $a^{b/c} = \sqrt[c]{a^b}$
### Geometric Series
- The formula for the sum of a finite geometric series with first term `a` and common ratio `r` is: $\sum_{i=0}^{n-1} ar^i = \frac{a(1-r^n)}{1-r}$
- The formula for the sum of an infinite geometric series with first term `a` and common ratio `r` is: $\sum_{i=0}^{\infty} ar^i = \frac{a}{1-r}$
If $|r| \ge 1$, then summation goes to infinity
### Probability
$nCr=\frac{n!}{r!(n-r)!}$     $nPr=\frac{n!}{(n-r)!}$
### Asympotic Growth Rates
$\mathcal{O}(1)$,  $\mathcal{O}(\log n)$,  $\mathcal{O}(n)$, $\mathcal{O}(n \log n)$,  $\mathcal{O}(n^2)$, $\mathcal{O}(n^3)$, $\mathcal{O}(2^n)$, $\mathcal{O}(n!)$
Let $n$, $m$ be num verticies and edges, then for $f(n)=n^2+2^{2+log_2n}$, we have $f(n)\in O(m^2)$ and $f(n)\in\Theta(n^2)$, as there is ratio between $n$ and $m$. 
## Gale-Shapely (SMP)
```
set all s ∈ S and e ∈ E to free
	while some free employer e hasn’t made an offer to every stude nt do 
		s ← the highest-ranking student e hasn’t made an offer to 
		if s is free then 
			hire(e, s) 
		else 
			e′ ← s’s current employer 
			if s prefers e to e′ then 
				set e′ to free hire(e, s) 
			endif 
		endif 
	endwhile 
return the set of pairs
```
Standard examples/counterexamples: 
- $e_1: [a_1, a_2], e_2: [a_2, a_1], a1: [e_2, e_1], a2: [e_1, e_2]$
- e1: a2 a1 a3, e2: a3 a2 a1, e3: a1 a3 a2, a1: e2 e1 e3, a2: e3 e2 e1, a3: e1 e3 e2
## Master Theorem
Let $a \ge 1, b \ge 1$ be real constants, let $f: N \rightarrow R^+$, and let $T(n)$ be defined by: 
$$T(n)=
\begin{cases}
aT(n/b)=f(n) \text{ if } n \ge n_0 \\
\Theta(1) \text{ if } n < n_0
\end{cases}$$
where $n/b$ might be either $\lfloor n / b \rfloor$ or $\lceil n / b \rceil$. Then
1. If $f(n) \in \mathcal{O}(n^{\log_ba-\epsilon})$ for some $\epsilon > 0$ then $T(n) \in \Theta(n^{\log_ba})$. 
2. If $f(n)\in\Theta(n^{\log_ba}\log^kn)$ for some $k \ge 0$ then $T(n) \in \Theta (n^{\log_ba}\log^{k+1}n)$. 
3. If $f(n)\in\Omega(n^{\log_ba+\epsilon})$ for some $\epsilon > 0$ and $af(n/b)<\delta f(n)$ for some $0<\delta<1$ (regularity condition) and all $n$ large enough, then $T(n)\in \Theta(f(n))$. 

Less formally: 
1. $\log_ba>$ exponent of $n$ in $f(n)$
2. $\log_ba =$ exponent of $n$ in $f(n)$, without considering $\log$ or exponential components
3. $\log_ba<$ exponent of $n$ in $f(n)$, check regularity condition
## Standard Problems for Reduction
### Packing Problems
[Independent Set](/nodes/Independent_Set): Given a graph G and a number k, does G contain an independent set of size at least k?
[Set Packing](/nodes/Set_Packing): Given a set U of n elements, a collection S1,..., Sm of subsets of U, and a number k, does there exist a collection of at least k of these sets with the property that no two of them intersect?
### Covering Problems
[Vertex Cover](/nodes/Vertex_Cover): Given a graph G and a number k, does G contain a vertex cover of size at most k?
[Set Cover](/nodes/Set_Cover): Given a set U of n elements, a collection S1,..., Sm of subsets of U, and a number k, does there exist a collection of at most k of these sets whose union is equal to all of U?
### Partitioning Problems
[3-Dimensional Matching](/nodes/3-Dimensional_Matching): 3-Dimensional Matching: Given disjoint sets X, Y, and Z, each of size n, and given a set T ⊆ X × Y × Z of ordered triples, does there exist a set of n triples in T so that each element of X ∪ Y ∪ Z is contained in exactly one of these triples?
[Graph Colouring](/nodes/Graph_Colouring): Given a graph G and a bound k, does G have a k-coloring?
### Sequencing Problems    
[Hamiltonian Cycle](/nodes/Hamiltonian_Cycle): Given a directed graph G, does it contain a path that visits each vertex exactly once? With restrictions on ordering. 
[Hamiltonian Path](/nodes/Hamiltonian_Path): Given a directed graph G, does it contain a cycle that visits each vertex exactly once?
[Traveling Salesman](/nodes/Traveling_Salesman): Given a set of distances on n cities, and a bound D, is there a tour of length at most D?
### Numerical Problems
[Subset Sum](/nodes/Subset_Sum): Given natural numbers w1,..., wn, and a target number W, is there a subset of {w1,..., wn} that adds up to precisely W?
### Constraint Satisfaction Problems
[3-SAT](/nodes/3-SAT): Given a set of clauses C1,..., Ck, each of length 3, over a set of variables X = {x1,..., xn}, does there exist a satisfying truth assignment?
### Others
[Steiner Tree](/nodes/Steiner_Tree): finding the shortest possible tree that connects a given set of points (called terminals) in a network. The tree is allowed to include additional points (called Steiner points) that are not part of the original set of terminals.
## Greedy Proofs
### Stays Ahead (By induction)
Used when there is a “local optimality” property which can be checked. If one measures the greedy algorithm’s progress in a step-by-step fashion, one sees that it does better than any other algorithm at each step; it then follows that it produces an optimal solution.
    1. **Define Your Solution.** Your algorithm will produce some object $X$ and you will probably compare it against some optimal solution $X^*$. Introduce some variables denoting your algorithm's solution and the optimal solution.
    2. **Define Your Measure.** Your goal is to find a series of measurements you can make of your solution and the optimal solution. Define some series of measures $m₁(X), m₂(X), …,mₙ(X)$ such that $m₁(X^*), m₂(X^*), …, mₖ(X^*)$ is also defined for some choices of $m$ and $n$. Note that there might be a different number of measures for $X$ and $X^*$, since you can't assume at this point that $X$ is optimal.
    3. **Prove Greedy Stays Ahead.** Prove that $m_i(X) ≥ m_i(X^*)$ or that $m_i(X) ≤ m_i(X^*)$, whichever is appropriate, for all reasonable values of $i$. This argument is usually done inductively.
    4. **Prove Optimality.** Using the fact that greedy stays ahead, prove that the greedy algorithm must produce an optimal solution. This argument is often done by contradiction by assuming the greedy solution isn't optimal and using the fact that greedy stays ahead to derive a *contradiction*.
### Exchange Argument
Pick an arbitrary solution $S$ (not the same as our greedy solution $S_G$), we construct a set $S'$ which has 2 properties:
    1. $S'$ must be more similar to $S_G$ than $S$, for some definition of “more similar”. For instance, depending on the problem, more similar might mean $S'$ has more edges in common with $S_G$ than $S$, or $S'$ might have a longer initial sequence whose elements are the same as those of $S_G$ than $S$.
    2. $S'$ must be “at least as good” as $S$ with respect to the quantity we are trying to optimize.
## SAT
For each integer $a$ from $1$ to $k$, add the clause $X_{a_1}\lor X_{2,a}\lor ... X_{n,a}$ so that at least one vertex is in each position of the clique. 
For each pair of verticies $v_p$ and $v_q$ and for every $a$ in $1$ to $k$, add the clause: $\neg X_{p,a}\lor\neg X_{q,a}$ so that no more than one vertex is in each position of the clique. 
For each vertex $v_p$ and for every two distinct integers $a,b$ from $1$ to $k$, add the clause: $\neg X_{p_a} \lor \neg X_{p_b}$ so that no vertex can be in more than one position in the clique. 
For all pairs of verticies $v_p$ and $v_q$ that do not share an edge, for every $a$ and every $b$ between $1$ and $k$, add the clauses: $\neg X_{p,a} \lor \neg X_{q,b}$, so that the clique consists only of connected verticies. 

## Graphs
Split Graph: Partitioning graphs into 2 sets $V_1,V_2$, where $V_1$ is fully connected and $V_2$ is fully disconnected.
![Pasted image 20221213015942.png](/nodes/Pasted_image_20221213015942.png)
Bipartite Graph (Bigraph): A set of graph vertices decomposed into 2 disjoint sets s.t. no two graph vertices within the same set are adjacent.
![Pasted image 20221213015952.png](/nodes/Pasted_image_20221213015952.png)
Independent Set: Subset of vertices $S$ s.t. no two vertices in $S$ are adjacent/connected. 
![Pasted image 20221213020103.png](/nodes/Pasted_image_20221213020103.png)
Clique: Subset of vertices s.t. every two distinct vertices are adjacent (i.e. Largest fully connected subgraph). 
![Pasted image 20221213020110.png](/nodes/Pasted_image_20221213020110.png)
Vertex Cover: A subset of vertices that are atleast one endpoint of all edges in the graph. 
![Pasted image 20221213020117.png](/nodes/Pasted_image_20221213020117.png)
## Dynamic Programming
Does use a recurrence relation; not more efficient that optimal greedy solution
## Amortized Cost (Potential Method)
Potential: $\Phi(D_i)$ is the state of the algorithm after $i$ operations. i.e. How much you can spend on the next expensive operations (comparing it to a bank balance), where $\Phi(D_i)\ge0$ and $\Phi(D_i)=0$
Amortized Cost: $cost_{am}(op_i)=cost_{real}(op_i)+\Phi(D_i)-\Phi(D_{i-1})$
-   $op_i$ is the cost to perform $i$th operation.
-   $cost_{am}(op_i)$ should be relatively consistent (the amount you’re actually paying)
By definition $\sum_{i=1}^ncost_{real}(op_i)\le\sum_{i=1}^ncost_{am}(op_i)$
### Hashtable Example with **Insert**
With potential of $\Phi(H)=5\times$num operations since last reallocation, two cases: 
1. No reallocation, so real cost is 1, so $1+\Phi(D_i)-\Phi(D_{i-1})=6$
2. After previous reallocation, array is `60%` full, to reach `90%` full, need at least `30%s` insert operations, where `s` is size of array before reallocation. The real cost is $1.5s$, and $\Phi(D_i)-\Phi(D_{i-1})=0-5*0.3s=-1.5s$, hence amortized cost is $0$. 

Cheat Sheet

End-to-end resources allocated to , reserved for "call" between source and destination. No packets are used, but rather there is a dedicated connection, called a circuit. 
Uses [Frequency Division Multiplexing (FDM)](/nodes/Frequency_Division_Multiplexing_(FDM)) or [Time Division Multiplexing (TDM)](/nodes/Time_Division_Multiplexing_(TDM)) to handle multiple circuits. 

Circuit Switching

Classification in machine learning refers to the process of training a model to predict the category or class to which a given input data point belongs, based on a set of labeled examples. The goal is to create an accurate and generalizable model that can correctly classify new, unseen data points. 
## Techniques
- [Decision Trees](/nodes/Decision_Trees)
- [Random Forests](/nodes/Random_Forests)
- [Support Vector Machines (SVM)](/nodes/Support_Vector_Machines_(SVM))
- [Naive Bayes](/nodes/Naive_Bayes)
- [k-Nearest Neighbours (kNN)](/nodes/k-Nearest_Neighbours_(kNN))
- [Neural Network](/nodes/Neural_Network)

Classification

Clustering is a machine learning technique used to group similar data points together based on their inherent similarities. It involves identifying patterns and similarities within datasets to aid in tasks such as data analysis, classification, and recommendation systems.
## Types
- [K-Means Clustering](/nodes/K-Means_Clustering)
- [Hierarchical Clustering](/nodes/Hierarchical_Clustering)
- [Density-based Clustering (DBSCAN)](/nodes/Density-based_Clustering_(DBSCAN)): for [Non-Convex](/nodes/Non-Convex) data set
## Other Types
- [Ensemble Clustering](/nodes/Ensemble_Clustering)
- [Biclustering](/nodes/Biclustering)
## Agglomerative Clustering: 
Each data point starts as a separate cluster. Clusters are recursively merged.
1. Make each point a separate cluster
2. Until the clustering is satisfactory, merge the two clusters with the smallest inter-cluster distance
## Divisive Clustering
The entire data set starts as a single cluster. Clusters are recursively split. 
1. Construct a single cluster containing all points
2. Until the clustering is satisfactory: 
	1. Split the cluster that yields the two components with th elargest inter-cluster distance
## Inter-Cluster Distance
### Single-link Clustering
The distance between the closest members in seperate sets
### Complte-Link Clustering
The distance between the farthest members in seperate sets
### Group Average Clustering
An average of distances between members of the two sets
## [Dendrogram](/nodes/Dendrogram)
A visual representation of what the algorithm does, similar to a tree but notes the time in which the node divides. 
![Pasted image 20221211173039.png](/nodes/Pasted_image_20221211173039.png)

Clustering

Spectral power distribution. 
Spectral albedo of natural surfaces. 
Addictive and Subtractive Colour (RGB vs CMYK). 
	i.e. when all the colours are combined, does it make white or black?
Human rod (~100 million, grey-scale vision, sensitive, poor spatial detail) vs human cone (~6 million, colour vision, in high light, less sensitive, higher resolution). 
## Metamers
Different spectral power distributions can give the same tristimulus values (e.g. perceived sunlight can be mimicked with matching light from tv, even though they have different spectral power distributions), as humans do not ‘see’ the spectral power distribution, but rather the cone response curves.
## Colour Matching
Three primaries work for most, provided allow subtractive matching. 
	some can match with two or only one primary
		most likely caused by biological differences
Most people make same matches. 
Negative matching is also possible. 
Some colours can’t be matched with only positive colours, so we write
	$M+aA=bB+cC$, interpreting as $(-a,b,c)$, for subtractive matching
Basically, when there’s a real life light source of some specific spectral power distribution, the computer must find rgb values that allows the spectral power distribution of the rgb LEDs to be perceived the same by human eyes. 
## Colour Spaces
RGB
CIE XYZ: primaries are imaginary, coordinates correspond to amount of each primary
CIE LAB (Uniform Colour Space): equal distances in space correspond to perceptually uniform colour differences (for humans)
HSV: hue saturation, value
YCbCr: separates luminance (Y) with opponent colours (CbCr)
	A linear transformation of RGB

Colour

A combination of a [Real Number](/nodes/Real_Number) and a[Imaginary Number](/nodes/Imaginary_Number), represented as $a+bi$, where $i=\sqrt{-1}$. 

Complex Number

Put a penalty on the model complexity. E.g. we minimize the training error plus the degree of polynomial. 
## Information Criteria
Scores are usually in the form $\text{score}(p)=\frac 12 || Z_pv-y||^2+\lambda K$. The value of $k$ is the number of estimated parameters/degrees of freedom, e.g. for polynomial basis, we have $k=(p+1)$. The parameter $\lambda > 0$ controls how strong we penalize complexity. A $\lambda=1$ is called the Akaike information criterion (AIC). 

Complexity Penalties

Any type of [Arithmetic](/nodes/Arithmetic)) or non-arithmetic calculation that follows a well-defined model (e.g., an [Algorithm](/nodes/Algorithm)). 
Generally performed on [Computer](/nodes/Computer)s. 

Computation

Classifying computational problems according to their resource usage, and relating thsese classes to each other. 
[Space Complexity](/nodes/Space_Complexity)
[Time Complexity](/nodes/Time_Complexity)
## Categories
[NP-Complete](/nodes/NP-Complete)

Computational Complexity

 - [Software](/nodes/Software), which focuses on using [Data Structure](/nodes/Data_Structure)s and [Algorithm](/nodes/Algorithm)s to solve problems
 - [Computer Hardware](/nodes/Computer_Hardware), which uses [Electrical Engineering](/nodes/Electrical_Engineering) and [Computation](/nodes/Computation) to solve problems. 

Computer Engineering

## Examples
- [Digital Circuit](/nodes/Digital_Circuit)
- [Synchronous Dynamic Random Access Memory (SDRAM)](/nodes/Synchronous_Dynamic_Random_Access_Memory_(SDRAM))
- [Central Processing Unit (CPU)](/nodes/Central_Processing_Unit_(CPU))
- [Microcomputer](/nodes/Microcomputer)
- [Tensor Processing Unit (TPU)](/nodes/Tensor_Processing_Unit_(TPU))

Computer Hardware

## Topics
- [Network Core](/nodes/Network_Core)
- [Network Edge](/nodes/Network_Edge)
- [Network Performance](/nodes/Network_Performance)
- [Network Layers](/nodes/Network_Layers)
- [Network Security](/nodes/Network_Security)
- [Web Cache (Proxy Server)](/nodes/Web_Cache_(Proxy_Server))
## Layers
- [Application Layer](/nodes/Application_Layer)
- [Transport Layer](/nodes/Transport_Layer)
## Types
 - [Wide Area Network (WAN)](/nodes/Wide_Area_Network_(WAN))
 ## Protocols
 [HTTP](/nodes/HTTP), [TCP](/nodes/TCP), [IP](/nodes/IP), [WiFi](/nodes/WiFi), [Ethernet](/nodes/Ethernet), etc.
 

Computer Networking

## Core Topics
- [Data Structure](/nodes/Data_Structure)
- [Algorithm](/nodes/Algorithm)
- [Computational Complexity](/nodes/Computational_Complexity)
- [Derivatives of Code](/nodes/Derivatives_of_Code)
- [Machine Learning](/nodes/Machine_Learning)
## Foundational Topics
[Math Proof](/nodes/Math_Proof)
[Set Theory](/nodes/Set_Theory)
## Hardware
[Computer](/nodes/Computer)
## Summary of DS/A II
[Cheat Sheet](/nodes/Cheat_Sheet)

Computer Science

Allows computers to get a high-level understand from digital images or videos. 
## Image Processing and Feature Detection
- [Image Formation](/nodes/Image_Formation)
- [Image Filtering](/nodes/Image_Filtering)
- [Sampling](/nodes/Sampling)
- [Edge Detection](/nodes/Edge_Detection)
- [Corner Detection](/nodes/Corner_Detection)
- [Colour](/nodes/Colour)
- [Texture](/nodes/Texture)
- [Local Image Features](/nodes/Local_Image_Features)
- [Pixel Labelling](/nodes/Pixel_Labelling)
- [Scaled Representations](/nodes/Scaled_Representations)
- [Template Matching](/nodes/Template_Matching)
## Camera and Image Transformations
- [Cameras](/nodes/Cameras)
- [Planar Transformations](/nodes/Planar_Transformations)
- [Hough Transform](/nodes/Hough_Transform)
- [Stereo](/nodes/Stereo)
- [Optical Flow](/nodes/Optical_Flow)
- [Multiview Reconstruction](/nodes/Multiview_Reconstruction)
## Machine Learning in Computer Vision
- [Visual Classification](/nodes/Visual_Classification)
- [Neural Network](/nodes/Neural_Network)
- [Deep Learning](/nodes/Deep_Learning)
- [Boosting Forests](/nodes/Boosting_Forests)
- [Decision Trees](/nodes/Decision_Trees)
- [Clustering](/nodes/Clustering)

Computer Vision

an electronic device for storing and processing data, typically in binary form, according to instructions given to it in a variable program. 
The hardware foundation of [Computer Science](/nodes/Computer_Science). 
Comprised of [Computer Hardware](/nodes/Computer_Hardware)
## Software Components
 - [Operating System](/nodes/Operating_System)
## Problems
 - [Computer Vision](/nodes/Computer_Vision)
 - [Internet of Things](/nodes/Internet_of_Things)
 - [Computer Networking](/nodes/Computer_Networking)

Computer

$\neg q \implies \neg q \equiv p \implies q$, used for simplifing proofs. 

Contrapostive

If $p \implies q$ is the statement, then $q \implies p$ is the converse statement. 

Converse

![Pasted image 20230127141452.png](/nodes/Pasted_image_20230127141452.png)

Convex Set

Is commutative, such that $conv(A,B)=conv(B, A)$
## One dimensional
$(f\times g)(t) \circledast \int_{-\infty}^\infty f(\tau)g(t -\tau)\tau'$ 
has applications in [Signals and Systems](/nodes/Signals_and_Systems)
## Two Dimensional
Uses [Matrix](/nodes/Matrix)es
$I'(X,Y)=\sum_{j=-k}^k\sum_{i=-k}^kF(i,j)I(X-i,Y-j)\\=\sum_{j=-k}^k\sum_{i=-k}^kF(-i,-j)I(X+i,Y+j)$
## Runtime
 [Fourier Transform](/nodes/Fourier_Transform)s can sometimes reduce [Time Complexity](/nodes/Time_Complexity) of convolutions. 

Convolution

Is a [Locally Connected Layer](/nodes/Locally_Connected_Layer) that shares the same parameters accross all the locations (assuming input is stationary). 
For example, a 200x200 image x 40k hidden units with filter size 10x10, will have around $10\times 10=100$ parameters. 
## The Function
Uses [Convolution](/nodes/Convolution)s between the inputs and filters. 
Given an input data of $d\times h\times w$ (depth/channels\\times height\\times width), a filter is selected of size $d\times k\times k$ (where $k$ is odd), where it is always extended to the full depth of the input volume. 
### Single Piece of Data
#### Single Filter
A single output element is $y=w^Tx+b$, which is a $d\times k\times k$-dimensional dot product + bias. 
The $k\times k$ piece of data used as input for this output element is called the [Receptive Field](/nodes/Receptive_Field) of the output. 
The full output is an activation map, of size $1\times (w-k-1)\times (l-k-1)$, accounting for the edge data loss from convolutions.  
This edge data loss is often resolved by [Padding](/nodes/Padding) zeroes around the input. 
#### Multiple Filters
This process is repeated with more filters, such that with $s$ filters, we get a $s\times (w-k-1)\times (l-k-1)$-dimensional output. As such, we also get a $s$-dimension bias vector. 
### Batches of Data
With a $N\times C_{in}\times H\times W$ batch of images and $C_{out}\times C_{in}\times K_w\times K_h$ filters, we output a $N\times C_{out}\times H'\times W'$ batch out outputs, with a $C_{out}$-dim bias vector. 
### Adding Non-Linearity
Multiple stacked [Convolution](/nodes/Convolution)s can be replaced by a single [Convolution](/nodes/Convolution), which results in a linear classifier (which cannot model non-linear data). Therefore [Activation Function](/nodes/Activation_Function)s are used between the convolutions to introduce non-linearity. 
### Computing Learnable Prameters and Work
With $f$ filters, stride 1 and "same" padding, the output volume size is $f\times h \times w$.  The number of learnable parameters is $(d * k * k + 1)*f$ (the $1$ for bias). The number of multiply-add operations is $f*h*w*d*k*k$ (number of outputs \* each output's inner product of two tensors). 
## Sumary
![Pasted image 20221126211627.png](/nodes/Pasted_image_20221126211627.png)

Convolutional Layer

Respects the spatial structure of the data (e.g. images can retain their shape and channels, rather than being stretched to a single column). 
## Techniques
 - [Convolutional Layer](/nodes/Convolutional_Layer)
 - [Pooling Layer](/nodes/Pooling_Layer)
 - [Fully Connected Layer](/nodes/Fully_Connected_Layer)
 - [Activation Function](/nodes/Activation_Function)
 - [Normalization](/nodes/Normalization)

Convolutional Neural Network (CNN)

Image structure:

1.  0D Structure, not useful for matching
2.  1D Structure: edge, can be localized to one direction, difficult to find location along edge
3.  2D Structure: corner, or interest point, can be localized in both directions, good for matching

Sum squared difference between patch and its local neighbourhood with a clear peak suggests that there is a corner.

## Harris Corners

SSD $= \sum _R|I(x) - I(x+ \triangle x)|^2=\triangle x^TH \triangle x$, where $H=\sum_R[I_x^2, I_xI_y],[I_xI_y,I^2_y](/nodes/I_x^2,_I_xI_y],[I_xI_y,I^2_y)$, which is the Harris Or 2nd moment matrix. This simplification is possible with Taylor expansion and using the lemma that $|a|^2=a^Ta$.

SSD function must be large for all shifts $\triangle x$ for a corner / 2D structure. Therefore both eigenvalues of $H$ must be large.

As a review, for Harris corners:

1.  Filter image with Gaussian
2.  Compute the magnitude of the x and y gradients at each pixel
3.  Construct C in a window around each pixel
    1.  Harris uses Gaussian window
4.  Compute the Harris corner strength function $det(C)-\kappa trace^2(C)$
5.  Threshold corner strength function, optionally apply non-maximal suppression

Covariance matrix and gradient vector are used such that for $\triangledown I=(I_x,I_y)$, then $C=\sum_i\triangledown I \triangledown I^T$.

## Difference of Gaussian

DoG = center-surround filter

Find local-maxima of the center surround response in both position and scale

Corner Detection

Correlation

A [Field-programmable Gate-Arrays (FPGA)](/nodes/Field-programmable_Gate-Arrays_(FPGA)) unit with two [Nios II](/nodes/Nios_II) processors, and several peripheral ports: memory, timer modules, audio-in/out, video-in/out, PS/2, analog-to-digital, infrared receive/transmit, and parallel ports connected to switches and lights. 
To generate RTL, use [Intel Quartus Prime Software](/nodes/Intel_Quartus_Prime_Software) -> [Create/Open Project] -> Processing -> Start Compilation. The RTL netlist can be viewed by [Intel Quartus Prime Software](/nodes/Intel_Quartus_Prime_Software) -> [Create/Open Project] -> Netlist Viewers -> RTL Viewer. 
To program the FPGA using generated RTL, use [Intel Quartus Prime Software](/nodes/Intel_Quartus_Prime_Software) -> Tools -> Programmer. 
## Components
 - [On-Chip Memory](/nodes/On-Chip_Memory)
 - [Synchronous Dynamic Random Access Memory (SDRAM)](/nodes/Synchronous_Dynamic_Random_Access_Memory_(SDRAM))

Cyclone V FPGA

A [Hard Processor System (HPS)](/nodes/Hard_Processor_System_(HPS)) with an [Arm Cortex A9](/nodes/Arm_Cortex_A9) and a set of peripheral devices. 

Cyclone V HPS

A development and education board from Intel. For computer organization and embedded systems. 
Consists of embedded processors, memory, auduio/video devices, simple I/O peripherals.  
The DE1-SoC Computer includes two instances of the [Nios II](/nodes/Nios_II)/f version, configured with floating-point hardware support
## Core Components
 - [Cyclone V HPS](/nodes/Cyclone_V_HPS)
 - [Cyclone V FPGA](/nodes/Cyclone_V_FPGA)

DE1-SoC Computer System

## A
Stands for "address". Shows the IP address for a specific hostname or domain. 
E.g. `example.com` points to `93.184.216.34`
## AAAA
Similar to A Record, but points to IPV6 addresses. 
## CNAME
Stands for "canonical name". Points a domain name (an alias) to another domain. 
E.g. `ng.example.com` points to `example.com`
## NS
Stands for "nameserver". Specifies the authoritative DNS server for a domain. 
E.g. `ns1.examplehostingprovider.com` and `ns2.examplehostingprovider.com`. 
## MX
Stands for "mail exchange". Shows where emails for a domain should be routed to. 
E.g. with priority 10 `mx.zoho.com` and priority 20 `mx2.zoho.com`, `mx.zoho.com` will be the primary mail server and the secondary will only be used if primary server is unavailable. 

DNS Records

- [Data](/nodes/Data)
- [Data Analysis](/nodes/Data_Analysis)
- [Machine Learning](/nodes/Machine_Learning)
- [Database](/nodes/Database)

Data  Science

How to analyze [Data](/nodes/Data)
## [Summary Statistics](/nodes/Summary_Statistics)

Data Analysis

[Graph](/nodes/Graph)
[Tree](/nodes/Tree)

Data Structure

## Graphs
- [Line Plot](/nodes/Line_Plot)
- [Histogram](/nodes/Histogram)
- [Box Plot](/nodes/Box_Plot)
- [Matrix Plot](/nodes/Matrix_Plot)
- [Scatterplot](/nodes/Scatterplot)- 

Data Visualization

Given a table of data with headers on the top, each row is an example/sample, and each column is a feature
## Types
Categorical features, numerical features
## Cleaning
To remove noise, outliers, missing values, duplicate data
## Features
### Aggregation
combine features (e.g. combine city data points into provinces), which reduces [Time Complexity](/nodes/Time_Complexity)/[Space Complexity](/nodes/Space_Complexity) but results in loss of data
### Transformation
#### Discretization (Binning)
Turn numerical data into categorical (e.g. age groups)
### Selection
Remove features not relevant to task

Data

a very large, integrated collection of data
## Types
 - [Traditional Database](/nodes/Traditional_Database)
 - [NoSQL Database](/nodes/NoSQL_Database)
## Database Management System
What are the benefits? 
- 24/7 access
- concurrent access
- recovery from crashes
- single data source: security, integrity
- uniform data administration/maintenance and reduced application development effort/time
## Topics
- [Logical Database Design](/nodes/Logical_Database_Design)

Database

A decision stump is a type of decision tree that consists of a single decision node and two or more leaf nodes, which represent the predicted classes. It is a simple and interpretable model that can be used as a baseline or building block for more complex models.
## Learning
Compute error using base line rule, that is number of times $y_i$ does not equal most common value. 
For each feature $j$: 
	For each threshold $t$: 
		set y-yes to most common label of objects $i$ satisfying rule $x_{ij}>t$
		set y-no to most common label of objects not satisfying rule
		set $\hat y$ to be our predictions for each object $i$ based on the rule
		compute error $E$, the number of objects where $\hat y_i\ne y_i$
		store the rule if it has the lowest error so far
output the best rule
## Cost
With $n$ examples, $d$ features, $k$ thresholds for each feature. 
- Computing the score of one rule costs $O(n)$. We need to go through all $n$ examples to find most common labels and go through all $n$ examples again to compute accuracy. We compute score up to $k*d$ rules. Therefore total cost of fitting a stump is $O(ndk$). 

Decision Stump

Decision trees are a type of supervised learning algorithm that uses a tree-like structure to model decisions and their possible consequences. They work by recursively partitioning the input data into smaller subsets based on the values of input features, until a prediction or decision can be made for each data point.
## Decision Stump
Multiple [Decision Stump](/nodes/Decision_Stump)s are used to build a decision tree. 
## Greedy Recursive Splitting
Recursively split the data such that each stumps' child's data satisfies the stump's conditions. 
## Pros
- Useful for when there's a lot of labeled data
- Easy to implement, interpretable, learning/prediction fast
- Elegantly handle small number of missing values during training
## Cons
- Problems too complicated to write a program ourselves
- Human expert can't explain why you assign certain labels
- Hard to find optimal set of rules
- Greedy splitting often not accurate, and requires deep trees
## Score Function
### Accuracy
If we use this rule, how many examples do we label correctly?
### Information Gain / Entropy
Choose split that decreases [Entropy](/nodes/Entropy) of labels the most, and thus maximizing information gain. 
Information gain = entropy(y) - $\frac {n_{leaf1}} n$entropy($y_{leaf1}$) - $\frac {n_{leaf2}} n$entropy($y_{leaf2}$). 
Where 
## Random Forest
[Random Forests](/nodes/Random_Forests) use a distribution over class at the leaves of the tree, combining predictions from multiple trees ([Ensemble Methods](/nodes/Ensemble_Methods)) to give a final classification. 

Decision Trees

Multilayered neural networks that learn from vast amounts of data. Based on [Neural Network](/nodes/Neural_Network)s. 
## Backward Pass for Common Layers
### Linear Layer
Use matrix transpose. Backward pass of correlation is convolution, vice versa. 

Deep Learning

Clusters are defined by dense regions and can be non-[Convex Set](/nodes/Convex_Set). This is a [Non-Parametric Models](/nodes/Non-Parametric_Models) clustering method. 
## Parameters
- Epsilon $\epsilon$: distance we use to decide if another point is a neighbour
- MinNeighbours: number of neighbours needed to say a region is dense
	- A point is called a "core" point if you have at least MinNeighbours neighbours. 

Density-based Clustering (DBSCAN)

Derivatives of Code

[Derivatives of Code](/nodes/Derivatives_of_Code)

Derivatives

Generally developed using [Field-programmable Gate-Arrays (FPGA)](/nodes/Field-programmable_Gate-Arrays_(FPGA)), to create [Application-Specific Integrated Circuit (ASIC)](/nodes/Application-Specific_Integrated_Circuit_(ASIC))s; both of which use [Register-Transfer Level (RTL)](/nodes/Register-Transfer_Level_(RTL)) [Hardware Description](/nodes/Hardware_Description) designs. 

## Topics
- [Timing](/nodes/Timing)

Digital Circuit

## Definition
Recursively breaks down a problem into two or more sub-problems of the same or related type, until they become simple enough to be solved directly. 
Generally uses a [Recurrence Relation](/nodes/Recurrence_Relation). 
Note that recurrence relation for runtime bounds on a function is independent of the implementation of the function. 
	For example, while a function on binary numbers can do "jank arithemetic" on the values, we only care about what number of what size sub-problems each problem divides into, without worrying about the constant-time "jank arithemetic". 

## Computing Runtime
 - [Master Theorem](/nodes/Master_Theorem)
 - [Recursion Tree](/nodes/Recursion_Tree) with geometric series based on total work at each depth
 - [Proof by Induction (Math Induction)](/nodes/Proof_by_Induction_(Math_Induction))


Divide and Conquer

People: many identifiers, e.g. SSN, name, passport #. 
Internet hosts, routers: IP address for addressing datagrams, or "name" used by humans. 
A distributed database with a hierarchy of many name servers. 
Hosts and name servers communicate to resolve names. 
## Top-level Domain (TLD) Servers
Responsible for com, org, net, edu, countries, etc.
## Authoritative DNS Servers
Organization's own DNS server(s), providing authoritative hostname to IP mappings for organization's named hosts. 
## Local DNS Name Server
Each ISP has one
## Resolution
### Iterative Query
Contacted server replies with name of server to contact
### Recursive Query
Puts burden of name resolution on contacted name server
## Caching/Updating Records
Name servers cache mappings once learning them. They may be out-of-date until all TTLs expire. 
DNS record types (resource records (RR)): A, NS, CNAME, MX
## Attacks
DDoS attacks, redirect attacks, exploit DNS for DDoS
## Topics
- [DNS Records](/nodes/DNS_Records)

Domain Name System (DNS)

Given a graph $G = (V, E)$ and an integer $k$, we want to and a subset $W$ of $V$ such that $|W| ≤ k$, and every elements of $V − W$ is joined by an edge to an element of $W$. 

Dominating Set

## Definition
Proceeds by making a choice, then solving the subproblem that results from that choice. Combine the choice and subproblem solution. 
Useful when problem instances contain overlapping subproblems. 
## Procedure
1. Determine the subproblems we may get by making a choice
2. Define a [Recurrence Relation](/nodes/Recurrence_Relation) for the optimal value of the objective function for the problem in terms of its optimal values for one or more subproblems
3. Determine the dimensions of the memo
4. Implement the algorithm (two ways)
	1. Memoization (recursion): Recursive approach that first checks the memeo to see if the solution has already been computed
	2. Iteration (dynamic programming): Loop over subproblems starting with base cases, then solve increasingly larger subproblems that uses subproblems that have already been computed
		1. Space may be saved by discarding never-to-be-used-again memo entries
5. Retrieve the optimal solution, as step 4 gives the value of the objective function for the optimal solution, but not the solution

Dynamic Programming

## Derivative Definition

For 1D:

$\frac{\partial I}{\partial x} = \lim_{\partial x \rightarrow 0} \frac {I(x + \partial x, y) - I(x,y)} {\partial x}$

For 2D:

Take two one dimensional derivatives

Filters for estimating derivatives need to sum to 0 (e.g. so that a constant image gets a correct derivative of zero). For instance, a $[-1,1]$ filter can be used to get derivative.

However, this doesn’t work well if there is noise. Solution?

Smooth, then take derivative. A trick is to take derivative of the smoothing filter first (e.g. derivative of a gaussian filter), then convolve with original image, getting the same result. This derivative will be the partial derivative of the gaussian filter for 1D.

Derivative can be approximated using the forward, backward, and centered approaches.

## Sobel Edge Detector

Uses central differencing to compute gradient image, which is more accurate. Uses a threshold on the gradient to obtain the edges.

## 2D Image Gradient

$\triangledown f = [\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}]$, with the gradient direction given as $\theta = \arctan (\frac{\partial f}{\partial x}/ \frac{\partial f}{\partial y})$. The edge strength is given by the gradient magnitude $= ||\triangledown f|| = \sqrt {(\frac{\partial f}{\partial x})^2 + (\frac{\partial f}{\partial y})^2}$.

## Canny Edge Detector

A “local extrema of a first derivative operator” approach

Design Criteria:

1.  Good Detection
    1.  low error rate for omissions (missed edges)
    2.  low error rate for commissions (false positive)
2.  Good Localization
3.  One (single) response to a given edge (eliminate multiple responses to a single edge)

Steps:

1.  Apply directional derivatives of Gaussian
2.  Compute gradient magnitude and gradient direction
3.  Non-maximum suppression (thin multi-pixel wide “ridges” down to a single pixel width)
4.  Linking and thresholding
    1.  Low, high edge-strength thresholds
    2.  Accept all edges over low threshold that are connected to edge over high threshold

### Edge Hysteresis

One way to deal with broken edge chains is to use hysteresis (a lag or momentum factor)

Maintain two thresholds $k_{high}$ and $k_{low}$. Use $k_{high}$ t find string edges to start edge chain, and use $k_{low}$ to find weak edges which continue edge chain. Typical ratio is $\frac {k_{high}} {k_{low}}=2$. Basically, edges start at edge locations past high threshold, then continue tracing edge until magnitude falls below low threshold.

Edge Detection

## Topics
 - [Karnaugh Maps](/nodes/Karnaugh_Maps)
 - [Signals and Systems](/nodes/Signals_and_Systems)

Electrical Engineering

The study of stationary electric charges or fields as opposed to electric currents. 

Electrostatics

## User Agents
The "mail reader", whose outgoing and incoming messages stored on server. 
## Mail Servers
- Mailbox: contains incoming messages for user
- Message queue: queue of outgoing mail messages
## Simple Mail Transfer Protocol (SMTP)
Between mail servers to send email messages
Ues TCP
## RFC 822
Standard format for text message format, includes: header lines (to, from ,subject) and body. 
## Sample Scenario
1. Alice uses user agent (UA) to send message to bob's email address, where here mail server places it in message queue
2. Client side of SMTP opens TCP connection to Bob's mail server
3. SMTP client sends Alice's message over TCP
4. Bob's mail server places message in Bob's mailbox, where he can invoke his UA to read message
## Improvements
### POP (Post Office Protocol)
authorization, download
### IMAP (Internet Mail Access Protocol)
more features, manipulation of stored messages on server
uses TCP


Email

 - [Electrical Engineering](/nodes/Electrical_Engineering)
 - [Computer Engineering](/nodes/Computer_Engineering)
 - [Mechanical Engineering](/nodes/Mechanical_Engineering)
 - [Civil Engineering](/nodes/Civil_Engineering)

Engineering

[Bootstrapping](/nodes/Bootstrapping) is widely used. Be careful about how models are combined. 
Doesn't work with label switching problem (i.e. the actual labels are exchangeable)


Ensemble Clustering

Classifiers that have classifiers as input. E.g. have a decision tree, naïve Bayes and k-nearest neighbours at the same time. 
## Methods
- Voting: take mode of the predictions across classifiers
- Stacking: fit another classifier that uses the prediction as features (e.g. voting + followed by decision tree)
- Random Forests: take vote from a set of deep decision trees
	- Bootstrapping: a way to generate different versions of your dataset
	- Random trees: a way to grow decision trees incorporating randomness
	- [Bagging](/nodes/Bagging) ("bootstrap-aggregating"): ensemble where you apply same classifier to different bootstraps
	- [Boosting](/nodes/Boosting): improves training error of classifiers with high $E_\text{train}$

Ensemble Methods

## Cardinality Constraint
For relationship set $R$ between entity sets $A$ and $B$, we can have the following cardinalities: 
- one-to-one
- one-to-many
- many-to-one
- many-to-many
Where if there is an arrow from $A$ to $B$, then there can be multiple $A$ for each $B$. If there are not arrows, then it is a many-to-many. 
## Participation Constraint
To enforce that every entity $A$ has an associated $B$. A bold line is used to indicate that participation is required. 
## Weak Entities
Can be identified uniquely only by considering the primary key of another (owner) entity. Weak entities sets and their identifying relationship are show with thick lines. 
## ISA ('is a') Hierarchies
If we declare $A$ ISA $B$, then every $A$ is also considered a $B$. Note that there can be overlap constraints (e.g. for $A$ ISA $C$ and $B$ ISA $C$, can Joe be both $A$ and $B$?), and covering constraints (e.g. from prev. example, does every $C$ have to be either $A$ or $B$?). 

Entity-Relationship (ER) Model

$H(X) = -\sum_{i=1}^{n} p_i \log_2(p_i)$. 

Entropy

- Feature selection is the process of identifying and selecting the most relevant and informative features (also known as variables or predictors) from a larger set of input features to improve model performance or reduce complexity.
- Relevant features help predict $y_i$ from $x_i$. 
	- In the example of food allergies, we want to know which foods are making you sick? Rather than a black box that tells you if you are sick. 
## "Association" Approach
- For each feature $j$, compute correlation between feature values $x^j$ and $y$, and say that $j$ is relevant if correlation is above 0.5 or below -0.5. 
- This usually gives unsatisfactory results as it ignores variable interactions
	- E.g. there may be a taco Tuesday, and if tacos make you sick, it will say Tuesday is relevant, but Tuesday itself is an irrelevant variable
	- E.g. diet coke and Mentos together make you sick, but not on their own so they might be deemed irrelevant on their own
## "Regression Weight" Approach
- Fit regression weights $w$ based on all features, and take features $j$ where weight $|w_j|$ is greater than a threshold. 
- Major problems with collinearity
	- E.g. if Tuesday variable always equals taco variable, it could say that Tuesdays are relevant but tacos are not
	- E.g. with two copies of irrelevant feature, it can take both irrelevant copies, such that $\hat y_i=0*a+0*b=100*a+-100*b$, where both $a$,$b$ are irrelevant
## Finding Feature Combinations
- [Search and Score Methods](/nodes/Search_and_Score_Methods)

Feature Selection

An integrated circuit designed to be configured by a customer or a designer after manufacturing. 
## Products
 - [DE1-SoC Computer System](/nodes/DE1-SoC_Computer_System)

Field-programmable Gate-Arrays (FPGA)

Financial Accounting

- [Logic](/nodes/Logic)
- [Math](/nodes/Math)
- [Statistics](/nodes/Statistics)
- [Computer Science](/nodes/Computer_Science)
- [Data  Science](/nodes/Data__Science)

Formal Science

Decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency.

Fourier Transform

where each channel is at a different frequency

Frequency Division Multiplexing (FDM)

Every input of the input vector influences every output of the output vector. 
For example, a 200x200 image x 40k hidden units will have around $200*200*40000=1600000000$ parameters for a single layer. 

Fully Connected Layer

## Notation
### Training Error
$E_{test}$ and $E_{train}$ are the test and training error respectively, such that we can formulate $E_{test}=(E_{test}-E_{train})+E_{train}$, where $E_{test}-E_{train}$ is the approximate error $E_{approx}$. 
## Concepts
### Bedrock Principle
Test data cannot influence the training phase in any way. This is especially important to make sure you don't cherry-pick the model that performs the best on the test set, as by chance, the model may have just happened to perform well on this particular test set. 
### Independent and Identically Distributed (IID) Random Variables Assumption
All examples from same distribution, are sampled independently
### Fundamental Trade-off
Training error starts high (underfitting) and decreases with training/tree depth; test error initially goes down, but eventually increases (overfitting). 
### Validation Set
Save part of training data to approximate test error
### Parameters and Hyper-Parameters
Parameters control how well we fit a dataset. Hyper-parameters control how complex the model is (can't train a hyper-parameter). 
### Optimization Bias
#### On Parameter Learning
Get lucky and find model with low training error by chance (overfitting of training error)
#### On Hyper-Parameter Tuning
One of the models might have low validation error by chance (overfitting of validation error)
## Cross-Validation
### 5-Fold
Train on 80% of data, validate on other 20%, repeat 5 times with different splits, and average score. I.e. split data into 5 folds, train on folds 1, 2, 3, 4, and compute error on fold 5, repeat for other combinations. This can be extrapolated to k-fold cross-validation. 
### Leave-one-out Cross-Validation
Train on all but one training example. 

Fundamentals of Learning

A [Gaussian](/nodes/Gaussian) probability density is used to estimate the probabily of data $x$, given parameters $m, \Sigma$, by maximizing probability $p(x|m,\Sigma)=\frac{1}{2\pi \Sigma}^{\frac 1 2} e^{-\frac 1 2 (x-m)^T\Sigma^-1(x-m)}$.  
## [Maximum Likelihood Classifier](/nodes/Maximum_Likelihood_Classifier)
Choose class $c_1$ if $p(x|c_1)>p(x|c_2)$. 
What is more of $c_1$ than $c_2$? 
## [Maximum a posteriori (MAP)](/nodes/Maximum_a_posteriori_(MAP))
Weight each likelihood by prior probabilities $p(c_1), p(c_2)$, such that the decision rule for a MAP classifier is choose class $c_1$ if $p(x|c_1)p(c_1)>p(x|c_2)p(c_2)$. 

Gaussian Classifier

An iterative optimization algorithm
1. starts with a guess $w^t$ with $t=0$
2. use the gradient $\nabla f(w^{t})$ to generate a better guess $w^{t+1}$
3. repeat step 2 for $t=t+1$
4. stop when the limit of $w^t$ as $t$ goes to $\infty$ has $\nabla f(w^t)=0$. 
More formally, $w^{t+1}=w^t-\alpha^t\nabla f(w^t)$, for $t=1,2,3...$, until $||\nabla f(w^t)|| \le \epsilon$. Where $\alpha$ is the learning rate, and we decrease $\alpha$ if it increases $f$. 

Gradient Descent

Graph Colouring

## Algorithms
[Dominating Set](/nodes/Dominating_Set)


Graph

Designed to process large amounts of image information and perform parallel tasks. Great at [Matrix Algebra](/nodes/Matrix_Algebra). 

Graphics Processing Unit (GPU)

## Greedy Algorithm Stays Ahead
A type of [Proof by Induction (Math Induction)](/nodes/Proof_by_Induction_(Math_Induction))
### What?
Prove base case is true, then prove that at each state, the greedy choice is at least as good as the choice in the optimal solution. 
### How? 
You compare the list of choice made by the greedy algorithm to a similar list for an optimal solution. 
### When? 
A value to induce upon
### Examples
[Interval Scheduling Problem](/nodes/Interval_Scheduling_Problem)

## Exchange Arguments
### What? 
Prove for arbitrary solution $S$ and greedy solution $G$, you can modify $S$ slightly to get $S'$ such that: 
 - $S'$ is more similar to $G$ than $S$; 
 - $S'$ is at least as good a solution as $S$. 
### How? 
At each stage, change $S$ by swapping elements, or adding elements to a solution. Show that the result $S$ is is no worse than before, and with enough stages $S'$ approaches a solution that is as good as $G$. 
### When?
When induction too hard :)
### Examples
[Kruskal's Algorithm](/nodes/Kruskal's_Algorithm)



Greedy Algorithm Proof

## Definition
Makes a choice based on a simple, local criterion. Then solve subproblems that result from that choice. Combine the choice and the subproblem solution
[Greedy Algorithm Proof](/nodes/Greedy_Algorithm_Proof)
## Examples of Choice
 - Interval with earliest finishing time
 - Job with earliest deadline
 - Item needed furthest in the future
 - Smallest weight edge that does not create a cycle
## Types of Problems
Optimization with Ordering: choice based on (weighted) sorting, with proof exchange argument
Intervals: choice based on (weighted) sorting, with proof by "stays ahead"
Graphs: choice based on weights, edges, verticies, with proof by contradiction
## Sample Problems
[Greedy Graph Colouring](/nodes/Greedy_Graph_Colouring)
[Min Interval Subset that Overlaps with All Intervals](/nodes/Min_Interval_Subset_that_Overlaps_with_All_Intervals)
[Optimal Scheduling](/nodes/Optimal_Scheduling)

Greedy Algorithm

Uses restrictions on the classic [Graph Colouring](/nodes/Graph_Colouring) to make it possible to use a greedy algorithm. 
Given a graph $G=(V,E)$, we want to colour each vertex with one of $k$ colours so that the two end points of any edge in $E$ receive different colours. Let $d$ be the maximum degree in the graph. 
Special condition: assume that there is at least one vertex $v$ in $V$ with degree less than $d$. 
The algorithm orders the verticies such that every vertex has at most $d-1$ neighbours among the proceeding, already-coloured verticies. This holds for verticies that have at least one neighbour among the following verticies in the ordering, or if the vertex is the one of the special vertex $v$. Thus having $v$ at the end of this ordering satisfies this condition.
A such procedure that does this algorithm is a BFS starting from $v$, then using the topological ordering of that tree. 

Greedy Graph Colouring

Hardware Description Language

[Hardware Description Language](/nodes/Hardware_Description_Language)


Hardware Description

Between the input and output of the algorithm. 
The function applies weights to the inputs and directs them trhough an activation function as the output. 