[{"id":"Dynamic Programming","folder":"Algorithms","content":"**Summary**: The DP thinking process (brute force → memoization → bottom-up), how to define states and recurrences, and classic problem types.\n\n**Last updated**: 2026-05-27\n\n---\n\n“building the next solution using the previous outcome”\n# Thinking process\n1. Brute Force\n2. optimization with memo (using space to exchange time)\n\t1. saving computation result to hashmap\n3. optimization space with bottom up strategy\n# Planning\n1. What does dp\\[i\\] mean\n2. Where do we start?\n\t1. top down: start with the biggest problem, recursively calling the smaller one (usually involve call stack)\n\t2. bottom up: from the smallest problem (array/table)\n3. Define DP rule （getting dp\\[i\\] using dp\\[i-1\\])\n4. Find base case (dp\\[0\\] and dp\\[1\\])\n# Classic Question type\n- Maximum, Minimum, Longest, shortest...\n- Best way to...\n- Making repetitive decisions (ex. climbing stairs) \n# Complexity\n- time complexity: can be high since trying every single possibilities \n- space complexity: needs to save all combinations\n\n## Related pages\n- [[Technical Interview Checklist]]\n"},{"id":"Computer Vision Overview","folder":"Computer Vision","content":"**Summary**: Sub-index and entry point for the Computer Vision cluster. Vision works *backwards* from pixel values to the scene that produced them — image **formation** (how pixels get their values), **features & reconstruction** (recovering 3D), and **recognition** (extracting meaning). Links to every CV page, grouped by sub-area.\n\n**Last updated**: 2026-05-29\n\n---\n\nComputer vision turns the physical world into digital numbers, then tries to reverse the process: given only pixel values, recover the scene that created them. A single pixel is ambiguous in isolation, so the field works **backwards** from pixels to scene:\n\n```\n3D World\n ↓ Geometry (projection, perspective)\n2D Image Plane\n ↓ Photometry (light, material, angle)\nPixel Values (just numbers!)\n ↓ Interpretation\nScene Understanding\n```\n\nThe three sub-areas below follow that arc: **formation** (world → pixels), **features & reconstruction** (pixels → 3D), and **recognition** (pixels → meaning).\n\n## Image Formation & Geometry\nHow a scene becomes pixels — *where* things appear (geometry) and *why* they look the way they do (photometry).\n- [[Image Formation & Photometry]] — how a camera turns a scene into pixels: optics, sensors, reflection models, BRDF, color\n- [[Geometric Projection Model]] — pinhole camera model and the projection formula\n- [[Camera Projection Pipeline]] — end-to-end mapping from a 3D world point to a 2D pixel\n- [[Extrinsics]] — world-to-camera coordinate transformation (rotation + translation)\n- [[From Image Plane to Pixel Coordinates]] — intrinsic matrix K and the image-to-pixel step\n- [[Ideal Points]] — points at infinity and their role in projective geometry\n- [[Lambertian Photometric Model]] — diffuse reflectance model and photometric stereo\n\n## Features & Reconstruction\nFind distinctive points, match them across views, and recover 3D structure.\n- [[Feature Detection]] — detecting corners and keypoints in images\n- [[Feature Matching]] — matching detected features across views\n- [[Two-View Reconstruction]] — recovering 3D structure from two images via epipolar geometry\n- [[RANSAC]] — robust model fitting: estimating the fundamental matrix despite outlier matches\n\n## Recognition & Retrieval\nHigher-level meaning — what's in the image, and finding specific instances.\n- [[Recognition & Vision Tasks]] — recognition as classification, the task taxonomy, and the data-driven shift\n- [[Discriminative vs Generative Methods]] — modeling the posterior vs. the likelihood/joint; the three pillars (representation, learning, inference)\n- [[Image Retrieval (Bag of Words)]] — instance recognition via the bag-of-features pipeline\n- [[Scaling Image Retrieval]] — making retrieval fast: inverted file index, TF-IDF, vocabulary tree\n\n## Leads into\nModern recognition is dominated by deep learning, which lives under Machine Learning: [[Neural Network]] → [[Convolutional Neural Network (CNN)]].\n"},{"id":"Feature Detection","folder":"Computer Vision/Features & Reconstruction","content":"**Summary**: Finding distinctive points (corners) via the sliding-window second-moment matrix, with smoothing and gradient/edge computation.\n\n**Last updated**: 2026-04-30\n\n---\n\nExtracting **unique/meaningful/unusual parts from the image**, serving as the foundation of tasks such as panorama stitching and depth estimation\n# Down stream application of feature detection\n- Panorama stitching\n- Stereo depth estimation\n- Autonomous driving\n- Image matching\n- Object recognition\n# Detecting Usual -- Sliding window technic\nCreating a sliding window (kernel), monitor the change of the window value as the window slide. Basically, we are trying to answer the question if I move this window slightly, how much do the pixels inside it change?\n## Three Scenario\n![[feature_detection_cases.svg|697]]\n- Flat feature: window movement doesn't matter\n- Edge feature: window movement in one direction cause the change\n- Corner feature: window movement anywhere would change the feature\n# Smoothing\nIt is a important and common operations that usually performed in the first step to resolve the noise in the image.\n\nGaussian kernel for 3D model: \n$$G(x,y) = \\frac{1}{2\\pi\\sigma^2} e^{-\\frac{x^2 + y^2}{2\\sigma^2}}$$\n--- start-multi-column\nID: gaussian-smoothing\nnumber of columns: 2\ncolumn size: [50, 50]\n---\n\n**Gaussian Smoothing**\n\nA discrete approximation to a Gaussian kernel with variance 1\n\n--- column-break ---\n\n

\n\n

\n\n$$\\frac{1}{273}$$\n\n

\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n

1	4	7	4	1
4	16	26	16	4
7	26	41	26	7
4	16	26	16	4
1	4	7	4	1

\n\n

\n\n--- end-multi-column\n# Edge detection\nfinding edge of the image via measuring the change of values in all the direction. Assuming h = 1 (h is how far away fix pixel you are going to look at the image)\n--- start-multi-column\nID: derivatives\nnumber of columns: 2\ncolumn size: [55, 45]\n---\nx-derivative at $(x_0, y_0)$:\n$$dx = \\frac{I(x_0+1, y_0) - I(x_0-1, y_0)}{2}$$\ny-derivative at $(x_0, y_0)$:\n$$dy = \\frac{I(x_0, y_0+1) - I(x_0, y_0-1)}{2}$$\n\n--- column-break ---\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n

	(x₀, y₀-1)
(x₀-1, y₀)	(x₀, y₀)	(x₀+1, y₀)
	(x₀, y₀+1)

\n\n--- end-multi-column\nWe can actually compute the derivative in dot product form across the entire message：\n$$I(x,y) * h = \\sum_{i=-a}^{a} \\sum_{j=-b}^{b} I(x-i, y-j) \\cdot h(i,j)$$The convolution in practice is done via efficient\n## Common Expression\nThe gradient of a single point can be defined as:\n$$\\nabla f = \\left[\\frac{\\partial f}{\\partial x}, \\frac{\\partial f}{\\partial y}\\right]$$\nThe gradient direction is:\n$$\\theta = \\tan^{-1}\\left(\\frac{\\partial f}{\\partial y}\\bigg/\\frac{\\partial f}{\\partial x}\\right)$$\nThe edge strength is can be found via:\n$$||\\nabla f|| = \\sqrt{\\left(\\frac{\\partial f}{\\partial x}\\right)^2 + \\left(\\frac{\\partial f}{\\partial y}\\right)^2}$$\n# Corner Detection\nIn the case of corner, we are observing the change of value within a tiny batch scene. There is no obvious pattern at the exact corner point where two directions meet. Instead, we are interested in the points near corner, which the gradient is more likely to have two different values. At the region near corner, the gradients point in two clearly different directions, neither one or zero\n## Implementation\nWe are actually going to implement this with 2nd-moment matrix\n$$\nM = \\sum_{(x,y) \\in W} \\begin{bmatrix} I_x^2 & I_x I_y \\\\ I_x I_y & I_y^2 \\end{bmatrix}\n$$\nwhere:\n- $I_x$: is the partial derivative of $I(x,y)$ \n- $I_y$: is the partial derivative of $I(x,y)$\n\n**Top-left:** $\\sum_W I_x^2$ \n- How much horizontal intensity change is happening in the window\n- Bigger number means pixel change sharply from left-to-right\n\n**Bottom-right:** $\\sum I_y^2$\n- How much vertical intensity change is happening in the window\n- Bigger number means pixel change sharply from top-to-bottom\n\n**Off-diagonals:** $\\sum I_x I_y$\n- How much diagonal-edge stuff is in this window, and which way does it tilt\n\n> [!question] What about the tilted corner?\n> Every corner is just a rotation of axis aligned corner, so we can always decompose any symmetric matrix into rotational and diagonal matrix.\n$$C = Q^{-1} \\begin{bmatrix} \\lambda_1 & 0 \\\\ 0 & \\lambda_2 \\end{bmatrix} Q$$\n## Step by step corner detection\n**Step 1.** Run small window and compute spatial gradient matrix\n**Step 2.** Applying non-maximal suppression to the create R\n**Step 3.** Filtering with a threshold value\n\n\n"},{"id":"Feature Matching","folder":"Computer Vision/Features & Reconstruction","content":"**Summary**: Comparing detected features across images using descriptors and distances (SSD, NCC) plus the ratio test.\n\n**Last updated**: 2026-05-01\n\n---\n\n\n**Interest Point**:\n- localized position\n- Informative about image content\n- Repeatable under variation\n\t- Geometric transformation invariant\n\t\t- location shift\n\t\t- rotation\n\t\t- scale\n\t- Photometric transformation invariant\n\t\t- the impact of Brightness\n\t\t- the impact of Exposure\n\t\t- the impact of Color shift\n- Distinctive: different features should have different features\n- example: [[Feature Detection#Corner Detection|Corner]]\n\n**Descriptor**: function that handle the information around the interest point\n- so we can actually compare them\n- naive approach\n\t- Sum of Squared Differences (SSD) $\\sum_{x,y} |W_1(x,y) - W_2(x,y)|^2$\n\t- Normalized Cross Correlation (NCC) $\\sum_{x,y} \\frac{(W_1(x,y) - \\overline{W_1})(W_2(x,y) - \\overline{W_2})}{\\sigma_{W_1} \\sigma_{W_2}}$\n- \n- sometimes, we might have ambiguity match where a lot of features from image 2 are similar to image 1. Thus, how do we measure the significance level, via the ratio distance: $SSD(f_1, f_2) / SSD(f_1, f_2')$\n"},{"id":"RANSAC","folder":"Computer Vision/Features & Reconstruction","content":"**(Robust Model Fitting)**\n\n**Summary**: RANSAC (RANdom SAmple Consensus) fits a model to data that contains outliers by repeatedly fitting to minimal random samples and keeping the model with the most inliers. In computer vision it is the standard way to estimate the fundamental matrix from noisy feature matches.\n\n**Last updated**: 2026-05-29\n\n---\n\n## Noise vs. outliers\nEvery real measurement process is imperfect, and the two kinds of error are handled very differently:\n\n- **Noise** — small jitter around the true value (a feature lands a pixel or two off). You beat noise with **more observations** — averaging many measurements, the same way [[Lambertian Photometric Model|photometric stereo]] uses more light sources.\n- **Outliers** — *gross* mistakes (a totally wrong match). More observations do **not** help: a single bad measurement can wreck the estimate. You must make a **hard decision** to detect and discard outliers before estimating.\n\nExamples of how outliers sneak in: repetitive structure (all the windows on a building look the same → a point gets mismatched), or a sensor failure (a black image vs. a black image gives a perfect-SSD match that is completely meaningless). Because outliers come from *unmodeled* sources, you can't predict where they are — so don't over-engineer; **let statistics do the heavy lifting**.\n\n## The intuition: fitting a line\nA line is defined by **2 points** (its degrees of freedom). Given a cloud of points that mostly lie on a line plus some outliers:\n\n1. Randomly pick 2 points → they define a candidate line (a **hypothesis**)\n2. Count how many other points are **consistent** with it (the **inliers** / **consensus**)\n3. A bad pick gets few inliers (e.g. 3); a good pick gets many (e.g. 20)\n4. Repeat, and keep the hypothesis with the most inliers\n\nThe winning hypothesis is a good explanation of the data.\n\n## The RANSAC algorithm (general form)\n1. Randomly choose **s** samples — typically *s* = the minimum sample size needed to fit the model\n2. Fit a model to those *s* samples\n3. Count the **inliers** that approximately fit the model\n4. Repeat **N** times\n5. Choose the model with the **largest set of inliers**\n\n\"Random sample consensus\": we randomly draw samples, fit the model, and measure the **consensus** of the rest of the data with that model.\n\n## Application: estimating the fundamental matrix\nThe [[Two-View Reconstruction#About F|fundamental matrix F]] is the model that relates corresponding points across two views (and decomposes into the camera rotation and translation). Matches come from [[Feature Matching|feature matching]], which produces outliers — so the **overall plan is to use F itself as the model to remove outliers**: find the F most points are consistent with (inliers), then drop the rest (outliers).\n\nFor **N** iterations:\n- Pick **8** pairs of correspondences (the [[Two-View Reconstruction#Solve for F|DLT / 8-point]] minimal set)\n- Estimate an **F** from these 8\n- Count inliers — the other correspondences where the epipolar constraint $\\mathbf{x}_1^\\top \\mathbf{F}\\, \\mathbf{x}_2 \\approx 0$ (below a threshold)\n- Keep the **F** with the most inliers\n\n## How many iterations N?\nThere is no guarantee, but for a target **probability of correctness** *p* you can compute *N* adaptively from the outlier proportion:\n\n$$N = \\frac{\\log(1-p)}{\\log\\!\\left(1-(1-\\epsilon)^{s}\\right)}$$\n\nwhere *p* = desired confidence, $\\epsilon$ = fraction of outliers, *s* = sample size.\n\n*N* values for **p = 0.99**:\n\n| sample size *s* | 5% | 10% | 20% | 30% | 40% | 50% |\n| --------------- | --- | --- | --- | --- | --- | ---- |\n| 2 | 2 | 3 | 5 | 7 | 11 | 17 |\n| 4 | 3 | 5 | 9 | 17 | 34 | 72 |\n| 8 | 5 | 9 | 26 | 78 | 272 | 1177 |\n\nThe striking takeaway: even with **20% outliers**, fitting F (s = 8) needs only **26 draws** for 99% confidence — that is the power of statistics. Reading down a column, larger sample size *s* (more model DOF) needs more draws; reading across a row, more outliers needs more draws.\n\n## Why degrees of freedom matter (8-point vs. 7-point)\nF has **7 degrees of freedom**, so in principle 7 correspondences suffice — but the 7-point method must enforce the nonlinear **rank constraint** ($\\det \\mathbf F = 0$, a cubic), which is expensive to solve. The **8-point DLT** drops the rank constraint and stays **linear** (solvable fast via SVD), at the cost of one extra correspondence.\n\nThis trade-off is the *real* reason DOF matters for **robust** estimation: RANSAC runs the inner solver many, many times. For a self-driving car solving structure-from-motion at 30 fps, each F estimate has a budget of roughly **1 ms**, so a fast linear solver in the inner loop beats a minimal-but-nonlinear one. With robust estimation, the number of times you estimate matters more than the cost of a single perfect estimate.\n\n## Related pages\n- [[Two-View Reconstruction]]\n- [[Computer Vision Overview]]\n- [[Feature Matching]]\n- [[Recognition & Vision Tasks]]\n"},{"id":"Two-View Reconstruction","folder":"Computer Vision/Features & Reconstruction","content":"**Summary**: Recovering 3D structure and camera motion from two views via epipolar geometry, the essential/fundamental matrix, and triangulation.\n\n**Last updated**: 2026-05-29\n\n---\n\n# Motivation \nGiven two photographs of the same scene from different angles, can we recover a 3D geometry of the scene, and the relative position and orientation of the cameras\n\n> [!question] Why are we doing this?\n> Photograph is 2D projection where the depth information is lost and it is more useful if we can use geometric relationship between the two viewpoints to recover them\n\n# Fundamental Concept\n## Depth from disparity\n$$Z_0 = \\frac{b \\cdot f}{x_L - x_R}$$\nWhere,\n* $Z_0$ is depth: distance from the cameras to the 3D point. What you compute. Real-world units.\n* $b$ is baseline: horizontal distance between the two camera centers. Known. Real-world units.\n* $f$ is focal length: distance from each camera's optical center to its image plane. Known. Pixels.\n* $X_0$ is the sideways position of the 3D point, measured from camera 1. Real-world units.\n* $x_L$ is the pixel column where the point appears in the left image. Measured. Pixels.\n* $x_R$ is the pixel column where the point appears in the right image. Measured. Pixels.\n* $x_L - x_R$ is the disparity: how much the point shifts between the two images. Pixels.\n\nThe **Depth is inversely proportional to disparity**\n## Cross-product as linear operator\n$$\\vec{a} \\times \\vec{b} = \\|\\vec{a}\\| \\|\\vec{b}\\| \\sin\\theta$$\nafter mathematical conversation, we can convert everything to:\n$$[\\mathbf{t}]_\\times = \\begin{bmatrix} 0 & -t_z & t_y \\\\ t_z & 0 & -t_x \\\\ -t_y & t_x & 0 \\end{bmatrix}$$ $$\\mathbf{t} \\times \\tilde{\\mathbf{p}} = [\\mathbf{t}]_\\times \\tilde{\\mathbf{p}}$$\nWhy? -- matrix multiplication lets us combine them with other linear operations cleanly\n## The Epipolar Geometry\n- Epipolar plane: the plane containing the 3D point X and both camera centers\n- Epipolar line: the intersection of the epipolar plane with the image planes. the matching point must lie somewhere along this line\n- Epipolar(e1, e2): how image show up in corresponding image\n### Define\n- In camera 1 coordinates, 3D point X is given by $\\mathbf{X}_1 = \\lambda_1 \\mathbf{p}$\n- In camera 2 coordinates, 3D point X is given by $\\mathbf{X}_2 = \\lambda_2 \\mathbf{p}$\n- camera 2 related to camera 1 by $[R, t]$\n- we define the following property:\n$$\n\\begin{aligned} \\mathbf{X}_2 &= RX_1 + t \\\\ \\lambda_2 q &= \\lambda_1 R p + t \\\\ \\lambda_2 [\\mathbf{t}]_\\times \\mathbf{q} &= \\lambda_1 [\\mathbf{t}]_\\times \\mathbf{R} \\mathbf{p} \\\\ 0 &= \\lambda_1 \\mathbf{q}^\\top [\\mathbf{t}]_\\times \\mathbf{R} \\mathbf{p} \\\\ 0 &= \\mathbf{q}^\\top E p \\end{aligned}\n$$\nWhere $E = [\\mathbf{t}]_\\times \\mathbf{R}$ \n# System overview\nEvery two-view reconstruction system follows the same pattern:\n- Step 1: [[Feature Detection|Detect features]] in each view\n- Step 2: [[Feature Matching|Match features]] across two views\n- Step 3: Estimate camera rotation and translation across views, finding $[R | t]$\n- Step 4: Backproject rays from camera centers to triangulate 3D point\n# Finding $[R|t]$\nFrom the [[#The Epipolar Geometry]], we know that for any pair of matching point $p, q$ across two images, the equation $0 = \\mathbf{q}^\\top E p$ must hold. We can Find E which contains the transformation from the solving this equation\n## About E\n### DOF and rank of E\nthe Essential matrix E has 5 DOF because $3 + 3 -1$\n- 3 Rotation: the camera orientation\n- 3 Translation: the direction of the placement of the camera\n- -1 scale ambiguity: we can't recover the unit\n# Find $[R|t]$ under uncalibrated cameras\nWe need to account for camera's intrinsic parameters, so\n- $p' = K_1p$ \n- $q' = K_2q$\n\nAnd we are solving for:\n$$\\mathbf{q}'^\\top \\mathbf{F} \\mathbf{p}' = 0$$\nWhere $F$ is called the fundamental matrix and $\\mathbf{F} = \\mathbf{K}_2^{-\\top} \\mathbf{E} \\mathbf{K}_1^{-1}$\n## About F\n### Solve for F\n- We can solve the problem with 7 matching points according to its DOF of 7\n- We can estimate result with 8 or more points solving $\\mathbf{A} \\mathbf{f} \\approx \\mathbf{0}$, where $A$ is a stack of matching point rows:\n$$\nrow_i = [x_2x_1, x_2y_1, x_2, y_2x_1, y_2y_1, y_2, x_1, y_1, 1]\n$$\n- In practice we don't solve $\\mathbf{A}\\mathbf{f} = \\mathbf{0}$ exactly; we seek the $\\mathbf{f}$ that **minimizes** $\\|\\mathbf{A}\\mathbf{f}\\|$ via SVD (the singular vector for the smallest singular value)\n- The raw solution is generally full rank, so we **impose** $\\text{rank}(\\mathbf{F}) = 2$ by taking its SVD and **zeroing the smallest singular value**\n- We use $n \\ge 8$ (rather than the minimal 7) precisely so the problem stays **linear**: dropping the rank constraint during the solve costs one extra correspondence but avoids a nonlinear ($\\det\\mathbf F = 0$, cubic) solve — much faster, which matters inside RANSAC's inner loop\n\nBecause real correspondences contain outliers, this estimation is run inside [[RANSAC]] — repeatedly fitting F from random 8-point samples and keeping the one with the most inliers.\n\n### DOF and rank of F\nthe Fundamental matrix F has 7 DOF because $9 - 1 - 1$\n- -1 scale ambiguity: we can't recover the unit\n- -1 rank constraint: the multiplication of F will produce a linear passing through the epipole line\n### F as a function\nWe can use $F$ as a function calculating the epipolar line. Let $x$ be the point in the first image, then $I=F^Tx'$ is the epipolar line in the first image"},{"id":"Camera Projection Pipeline","folder":"Computer Vision/Image Formation & Geometry","content":"**Summary**: The full pipeline converting a 3D world point to a 2D pixel — extrinsics, projection, and intrinsics composed into one matrix Π = K[R | −Rc].\n\n**Last updated**: 2026-04-24\n\n---\n\nThe conversation pipeline that convert 3D worlds into 2D images.\n\nThe pipeline covers 3 major steps:\n- [[Extrinsics#|standardization Process]]\n- [[Geometric Projection Model|Camera Projection]]\n- [[From Image Plane to Pixel Coordinates|internal translation]]\n\nthe Projection function:\n$$\\begin{aligned} \\Pi &= K \\underbrace{\\begin{bmatrix} 1&0&0&0\\\\0&1&0&0\\\\0&0&1&0 \\end{bmatrix}}_{\\text{projection}} \\underbrace{\\begin{bmatrix} R & \\mathbf{0}\\\\0&0&0&1 \\end{bmatrix}}_{\\text{rotation}} \\underbrace{\\begin{bmatrix} I_{3\\times3} & -\\mathbf{c}\\\\0&0&0&1 \\end{bmatrix}}_{\\text{translation}} \\\\ &= K[R \\mid -Rc] \\end{aligned}$$\n\nLet $q=(x, y, z, 1)$ which is cord in the real world, we will\n- $\\Pi q$ \n- Divide by the last coordinate to get the final 2D pixel coordinates \n$$\\left(\\frac{(\\Pi q)_1}{(\\Pi q)_3},\\ \\frac{(\\Pi q)_2}{(\\Pi q)_3}\\right)$$\n"},{"id":"Extrinsics","folder":"Computer Vision/Image Formation & Geometry","content":"**Summary**: The world-to-camera transformation: translate the world origin to the camera, then rotate axes to align, giving the extrinsic matrix.\n\n**Last updated**: 2026-04-24\n\n---\n\nA process of standardization ^7b2cf4\n# Problem\nThere **TWO** coordinate system when we are talking pictures -- the camera coordinate system and the world coordinate system. Me must standardize both info when handling problem that involve both systems.\n# Converting Process\nReference to the projection formula:\n![[Geometric Projection Model#^1b2ea1]]\n![[Geometric Projection Model#^0d2ac1]]\n\nWe need to standardize them before doing projection\n## Step 1. Finding positions\n- **Camera position** — where is the camera in the world?\n- **Camera orientation** — which direction is the camera facing?\n## Step 2. Translate\nMove the origin of the world to where the camera is sitting.\n$$T = \\begin{bmatrix} I_{3\\times3} & -\\mathbf{c} \\\\ 0 & 0 & 0 & 1 \\end{bmatrix}$$\nwhere:\n- $c$ is the world position vector of camera\n## Step 3. Rotate\nRotate everything so the camera axes align with the world axes. \n$$R = \\begin{bmatrix} \\mathbf{u}^T \\\\ \\mathbf{v}^T \\\\ \\mathbf{w}^T \\end{bmatrix}$$\nwhere $u$, $v$, $w$ are the camera's axis directions\n## Step 4. Combine everything\n\nNow the camera sits at the origin looking down the correct axis — \nexactly what the projection formula expects.\n\n$$\\text{Extrinsics} = R \\times T$$\nwhere:\n- $T$ is translation matrix (camera position)\n- $R$ is rotation matrix (camera orientation)\n\nAt the end, we have\n$$(x, y, z) \\rightarrow (x_{cam}, y_{cam}, z_{cam})$$\n> [!question] Are translation and rotation interchangeable? \n> No, rotation would spins around the origin. Rotation first, would cause the world point spin around the world origin.\n\n"},{"id":"From Image Plane to Pixel Coordinates","folder":"Computer Vision/Image Formation & Geometry","content":"**Summary**: The intrinsic matrix K that converts physical image-plane coordinates into pixels (focal length, skew, principal point).\n\n**Last updated**: 2026-05-29\n\n---\n\nThe projection formula gives us a position in physical units — not pixels yet. K (the intrinsic matrix) bridges this gap by converting image plane coordinates into actual pixel coordinates.\n\n# General Pipeline \n$$\\text{pixel} = K \\times \\text{Projection} \\times \\begin{bmatrix} x \\\\ y \\\\ z \\\\ 1 \\end{bmatrix}$$\nwhere:\n- $\\begin{bmatrix} x \\\\ y \\\\ z \\\\ 1 \\end{bmatrix}$ is the physical point\n- $Projection$ is the [[Geometric Projection Model#Projection Formula|model here]]\n- $K$ is the [[#K transformation|transformation]]\n# K transformation\nIn general:\n$$K = \\begin{bmatrix} -d_x' & s & c_x' \\\\ 0 & -d_y' & c_y' \\\\ 0 & 0 & 1 \\end{bmatrix}$$\nWhere:\n- $d_x'$, $d_y'$ — **focal length in pixel units** along the x and y axes. Their ratio $\\alpha = d_x'/d_y'$ is the **aspect ratio**: are the pixels square? \n (equal unless pixels are not square)\n- $s$ — **skew**: are the pixels rectangular? \n (0 unless pixels are shaped like rhombuses)\n- $(c_x', c_y')$ — **principal point**: where is the center of the image? \n (origin unless optical axis does not intersect image plane at center)\n---\nK is called **intrinsic** because these are fixed properties of the \ncamera hardware -- they do not change regardless of where the camera \nis pointing."},{"id":"Geometric Projection Model","folder":"Computer Vision/Image Formation & Geometry","content":"**Summary**: The pinhole-camera projection formula (3D → 2D) and how homogeneous coordinates turn it into a single matrix multiply.\n\n**Last updated**: 2026-05-29\n\n---\n\nThe real world is 3D, but photos are 2D. Every time we capture an image, the 3D world \"collapses\" from three dimensions down to two — losing one dimension (depth). The Geometric Projection model explains exactly how that collapse happens\n# How camera works\n![[pinhole_camera_model.svg]]\n# Projection Formula\n$$(x, y, z) \\rightarrow \\left(-d\\frac{x}{z},\\ -d\\frac{y}{z}\\right)$$\nwhere ^1b2ea1\n- $(x,y)$ is coordinates ^0d2ac1\n- $d$ is focal length\n- $z$ is how far the object is from the pinhole\n# Optimizing Projection Formula\nWe want to apply many transformations to millions of pixels as efficiently as possible, but division by z is not a matrix operation -- it breaks the chain, forcing us to process each transformation step by step for every points. To solve the issue, we use **Homogeneous coordinates**.\n## The trick\n### Homogenenous coordinates\n- adding an extra coordinate at the end, so going from $(x, y) \\Rightarrow \\begin{bmatrix} x \\\\ y \\\\ 1 \\end{bmatrix}$ and $(x, y, z) \\Rightarrow \\begin{bmatrix} x \\\\ y \\\\ z \\\\ 1 \\end{bmatrix}$\n- at the end, converting back from $\\begin{bmatrix} x \\\\ y \\\\ w \\end{bmatrix} \\Rightarrow (x/w,\\ y/w)$ and $\\begin{bmatrix} x \\\\ y \\\\ z \\\\ w \\end{bmatrix} \\Rightarrow (x/w,\\ y/w,\\ z/w)$\n- when the last coordinate $w = 0$, this conversion divides by zero — the point is at infinity. See [[Ideal Points]].\n### Applying the trick\nWe write the 3D point in homogeneous form:\n$$\n\\begin{bmatrix} x \\\\ y \\\\ z \\\\ 1 \\end{bmatrix}\n$$\nWe write the projection as matrix multiplication:\n$$\\begin{bmatrix} -d & 0 & 0 & 0 \\\\ 0 & -d & 0 & 0 \\\\ 0 & 0 & 1 & 0 \\end{bmatrix} \\begin{bmatrix} x \\\\ y \\\\ z \\\\ 1 \\end{bmatrix} = \\begin{bmatrix} -dx \\\\ -dy \\\\ z \\end{bmatrix}$$\nAt the end of everything, we may divide by the last coordinate:\n$$\\begin{bmatrix} -dx \\\\ -dy \\\\ z \\end{bmatrix} \\rightarrow \\left(-d\\frac{x}{z},\\ -d\\frac{y}{z}\\right)$$\n### Main Reason\nAll the transformations can now be chained into one single matrix and applied to every point in one shot. The division by z is deferred to the very end -- keeping the entire pipeline as clean matrix multiplications.\n"},{"id":"Ideal Points","folder":"Computer Vision/Image Formation & Geometry","content":"**Summary**: Points at infinity in homogeneous coordinates (last coordinate w = 0) and the line at infinity — where parallel lines meet.\n\n**Last updated**: 2026-05-29\n\n---\n\nNormally, parallel lines never meet. But when a camera \ncaptures the world (see [[Geometric Projection Model]]), parallel lines appear to converge toward a single \npoint on the horizon. We call these points vanishing points or ideal points **How do we represent and handle this mathematically?**\n# Mathematical Definition\nIn homogeneous coordinates, an ideal point is any point where the \nlast coordinate w = 0:\n\n$$(x, y, 0)^T$$\n\nWhen you try to convert back to regular coordinates, you divide by w:\n\n$$\\left(\\frac{x}{0},\\ \\frac{y}{0}\\right) = \\infty$$\n\nDivision by zero — the point is at infinity. It exists in projective \nspace but not in regular Cartesian space.\n# How to Find It\nGiven two parallel lines in homogeneous coordinates:\n\n$$\\mathbf{l} = (a, b, c)^T \\quad \\mathbf{l}' = (a, b, c')^T$$\n\nTheir intersection is given by the cross product:\n\n$$\\mathbf{x}_\\infty = \\mathbf{l} \\times \\mathbf{l}' = (c - c')(-b, a, 0)^T \\sim (-b, a, 0)^T$$\n\nThe last coordinate is always 0 — confirming this is an ideal point \nregardless of what c and c' are.\n### The Line at Infinity\nAll ideal points have the form $(x, y, 0)^T$. There is one special \nline that contains ALL ideal points — the line at infinity:\n\n$$\\mathbf{l}_\\infty = (0, 0, 1)^T$$\n\n**Proof** — a point lies on a line if $\\mathbf{l}^T\\mathbf{x} = 0$:\n\n$$(0, 0, 1) \\cdot (x, y, 0) = 0 + 0 + 0 = 0$$\n\nWorks for every ideal point regardless of x and y.\n# Use Case\nTODO: can do some research and put more use case"},{"id":"Image Formation & Photometry","folder":"Computer Vision/Image Formation & Geometry","content":"**Summary**: How a real camera turns a 3D scene into pixel values — camera design (pinhole → lens → digital sensor), what determines a pixel's brightness, reflection models and the BRDF, and color sensing.\n\n**Sources**: CSE 152A (SP26, Manmohan Chandraker) — Photometry & Geometry of Image Formation.\n\n**Last updated**: 2026-05-29\n\n---\n\nTwo fundamental questions in computer vision:\n\n1. **Photometry** — *why does the image look the way it does?* (intensity, color, brightness)\n2. **Geometry** — *where does everything appear in the image?* (placement, projection, perspective — see [[Geometric Projection Model]])\n\nThe same scene looks completely different depending on lighting — e.g. Monet's haystacks at different times of day: same geometry, different photometry.\n\n## Camera Design\n\n### Problem: just film\n- Every point on an object sends light in **all directions**\n- Multiple rays hit the same spot on film → **blurry mess**\n\n### Solution: pinhole camera\n- Add a **barrier with a tiny hole (aperture)**\n- Only **one ray per point** passes through → each point maps to exactly one point on the film → sharp image\n- Resulting image is **flipped upside down**\n\n### Camera obscura\n- Literally a dark room/box with a pinhole\n- Used historically to observe eclipses and as an artist's aid (e.g. Vermeer); Leonardo da Vinci described objects appearing in proper form, reduced in size, reversed\n\n### Aperture & the circle of confusion\n- Real apertures have **finite size** → rays from one point hit slightly different spots → **circle of confusion** (blur)\n- **Smaller aperture** → sharper, BUT less light gets through and **diffraction** kicks in at very small sizes → there is a **sweet spot**\n\n| Aperture | Result |\n|---|---|\n| 2mm | Very blurry |\n| 1mm | Blurry |\n| 0.6mm | Clearer |\n| 0.35mm | Sharp |\n| 0.15mm | Sharp |\n| 0.07mm | Blurry again (diffraction) |\n\n### Adding a lens\n- A lens **bends all rays from one point back together** onto one spot → allows a **large aperture** (lots of light) AND a sharp image\n- Only objects at a **specific distance** are perfectly in focus; other distances → circle of confusion → **background blur (bokeh)**\n- Changing lens shape changes the focus distance\n\n### Digital camera\n- Replaces film with a **sensor array**; each cell is a light-sensitive diode converting **photons → electrons** (two types: **CCD** and **CMOS**)\n- Recording chain: `light source → hits scene → reflects → passes through imaging system → hits sensor`\n\n### The raster image (pixel matrix)\n- An image is a **2D grid of numbers**, each = brightness (0 = black, 1 = white, between = grey)\n- Color image = **3 matrices** stacked: R, G, B\n\n## What Determines a Pixel's Value?\n\nA pixel's brightness depends on **5 factors** — which is why a single pixel is too ambiguous to interpret alone:\n\n1. **Illumination** — strength, direction, color of the light source\n2. **Surface orientation** — angle between surface and light\n3. **Surface material** — how it reflects light (shiny vs. matte)\n4. **Nearby surfaces** — shadows, inter-reflections\n5. **Camera parameters** — exposure, aperture, sensor sensitivity\n\n### Intensity & surface orientation (foreshortening)\n$$I(x) \\propto (S \\cdot N(x))$$\n- **S** = light direction, **N(x)** = surface normal\n- The dot product is between 0 and 1: 0° → cos 0 = 1 (max brightness); 45° → 0.7; 90° → 0 (no light)\n- Intuition: sunlight directly overhead (equator) is hot & bright; at a low angle (poles) the same light spreads over more area → cold & dim\n\n## Reflection Models\n\n### Diffuse (Lambertian) reflectance\n- Some light **absorbed** (controlled by albedo ρ); the rest **scattered equally in all directions**\n- Looks equally bright from any viewing angle — e.g. cloth, concrete, matte paint\n- Modeled in depth in [[Lambertian Photometric Model]]\n\n### Specular reflection\n- Light reflects at a **specific angle** (angle in = angle out); appearance changes with viewing angle; creates **highlights** — e.g. mirrors, shiny metal\n\n> Most real surfaces = a **mix of diffuse + specular**.\n\n### The full image-formation equation (BRDF)\n$$L_o(\\omega_o) = \\int_\\Omega L_i(\\omega_i)\\, f(\\omega_o, \\omega_i)\\, (\\omega_i \\cdot n)\\, d\\omega_i$$\n\nAs a **chain of percentages**:\n\n| Term | Meaning |\n|---|---|\n| $L_i(\\omega_i)$ | How much light is coming in |\n| $(\\omega_i \\cdot n)$ | What % of that light lands on the surface (geometry) |\n| $f(\\omega_o, \\omega_i)$ | What % of landed light reflects toward the camera (material) |\n| $L_o(\\omega_o)$ | Final pixel brightness |\n\nEach term is an independent fraction applied in sequence, so they multiply. And $\\text{BRDF} = \\text{Diffuse} + \\text{Specular}$.\n\n### Other lighting effects (beyond the BRDF)\n- **Refraction** — light bends passing *through* a surface (glass, water); the BRDF only models light bouncing *off* surfaces\n- **Subsurface scattering** — light enters, bounces inside the material, exits elsewhere (e.g. skin backlit; CGI skin like Gollum)\n- **Fluorescence** — absorbed at λ₁, instantly re-emitted at λ₂ (e.g. highlighter under UV)\n- **Phosphorescence** — like fluorescence but time-delayed (glow-in-the-dark)\n\n## Color\n\n### Light is a spectrum\n- Visible range 400–700nm: **400nm** violet/blue, **550nm** green/yellow (peak human sensitivity), **700nm** red\n\n### Why RGB?\n- Human eyes have only **3 cone types**: **S** (~420nm, blue), **M** (~534nm, green), **L** (~564nm, red), plus **rods** for intensity (night vision, no color)\n- Only 3 receptors → **3 numbers** suffice to describe any color we see → cameras mimic this with RGB\n\n| Animal | Cone Types | Color Vision |\n|---|---|---|\n| Night animals | 1 | None |\n| Dogs | 2 | Limited |\n| Humans | 3 | Normal |\n| Fish/Birds | 4 | Beyond human |\n| Mantis shrimp | 12 | Extraordinary |\n\n### Surface color\n- A surface's color = which wavelengths it **reflects** vs. **absorbs** (red tomato reflects red, absorbs the rest)\n- Color seen = **E(λ) × ρ(λ)** (light spectrum × surface albedo spectrum)\n\n### Color sensing: the Bayer grid\n- Sensors measure only **intensity**, not color → place a **color filter** over each cell\n- Pattern alternates R, G, B (twice as many green — matches human sensitivity); each cell records one channel\n- Missing channels are **estimated from neighbors** → **demosaicing**\n\n## Key Insights\n- **The plight of the poor pixel** — a pixel value is set by 5 factors at once, so it can't be interpreted in isolation; context is everything.\n- **Local differences matter most** — we recognize a pencil sketch with no color/accurate brightness because recognition relies on **edges and local differences**, not absolute values.\n- **Adelson checker-shadow illusion** — squares A and B are the *exact same* pixel value but look different because the brain compensates for shadow → raw pixel values ≠ perceived reality.\n\n## Related pages\n- [[Computer Vision Overview]]\n- [[Lambertian Photometric Model]]\n- [[Geometric Projection Model]]\n- [[Feature Detection]]\n"},{"id":"Lambertian Photometric Model","folder":"Computer Vision/Image Formation & Geometry","content":"**Summary**: Recovering surface normals and albedo from several images under known lighting (photometric stereo), assuming a matte Lambertian surface.\n\n**Last updated**: 2026-05-27\n\n---\n\nModel we use to convert an image to 3D Model\n## Motivation\n\n> [!question] Why not inferencing 3D from one image?\n> The formation of an image can be contributed to by factors such as the distance from the light source, the brightness of the light source, the reflectiveness of the surface, and so on. A single pixel of one image is baked with all of this information. If we just use a single image to infer the 3D model, then the result will be random as hell.\n\n> [!question] Why not inferencing 3D from multiple random images of the same object?\n> As we discussed earlier, the brightness of a pixel can depend on multiple factors. Getting an accurate 3D model is like running a controlled experiment, where you have to keep most variables fixed and only a few changeable.\n\n## The Lambertian Photometric Model\nTo implement this controlled experiment, we will use the Lambertian Photometric model. One key assumption of the Model is that the surface is **matte** (the surface reflect equally regardless of viewing angle). \n\nThe brightness of each pixel is described by:\n$$\nI_k(x,y) = ρ(x,y) * n̂(x,y) · sᵏ\n$$\nWhere:\n- $I_k(x,y)$: the brightness of coordinate $(x, y)$ (known; we measure) \n- $ρ(x,y)$: how reflective the surface is (unknown)\n- $n̂(x,y)$: the normal direction of the surface (unknown; critical information we want)\n- $sᵏ$: the direction of light k (known; we control)\n\n\nBy stacking at least 3 images with different known lighting directions, we get enough equations to solve for the unknowns - giving us the surface normals and albedo at every pixel. The more images (light directions) we provide, the more robust our solution becomes. \n## Solving LP Model in actually application\n### Step 1. Simplify\nDefine:\n$$b(x,y) = \\rho(x,y) \\cdot \\hat{n}(x,y)$$\n\nSince $\\rho$ is a constant and $\\hat{n}$ is a vector,\n$$\nb(x,y) = \\begin{bmatrix} \\rho n_1 \\\\ \\rho n_2 \\\\ \\rho n_3 \\end{bmatrix}\n$$\n### Step 2. New equation\nWe now are trying to solve for:\n$$I^k(x,y) = b(x,y) \\cdot s^k = \\begin{bmatrix} \\rho n_1 \\\\ \\rho n_2 \\\\ \\rho n_3 \\end{bmatrix} \\cdot \\begin{bmatrix} s^k_1 \\\\ s^k_2 \\\\ s^k_3 \\end{bmatrix}$$\n### Step 3. Stack for matrix form\nWith K images, we can stack them for fast computation. We have:\n$$\\begin{bmatrix} I^1(x,y) \\\\ I^2(x,y) \\\\ I^3(x,y) \\end{bmatrix} = \\begin{bmatrix} s^1_1 & s^1_2 & s^1_3 \\\\ s^2_1 & s^2_2 & s^2_3 \\\\ s^3_1 & s^3_2 & s^3_3 \\end{bmatrix} \\begin{bmatrix} \\rho n_1 \\\\ \\rho n_2 \\\\ \\rho n_3 \\end{bmatrix}$$\nWe can simplify the representation to:\n$$I = Sb$$\nWhere:\n- $I$ is the measured brightness values (known)\n- $S$ is the matrix of light directions (known)\n- $b$ is what we are solving for (unknown)\n### Step 4. Solving for b\nWe will use Least squares to find the value of b that minimizes the total error between the brightness values our model predicts and the brightness values the camera actually measured.\n\nWe can solve for b with the following equation:\n$$b = (S^TS)^{-1}S^TI$$\n### Step 5. Get albedo and normal value\n- $\\rho(x,y) = \\|b(x,y)\\|$ (we are scaling a unit vector, the length is the scaler)\n- $\\hat{n}(x,y) = \\frac{b(x,y)}{\\|b(x,y)\\|}$ (typical way of finding the unit vector)\n### Step 6. Repeat this for every single pixel\n\n"},{"id":"Discriminative vs Generative Methods","folder":"Computer Vision/Recognition & Retrieval","content":"**Summary**: Two paradigms for learning-based recognition. **Discriminative** methods model the posterior (decision boundaries); **generative** methods model the likelihood and prior (the full data distribution). This page also covers the statistical (Bayes) viewpoint and the three pillars of any recognition method: representation, learning, inference.\n\n**Last updated**: 2026-05-29\n\n---\n\nWhen we can't hand-define a model for a category (you can't write the \"cat algorithm\" — see [[Recognition & Vision Tasks]]), we learn from labeled examples. There are two dominant ways to set up that learning: **discriminative** and **generative**.\n\n## The statistical viewpoint\nTake a classification question — *given an image, is it a zebra?* — and frame it probabilistically. Applying Bayes' rule to the ratio of \"zebra\" vs. \"no zebra\":\n\n$$\\underbrace{\\frac{p(\\text{zebra}\\mid \\text{image})}{p(\\text{no zebra}\\mid \\text{image})}}_{\\text{posterior ratio}} = \\underbrace{\\frac{p(\\text{image}\\mid \\text{zebra})}{p(\\text{image}\\mid \\text{no zebra})}}_{\\text{likelihood ratio}} \\cdot \\underbrace{\\frac{p(\\text{zebra})}{p(\\text{no zebra})}}_{\\text{prior ratio}}$$\n\n- **Posterior** $p(\\text{zebra}\\mid\\text{image})$ — given the pixels, how likely is \"zebra\"? (Usually what we want for classification.)\n- **Likelihood** $p(\\text{image}\\mid\\text{zebra})$ — if you sampled from the distribution of all zebra images, how likely is *this* image?\n- **Prior** $p(\\text{zebra})$ — how common are zebras to begin with?\n\n(Conditional-probability reminder: $p(A\\mid B)$ restricts the universe to $B$ and asks how often $A$ also happens — i.e. $p(A\\cap B)/p(B)$.)\n\nThe two paradigms take opposite sides of this equation.\n\n## Discriminative methods\nModel the **posterior** $p(\\text{class}\\mid\\text{image})$ **directly**. They don't care what a zebra \"looks like\" — only that *zebra* and *not-zebra* are well separated. The output is a **decision boundary**: given a feature representation of the image, which side does it fall on?\n\n- Example: **SAM (Segment Anything)** — type \"people\" and it returns a boundary between *people* and *not-people* pixels.\n- Historically the dominant, most powerful approach for recognition.\n\n## Generative methods\nModel the **likelihood** $p(\\text{image}\\mid\\text{class})$ (and the prior) — equivalently the **joint distribution** $p(\\text{image}, \\text{class}) = p(\\text{image}\\mid\\text{class})\\,p(\\text{class})$. The question becomes: *if I sampled from the concept \"zebra,\" how likely is a set of pixels like this?* A good zebra model assigns high probability to zebra images and low probability to motorbike images.\n\n- Example: **generative AI** — image/video generation (e.g. Sora) is generative modeling done well.\n\n## Discriminative vs. generative: the trade-off\nThe lecture's intuition: **\"I can recognize a cat but I can't draw one.\"**\n\n- **Recognizing = discriminative.** To tell cats from dogs you only need an abstract notion that they *differ*. The posterior is a \"slice\" of the joint — enough to classify, and easier to learn.\n- **Drawing = generative.** To draw a cat you must know its *whole appearance distribution*. The joint is strictly more expressive than the posterior, so generative modeling asks a much harder question.\n\nBut generative is more **powerful**: modeling the full distribution gives you distances between concepts, interpretability, \"give me another zebra slightly different from this one,\" and generation. A discriminative model only knows *boundaries* — it can't say whether two zebras are similar, nor generate a new one.\n\n## Three pillars of a recognition method\nAny learning-based method (discriminative or generative) must address three issues:\n\n1. **Representation** — how to represent a category. The key property is **expressivity**, whose counterpart is **invariance**: a good representation is robust to imaging variations (viewpoint, illumination, occlusion, scale, deformation, clutter) and to intra-/inter-class variation (see [[Recognition & Vision Tasks]]).\n2. **Learning** — how to form the classifier from training data (input–output pairs: images → labels). This is where the **training objective** differs by paradigm\n\t- **Generative → maximize likelihood.** Tune the model so the training images get high probability under their class (maximum-likelihood estimation). You fit the **data distribution** itself.\n\t- **Discriminative → maximize performance on the train/validation sets.** Tune the decision boundary to classify correctly, measured on the training set and checked on validation to avoid overfitting. You fit the **boundary**, not the data.\n3. **Inference** — how the learned model is applied to *new* images at test time, and how efficiently. E.g. face detection must scan boxes at all locations and scales, so scanning speed sets the detection efficiency.\n\n## Levels of supervision\nSupervised learning needs labels, and richer supervision unlocks richer tasks (at greater labeling cost):\n\n- **Image label** (\"contains a motorbike\") → classification\n- **Bounding box** → localization / detection\n- **Pixel mask / boundaries** → segmentation\n- **Part-level labels** (wheels, handlebars, seat) → fine-grained / part understanding\n\n## Related pages\n- [[Recognition & Vision Tasks]]\n- [[Image Retrieval (Bag of Words)]]\n- [[ML Overview]]\n- [[RANSAC]]\n"},{"id":"Image Retrieval (Bag of Words)","folder":"Computer Vision/Recognition & Retrieval","content":"**Summary**: Image retrieval (instance recognition) finds the same specific instance or place in a large image database. The classic approach is **bag of words** (bag of features): extract features, learn a visual vocabulary by clustering, represent each image as a histogram of visual-word frequencies, then compare images by the distance between those histograms.\n\n**Last updated**: 2026-05-29\n\n---\n\nImage retrieval — also called **instance recognition** — is the first kind of recognition we study. Unlike *category* recognition, we want the *same specific instance*, so [[Recognition & Vision Tasks|intra-class variation]] doesn't apply here.\n\n## Applications\n- **Place recognition** for self-driving / robots: pre-capture a database of images across a city or building; later take one image and find the closest match to localize (\"which block / room am I in?\").\n- **Photo search on your phone** — instantly retrieve among tens of thousands of images.\n- **Google image search** — upload an image, find it (and near-duplicates) among a billion.\n\n## Why is it hard?\nTwo guiding principles shape every retrieval method:\n\n1. **Robustness to imaging variations** — find the same instance despite changes in scale, viewpoint, lighting, occlusion, clutter, blur, and noise.\n2. **Efficiency** — the database is huge and results must be near-instant.\n\n## Baseline: just match local features\nRetrieval is fundamentally the [[Feature Matching|feature matching]] we already know, scaled up:\n\n- For every training image, run [[Feature Detection|feature detection]], extract a patch around each feature, and push all patches into one big list (an index).\n- For a query image, extract its patches the same way; for each, find the closest match in the index (e.g. lowest SSD / smallest vector distance).\n- The training image with the **most matched patches** is the closest instance.\n\nThis works, but doesn't scale ([[#Why a visual vocabulary? (why step 2 exists)|see why]]) and does not generalized — which is what motivates the bag-of-words representation.\n\n## Bag of words: the idea\nBorrowed from text search (Salton & McGill, 1983 — the representation under classic Google document search). A **bag of words** is an *orderless* representation: throw away all structure and keep only **which words appear and how often**.\n\n- **Text example:** the State-of-the-Union addresses of 2002 vs. 2011. With no other context, word frequencies alone reveal the moment — 2002 emphasizes *security, freedom, terror*; 2011 emphasizes *jobs, business, economy*.\n- **For images:** destroy an image's structure and treat it as a **bag of patches**. Even unordered, the patches (a bit of face, some vegetation, some building) let you infer the image contained a person, a building, flowers — enough to classify.\n\n## The four-step pipeline (bag of features)\n1. **Extract features.** From every training image, extract patches — either on a **regular grid** (e.g. subdivide into 20×20 patches) or around interest points (corner detectors, SIFT). Each patch becomes a **descriptor**: a vector representing it (simplest: stack the patch's intensities — a 10×10 patch → a 100-D vector), mapping image locations into a high-dimensional feature space.\n2. **Learn a \"visual vocabulary.\"** Cluster all the feature vectors; each **cluster center is a \"visual word.\"** A patch is then described by *which cluster it belongs to*, not its raw pixels or vector representation. (A \"circle-ish\" cluster might come from a car wheel or a round window — we only care that something looked like that.)\n3. **Represent images by frequencies of \"visual words.\"** Like word frequencies in the speeches, each image becomes a **histogram** over the vocabulary: how many of its patches fall into each cluster. This gives every image a fixed-length vector.\n4. **Use distances between representations for classification.** Compare two images by the distance between their histograms; classify with **nearest neighbors**.\n\n## Why a visual vocabulary? (why step 2 exists)\nNaive patch-to-patch matching is **intractable** at scale: 1M images × 1k features ≈ 1 **billion** patches; a query of 1k patches × 1B ≈ **1 trillion** comparisons. And you don't need exact matches — only closeness. Clustering the feature space collapses a billion patches into a small vocabulary, so you compare **global** bag-of-words histograms instead of individual patches — far more efficient.\n\n(High-dimensional feature spaces help here: even a 100-D space with 256 intensity levels per dimension holds $256^{100}$ distinguishable points — plenty to represent diverse features. The clusters in that space *are* the visual words.)\n\n## The tools\nEach pipeline step rests on a standard tool:\n\n- **Build the vocabulary → [[k-means Clustering]].** Cluster all feature vectors; the cluster centers are the visual words.\n- **Represent an image → a histogram.** Match each patch to its nearest visual word and count: bin $i$ = number of patches closest to codeword $i$. The result is a fixed-length vector (one entry per word). A histogram is just a **vector representation of a distribution**.\n- **Compare images → histogram distance.** With a vocabulary of $V$ words, compare query $q$ and database image $d_j$ by **cosine similarity** (the normalized dot product):\n$$\\text{sim}(d_j, q) = \\frac{\\langle d_j, q\\rangle}{\\lVert d_j\\rVert\\,\\lVert q\\rVert} = \\frac{\\sum_{i=1}^{V} d_j(i)\\,q(i)}{\\sqrt{\\sum_i d_j(i)^2}\\,\\sqrt{\\sum_i q(i)^2}}$$\n Cosine measures **similarity** (maximize it — identical vectors → 1); the **Euclidean distance** $\\lVert d-q\\rVert$ measures **dissimilarity** (minimize it — identical vectors → 0).\n- **Classify on top → [[Nearest-Neighbor Classification]].** Retrieval *is* nearest-neighbor: return the database image with the highest similarity; for labeled classification, take the majority label among the *k* nearest (kNN).\n\nEverything above — features → clustering → histograms → distances — exists to give each image an **efficient yet expressive vector**. (A raw 1000×1000 image is a trivial 1M-D pixel vector: expensive *and* meaningless. The histogram compresses it into a few semantically meaningful dimensions.)\n\n## Evaluating retrieval: precision, recall, average precision\nTreat retrieval as returning matches one-by-one from best to worst. At each step:\n\n- **precision** = relevant returned / total returned\n- **recall** = relevant returned / total relevant in the database\n\nPlotting precision vs. recall over the ranked list gives a **PR curve**. A perfect retriever (all relevant items first) traces a flat line at precision = 1 → area = 1. Summarizing the curve by one number gives the **Average Precision (AP)** = area under the PR curve (also called area-under-the-curve elsewhere).\n\nCaveat: two methods can have the **same AP** but very different PR curves, so AP alone isn't enough to deploy — you also pick an operating point (some apps favor recall, e.g. don't miss pedestrians; others favor precision).\n\n(This pipeline and the [[Bayesian Classification (MAP & ML)|Bayesian skin classifier]] are the basis for Homework 3.)\n\n## Making it fast at scale\nComparing a query against every database image (and matching every patch against a flat vocabulary) doesn't scale to web-sized databases. See [[Scaling Image Retrieval]] for the standard speed-ups: the **inverted file index** (query by word instead of scanning every image), **TF-IDF** weighting, and the **vocabulary tree** (O(log N) word lookup) — including a full end-to-end worked example.\n\n## Related pages\n- [[k-means Clustering]]\n- [[Nearest-Neighbor Classification]]\n- [[Bayesian Classification (MAP & ML)]]\n- [[Scaling Image Retrieval]]\n- [[Feature Detection]]\n- [[Feature Matching]]\n- [[Recognition & Vision Tasks]]\n- [[Discriminative vs Generative Methods]]\n- [[Dense retrieval]]\n"},{"id":"Recognition & Vision Tasks","folder":"Computer Vision/Recognition & Retrieval","content":"**Summary**: Recognition maps pixels to concepts. This page covers the taxonomy of recognition tasks (all framed as classification), why recognition is hard (three kinds of variation), and why the field shifted from hand-written rules to data-driven machine learning.\n\n**Last updated**: 2026-05-29\n\n---\n\nRecognition is the **second half** of the course. The first half was about *models* (geometry, photometry, robust estimation) — the power of a few parameters. Recognition is about the power of **data**.\n\n## The four recognition questions\nEvery recognition problem is really a question we ask of an image:\n\n- **What is it?** → object & scene recognition\n- **Who is it?** → identity recognition\n- **Where is it?** → object detection\n- **What are they doing?** → activity recognition\n\n**All of these are classification problems**: choose one class from a list of possible candidates. Classification is the most basic recognition problem.\n\n## Task taxonomy\nUsing one street scene as a running example:\n\n- **Verification** — yes/no for a region: *\"is that a bus?\"*\n- **Detection** — find and localize instances: *\"where are the cars?\"* → pinpoint each\n- **Identification** — a specific instance/identity: *\"is that a picture of Mao?\"* / \"is this *this* person?\"\n- **Object categorization** — label every region with its semantics: sky, building, flag, banner, face, street lamp, bus, cars, wall\n- **Scene / context categorization** — the overall scene: outdoor, city, traffic; indoor vs. outdoor, urban vs. rural, sunny vs. rainy\n\n## Recognition in autonomous driving\nA single application needs many of these at once:\n\n- **Where is our car?** → [[Two-View Reconstruction|structure from motion]], visual SLAM\n- **Where are other agents?** → object detection, 3D localization\n- **Where are scene elements?** (road, sidewalk — things you can't box) → **semantic segmentation** (label every pixel)\n- **What is a safe path?** → behavior prediction & path planning (you care about not hitting someone *seconds in the future*)\n\nGeometry/motion is solved with 3D estimation ([[Two-View Reconstruction]]); the rest are recognition problems.\n\n## Why is recognition hard? Three kinds of variation\n**1. Imaging variations** — same object, different image:\n- **Viewpoint** — the object looks different from different angles\n- **Lighting** — intensities change, appearance shifts\n- **Occlusion / clutter** — the object is partly hidden\n- **Deformation** — articulated/soft objects (people, animals) bend and pose\n\n**2. Inter-class variation** — between categories. There are roughly **10,000–30,000** object categories worth recognizing. Few classes are easy (cat vs. bicycle), but as you add dogs, motorbikes, tricycles… the **confusion between class boundaries** grows.\n\n**3. Intra-class variation** — within one category. Try to *define a chair*: seat, back, legs… and someone builds a chair that breaks every rule (wheels instead of legs, no back). *Define a cat*: impossible to capture with rules. Definitions are insufficient for semantic categories.\n\n## Why machine learning (not rules)?\n- **Typical CS**: write a program that executes a fixed set of **rules** (a codified algorithm).\n- **Computer vision**: for most categories it is *very hard* to define such rules (you can't write the \"cat algorithm\").\n- **Machine learning**: the program is **developed from examples** instead of rules. We stop trying to define a cat and just collect many labeled examples — *cat* vs. *not cat*.\n- **Training data** = input–output pairs. In vision, inputs are **images**, outputs are **labels**.\n\n## Why it works now: data-driven vision\nRecognition hit an inflection point around **2012**, when three things came together:\n\n1. **Big labeled datasets** — the internet & social media produced massive image+caption data (a caption is a free label)\n2. **Deep learning** — methods able to ingest that data\n3. **GPU technology** — highly parallel compute to train large networks (cf. NVIDIA)\n\nImageNet top error rates fell from ~25% (2011) to below the **human level (~5%)** by 2015.\n\n## What's next\nThe course looks at [[Discriminative vs Generative Methods|discriminative vs. generative]] methods, then families of recognition methods — **retrieval** (see [[Image Retrieval (Bag of Words)]]), **classification**, and **deep learning / [[Neural Network|neural networks]]**.\n\n## Related pages\n- [[Computer Vision Overview]]\n- [[Discriminative vs Generative Methods]]\n- [[Image Retrieval (Bag of Words)]]\n- [[Neural Network]]\n- [[Feature Detection]]\n- [[Two-View Reconstruction]]\n- [[RANSAC]]\n- [[ML Overview]]\n"},{"id":"Scaling Image Retrieval","folder":"Computer Vision/Recognition & Retrieval","content":"**Summary**: Three techniques that make [[Image Retrieval (Bag of Words)|bag-of-words image retrieval]] fast at scale: the **inverted file index** (query by word instead of scanning every image), **TF-IDF** weighting (treat discriminative words as more important), and the **vocabulary tree** (search codewords in O(log N) instead of O(N)).\n\n**Last updated**: 2026-05-29\n\n---\n\nBasic [[Image Retrieval (Bag of Words)|bag-of-words retrieval]] compares a query against every database image — too slow for a web-scale database. These three ideas (the machinery behind early Google-style search) make it practical.\n## Inverted file index\nFinding a word by scanning a whole book line-by-line is wasteful; instead you use the **index** at the back, which maps each important word → the pages it appears on. Do the same for images:\n\n- Instead of storing *image → list of words*, store **word → list of images** the word appears in.\n- **Query:** extract the visual words in the query image, look each up in the index, gather the database images that share those words, and compare word counts to rank matches.\n\nThis avoids a linear scan over a huge image set — you jump straight to the images that share a word, and can layer hashing on top.\n## TF-IDF weighting\nSo far all visual words are treated as equally important. But when comparing documents, common words (*the*, *and*) shouldn't count as much as distinctive ones. **TF-IDF** assigns each word a weight:\n\n$$t_i = \\underbrace{\\frac{n_{id}}{n_d}}_{\\text{term frequency}} \\cdot \\underbrace{\\log\\frac{N}{n_i}}_{\\text{inverse doc. frequency}}$$\n\n- **Term frequency** $\\frac{n_{id}}{n_d}$ — occurrences of word $i$ in document $d$, over the total words in $d$. A word that appears a lot **in this document** is important to it.\n- **Inverse document frequency** $\\log\\frac{N}{n_i}$ — $N$ = total documents, $n_i$ = documents containing word $i$. **Downweights words common across the whole database** (they don't distinguish documents). Words in nearly every document → IDF ≈ 0.\n\nExample: in a database of Harry Potter books *and* pottery books, \"Harry\" is discriminative (appears a lot in one book, rare across the database) while \"Potter\" appears everywhere → \"Harry\" gets the higher weight. The same weighting applies to visual words. (TF-IDF was a key enabler of early Google search.)\n## Vocabulary tree\nEven with an index, you must match each query feature to the right visual word — and there may be millions of codewords. Stored as a flat **array**, that lookup is **O(N)**. Stored as a **tree**, it's **O(log N)**.\n\n- **Build:** apply clustering **hierarchically** — cluster the codewords into (say) 3 groups, sub-cluster each into 3, and so on, forming a tree (hierarchical k-means). Each codeword becomes a **leaf**; an image's features map to paths through the tree.\n- **Query:** descend the tree instead of scanning a flat vocabulary — O(log N) per lookup.\n\nFor databases with millions of codewords, O(log N) vs. O(N) is a large saving. (Nistér & Stewenius, *Scalable Recognition with a Vocabulary Tree*.)\n\n### Why not a plain hash table?\nTempting (O(1) lookup), but a hash set does **exact-match** lookup, and this is a **nearest-neighbor** problem. A query descriptor is a continuous vector that will essentially never equal a codeword exactly, and hashing scatters nearby vectors into different buckets — so the right bucket comes up empty. The tree instead **routes by proximity** (descend toward the nearest center at each level), solving nearest-neighbor deterministically in O(log N). Hashing *can* be used, but only the **locality-sensitive** kind (LSH), where nearby vectors collide on purpose — that's the probabilistic alternative to the deterministic tree.\n\n## Worked example: one query, end to end\nThe visual words **are the [[k-means Clustering|k-means]] cluster centers** — \"cluster center = visual word = codeword = dictionary entry\" are all the same thing. The whole method hangs on that. Here's a tiny end-to-end run (2-D descriptors so the arithmetic is visible; real ones are ~128-D).\n\n### The dictionary: 4 visual words\nk-means on all training patches (with k = 4) produced 4 cluster centers — these *are* the words:\n\n| word | vector (cluster center) | roughly |\n|---|---|---|\n| W1 | (1,1) | sky |\n| W2 | (9,2) | building corner |\n| W3 | (5,9) | leaves |\n| W4 | (8,5) | window |\n\nSo **k (in k-means) = the vocabulary size**. Here 4; in practice thousands–millions.\n\n### Offline: build the database (once)\nThree database images, each already turned into a **bag of words** (count of patches per word):\n\n| Image | W1 | W2 | W3 | W4 |\n|---|---|---|---|---|\n| Image 1 (building) | 1 | 3 | 0 | 2 |\n| Image 2 (building) | 0 | 2 | 0 | 1 |\n| Image 3 (forest) | 2 | 0 | 4 | 0 |\n\nThen the **inverted index** — for each word, which images contain it:\n\n```\nW1 → {Image1, Image3}\nW2 → {Image1, Image2}\nW3 → {Image3}\nW4 → {Image1, Image2}\n```\n\n### Online: a query image arrives\n**1. Patches → vectors.** Detect 3 patches with descriptors: a = (8,3), b = (8.5,4.5), c = (9,2).\n\n**2. Each vector → its 1 nearest word (the vocabulary-tree job).** For patch a = (8,3), squared distances to the 4 centers:\n\n| to W1 (1,1) | to W2 (9,2) | to W3 (5,9) | to W4 (8,5) |\n|---|---|---|---|\n| 49+4 = 53 | 1+1 = **2** ✓ | 9+36 = 45 | 0+4 = 4 |\n\n→ patch a is **W2**. Likewise b → **W4** (distance 0.5) and c → **W2** (sits exactly on it). Each patch gets **exactly one** word — the tree just makes finding that one nearest center fast when there are millions.\n\n**3. Count the words → bag-of-words histogram.** *(This is the step that trips people up — it's just a tally.)* The three patches produced the list **{W2, W4, W2}**. Tally per dictionary word:\n\n| word | which patches | count |\n|---|---|---|\n| W1 | — | 0 |\n| W2 | a, c | 2 |\n| W3 | — | 0 |\n| W4 | b | 1 |\n\n→ query histogram = **[0, 2, 0, 1]** (4 slots because the dictionary has 4 words).\n\n**4. Words → candidate images (the inverted-index job).** The query contains W2 and W4. Look them up:\n- W2 → {Image1, Image2}\n- W4 → {Image1, Image2}\n\nCandidates = **{Image1, Image2}**. **Image3 never appears** — it shares no words, so we never even score it. The index is a **filter** (\"which images are worth looking at?\"), not a ranking.\n\n**5. Score the candidates → rank → return.** Cosine similarity between the query histogram and each candidate:\n- query [0,2,0,1] vs Image1 [1,3,0,2] ≈ **0.96**\n- query [0,2,0,1] vs Image2 [0,2,0,1] = **1.0** ← identical counts → best match\n\n→ **Return Image 2.** Ranking and any \"top-k results\" cutoff happen *here*, in scoring — not in the index.\n\n### Two roles, don't merge them\n- **Vocabulary tree** = *vector → 1 word* (\"what word is this patch?\")\n- **Inverted index** = *words → candidate images* (\"which images use these words?\", a filter)\n- **Scoring** = rank the candidates → return the top match(es)\n\n### Three different \"k\"s (a common mix-up)\n\n| \"k\" | meaning | where |\n|---|---|---|\n| k in **k-means** | number of clusters = **vocabulary size** | building the words |\n| k in **kNN** | number of neighbors that vote | [[Nearest-Neighbor Classification\\|classification]] (a different method) |\n| \"top-k results\" | how many images to return | the final ranking step |\n\n## Related pages\n- [[Image Retrieval (Bag of Words)]]\n- [[k-means Clustering]]\n- [[Feature Matching]]\n- [[Dense retrieval]]\n"},{"id":"Dense retrieval","folder":"Information Retrieval","content":"**Summary**: Neural retrieval with bi-encoders, cross-encoders, and ColBERT — designs, contrastive training, and approximate-nearest-neighbor search at scale.\n\n**Last updated**: 2026-05-29\n\n---\n\nThere are multiple ways to design and implement dense retrieval. You can use different ways to compare embedding, different embedding strategies, and so on. Making the choice based on the priorities are most critical here.\n![[expressiveness_efficiency_spectrum.svg|697]]\n# Encoder Overview\n**Bi-encoder**: handle query and document separately\n**Cross-encoder**: embed query and doc together\n**ColBERT**: token-level comparison\n# Bi-encoder\n**Fast** retrieval, **Scales** to millions of documents, works well with **contrastive learning**\n## Design\n- encode query x and document d independently\n- map each to a single-vector representation in $\\mathbb{R}^k$ \n- compute their similarity and get the result \n## Training\nContrastive loss over\n- One positive passage\n- Hard negatives (BM25 top - k: query with the same keywords)\n- in-batch negative (training multiple query at the same time, so positive document for one query can be negative for others)\n- **only aiming on getting the right relative rankings**\n\nTraining goal: minimize the loss $\\mathcal{L}$ (equivalently, maximize the log-probability of the positive pair)\n$$\\mathcal{L} = -\\log \\frac{\\exp(\\textbf{sim}(q, d^+))}{\\exp(\\textbf{sim}(q, d^+)) + \\sum_{j=1}^{n} \\exp(\\textbf{sim}(q, d_j^-))}$$\n\n$\\exp(\\textbf{sim}(q, d^+))$: the similarity score of positive label \n- **Maximize Agreement**: increase this so that query is close together with the embedding space of the positive example\n\n$\\sum_{j=1}^{n} \\exp(\\textbf{sim}(q, d_j^-))$: the similarity score of negative label\n- **Minimize Agreement**: decrease this so query is away from the embedding space of negative examples\n## Search Scale\nModern approach using Approximate Nearest Neighbor (ANN) search. For example, the FAISS (Facebook AI Similarity Search) with vector indexing. **Fast retrieval with small accuracy loss**\n## Limitation \n- No query-document interaction during encoding\n- semantic lost when compressing all the token into a single vector\n# Cross-Encoder\nexpressive encoder that can understand the semantic relationships between query tokens\n## Design\n- encode query x and document d together\n- getting a single score\n## Training\nsame as [[#Training]] process in Bi-encoder with a different scoring function. that is $s(q, d) = f([q; d])$ \n## Limitation\n- computationally expensive\n# ColBERT\nTrying to take the advantage of both [[#Bi-encoder]] and [[#Cross-Encoder]] to keep both pre-computation and allow fine-grained interactions\n## Design\n- getting per word token for both query x and document d\n- for each query-document pair, find the maximum similarity between each query token and all document tokens, then sum those maximums to get the final relevance score\n- scoring function $$\\text{score}(q, d) = \\sum_{i \\in q} \\max_{j \\in d} \\langle q_i, d_j \\rangle$$\n## Training\nsame as [[#Training]] process in Bi-encoder with a different scoring function which is MaxSim. \n\nTwo approaches on ranking documents\n- Two-Stage Retrieval Pipeline\n\t- getting top-K documents using a fast model and re-rank with ColBERT\n\t- save computational cost\n- Direct token-level retrieval\n\t- for each query word token find n nearest token\n\t- finding the documents with highest frequency of appearing across all the query word token\n\n## Related pages\n- [[Retrieval-Augmented Generation (RAG)]]\n- [[Image Retrieval (Bag of Words)]]\n"},{"id":"Retrieval-Augmented Generation (RAG)","folder":"Information Retrieval","content":"**Summary**: Grounding a language model in retrieved external documents — relevance scoring, retrieval timing, and handling under-use of sources.\n\n**Last updated**: 2026-05-29\n\n---\n\ntechnique that lets language model ground its answers in external knowledge rather than relying on internal knowledge\n\nRAG's automated context selection mechanism making it a automatic prompt engineering\n![[rag_pipeline.svg|631]]\n\nmathematically\n$$p(y \\mid x) = \\sum_{d} p(y \\mid x, d) \\, p(d \\mid x)$$\nto maximize $p(y \\mid x)$, getting most relevant document $d$ and get the most relevant text for that document as well.\n# Scoring Document relevance \nHow do we measure $p(d \\mid x)$. In different approach, we have different ways of constructing the following function $f(input, memory)-> score$ \n\n**Sparse retrieval**: literal token overlap\n**[[Dense retrieval]]**: (modern approach) (based on semantic similarity) embed both the query and documents into the same vector space, then measure similarity \n# Retrieval Timing\n\n**Retrieve Once** (at the start)\n- Most common approach\n- Limiting for long-form generation\n\n**Retrieve Periodically**\n- Every k tokens\n\n**Retrieve Adaptively**\nModel learn when to retrieve\n(ex. toolformer)\n- teach LLM to make external call during text generation\n- getting training data by running candidate few-shot prompting call. and keep the effective ones as the training data\n- fine tune model based on these positive result.\n# Handling underutilization of retrieved source\nretrieving is easy, using and reasoning the retrieved info is hard. Sometimes, pre-trained model learned to related on the pre-trained knowledge rather than the provided source which cause inaccurate info.\n## Solution 1 - counterfactual training\nfine-tuning the model with retrieval and intentionally use the training data that only has answer from the retrieval document. so that we force the model to learn to read from the retrieval document.\n## Solution 2 - Training with retrieval\nImproving language models by retrieving from trillions of tokens\n\n## Related pages\n- [[Dense retrieval]]\n"},{"id":"Operating Systems (Interview Cheat Sheet)","folder":"Interview Cheat Sheets","content":"**Summary**: OS interview concepts — user vs. kernel mode, processes/threads, IPC, scheduling, synchronization, and memory management.\n\n**Last updated**: 2026-04-20\n\n---\n\n> Source: [All You Should Know About Operating Systems in Technical Interviews](https://towardsdatascience.com/all-you-should-know-about-operating-systems-in-technical-interviews-4dcc55210fea/)\n## What is an Operating System?\n- Interface between users and computer hardware\n- Program managing hardware and software resources of the computer\n- Structured by the kernel (bridge between application and hardware), which is responsible for managing things such as process, internal memory, file, and network\n\nMost applications stay in **user mode** and they are restricted from accessing hardware and other processes which are freely accessible in the **kernel mode**\n![[user_kernel_mode.svg|697]]\n## Processes & Threads\n### Process vs. Thread\n**Process**\n- Separate memory space (so one cannot corrupt another process)\n- Increasing execution time when switching\n\n**Thread**\n- A unit of execution within a process\n- Fast switching\n- Single point of failure\n### Lifecycle\n- **New**: Process created\n- **Ready**: Ready to go\n- **Run**: Running\n- **Wait**: Waiting for the required resources to be available\n- **Complete**: The execution has been complete\n- **Suspended Ready**: The process is ready to run but got moved to Disk due to Full RAM\n- **Suspended Block**: The process is waiting for resource but got moved to Disk due to Full RAM. Will move to Susp. Ready when the resources is ready\n![[process_lifecycle.svg|697]]\n### Process Communications\n1. **Pipe**: Output of a process becomes the input of another process\n2. **Named pipe**: Similar to pipe but handles process of different origin\n3. **Message queueing**: It's like a todo list\n4. **Shared memory**: Shared data and see the real-time update all at once\n5. **Semaphore**: Premium of shared memory where it used to avoid race condition\n6. **Socket**: Client/server, server/server communication\n### Thread Synchronization\n- **Mutex**: Mutual exclusion, which only allows one thread accesses the shared resources at a time\n- **Semaphore**: Larger than 1 and allows multiple threads\n- **Event**: Remains thread synchronization by notification\n### CPU Schedule Process\n1. **First Come First Serve**\n2. **Shortest Job First**\n3. **Shortest Remaining Time First**\n4. **Round Robin**: Each process is allocated to a given time\n5. **Priority Based**: Based on Priority Score\n6. **Multilevel**: Multiple priority queue\n7. **Multilevel Queue Feedback**: Process can change in these multi priority queue\n### Potential Bugs\n- **Context switching**: Switch from one running process to another process\n- **Race Condition**: When different processes or different threads modified share resources causing a problem\n## Memory Management\n### Memory Model\n- **Primary memory (internal)**: CPU registers, cache memory and main memory\n- **Secondary memory (external)**: Different types of disk\n### OS Memory Allocation\n- **Partitioned allocation**: Memory by block\n- **Paged memory management**: Memory by page frames (not continuous)\n- **Segmented memory management**: Divide memory by segments\n- **Segmentation with paging**: Divide things in logic chunks, then separates each segment into several page frames\n\n## Related pages\n- [[Technical Interview Checklist]]\n"},{"id":"Technical Interview Checklist","folder":"Interview Cheat Sheets","content":"**Summary**: A personal checklist for coding interviews — the workflow from problem understanding through planning, implementation, and explanation.\n\n**Last updated**: 2026-04-25\n\n---\n\nA mental model, I personal has when doing a problem solving (classic coding) interview\n# General Workflow\n- **Beginning**: General intro and conversation\n- **Problem understanding**: understand problem (5 mins)\n- **Solution Planning**: plan out ur approach (10 mins)\n- **Solution Implementation**: ur plan to actual code (15 mins)\n- **Explanation**: explain and clarify your approach with interviewer (5 mins)\n# Beginning\n- [ ] conversation to **set the tone** and **understand interviewees' style**\n- [ ] inform your problem solving style to interviewer (I plan and then move onto solving)\n- [ ] (optional): learn more about the interviewee\n# Problem understanding\n- [ ] expected input and output of the problem\n\t- [ ] Data type\n\t- [ ] Data constrain\n- [ ] the expected time and space complexity\n- [ ] walk through the problem with a few test cases\n# Problem planning\n- [ ] using pseudo code and general terms (reference to [[Algorithm CheatSheet (TODO)|here]])\n- [ ] discussing the corresponding time complexity and space complexity\n- [ ] discussing the edge case\n\t- [ ] empty input\n\t- [ ] duplication handling\n\t- [ ] null root (graph problem)\n\t- [ ] termination condition (recursion)\n# Solution Implementation\n- [ ] use common variable (`res`, `l`, `r`)\n- [ ] use implemented func (reference to [here](https://neetcode.io/courses/lessons/python-for-coding-interviews))\n- [ ] use helper func if you can\n# Explanation\n- [ ] walk through your approach\n- [ ] explain the time complexity and space complexity again\n- [ ] clean up the code if possible\n\n## Related pages\n- [[Operating Systems (Interview Cheat Sheet)]]\n"},{"id":"Bayesian Classification (MAP & ML)","folder":"Machine Learning","content":"**Summary**: A **generative** classifier. We want the posterior $P(\\text{class}\\mid\\text{data})$, but what we can measure from labeled data is the likelihood $P(\\text{data}\\mid\\text{class})$ — a histogram. Bayes' rule converts one to the other; we decide with **MAP** (using a prior) or **ML** (assuming a uniform prior).\n\n**Last updated**: 2026-05-29\n\n---\n\n## Where this fits\nThis is the worked, concrete instance of the **generative** side of [[Discriminative vs Generative Methods]]. Recall the Bayes decomposition: the posterior we want for classification factors into a likelihood and a prior. Bayesian classification *estimates the likelihood from data* and applies Bayes' rule to recover the posterior.\n\n## The skin-classifier example\nGoal: given a pixel's color $R$, decide **skin** vs. **not skin**. This is not deterministic (skin spans many colors), so we model it probabilistically.\n\n- **What we want** is the **posterior** $P(\\text{skin}\\mid R)$ — given the color, how likely is skin? We classify a pixel as skin where $P(\\text{skin}\\mid R) > P(\\lnot\\text{skin}\\mid R)$.\n- **What we can measure** is the **likelihood** $P(R\\mid\\text{skin})$ — among skin pixels, how often does color $R$ occur. It's literally a normalized histogram:\n$$P(R\\mid\\text{skin}) = \\frac{\\#\\,\\text{skin pixels with color } R}{\\#\\,\\text{skin pixels}}$$\n\nThese are not the same thing — so how do we get the posterior we want from the likelihood we have?\n\n## Bayes' rule bridges them\n$$P(\\text{skin}\\mid R) = \\frac{\\overbrace{P(R\\mid\\text{skin})}^{\\text{likelihood (measured)}}\\;\\overbrace{P(\\text{skin})}^{\\text{prior}}}{\\underbrace{P(R)}_{\\text{normalization}}}$$\n\n- **Likelihood** $P(R\\mid\\text{skin})$ — the measured histogram.\n- **Prior** $P(\\text{skin})$ — our belief about how common skin is, from **domain knowledge** (e.g. faces sit near the center of portrait photos) or from **class counts** in a fairly collected dataset.\n- **Normalization** $P(R) = P(R\\mid\\text{skin})P(\\text{skin}) + P(R\\mid\\lnot\\text{skin})P(\\lnot\\text{skin})$ — the **same** for both classes, so for classification we can **ignore it and just compare numerators**.\n\n## Two decision rules\n- **MAP — maximum a posteriori.** If we **know the prior**, multiply likelihood × prior to get the (unnormalized) posterior for each class, then pick the larger. Decide skin where $P(\\text{skin}\\mid R) > P(\\lnot\\text{skin}\\mid R)$ — e.g. the color band $R_1 < R \\le R_2$ where the skin posterior curve sits above the not-skin one.\n- **ML — maximum likelihood.** If we **don't know the prior**, the best assumption is a **uniform prior** (0.5 / 0.5 for two classes; $1/n$ for *n* classes). Then the prior is identical for both classes, so comparing posteriors **reduces to comparing likelihoods** directly.\n\nThis is the precise meaning of the \"what are you maximizing?\" distinction from [[Discriminative vs Generative Methods]]: **generative training maximizes likelihood** — ML here literally compares/maximizes likelihoods, and MAP maximizes the (unnormalized) posterior.\n\n## Why it connects back\n- **Generative recipe:** model the data (estimate $P(R\\mid\\text{class})$), then use Bayes to classify — exactly \"generative models the likelihood and prior.\"\n- **Histograms appear twice:** as the [[Image Retrieval (Bag of Words)|bag-of-words]] image representation *and* as the likelihood $P(R\\mid\\text{skin})$ here. Both are \"a histogram is a vector representation of a distribution.\"\n- Despite its simplicity, MAP/ML skin detection works reasonably well in practice.\n\n## Related pages\n- [[Discriminative vs Generative Methods]]\n- [[Nearest-Neighbor Classification]]\n- [[Image Retrieval (Bag of Words)]]\n- [[Recognition & Vision Tasks]]\n"},{"id":"Convolutional Neural Network (CNN)","folder":"Machine Learning","content":"**Summary**: A CNN is a neural network built around the convolution operation, designed to exploit the spatial structure of images. Instead of hand-designing filters (Sobel, etc.), a CNN *learns* its filters from data; each layer convolves learned kernels over its input (local connectivity + weight sharing) to produce feature maps, and stacking conv + nonlinearity builds hierarchical features.\n\n**Last updated**: 2026-05-29\n\n---\n\nA CNN is a neural network architecture built around the **convolution** operation, designed to exploit the spatial structure of grid-like data such as images (and audio spectrograms, geophysical fields, …). It's the dominant way [[Neural Network|neural networks]] are applied to images, and it builds directly on the convolution we saw for [[Feature Detection|filtering]].\n\n## Why learn the filters?\nClassic computer vision **hand-crafts** filters — Sobel (edges), Gaussian blur, Gabor, morphological filters, etc. A Sobel kernel like $\\begin{bmatrix}-1&0&1\\\\-2&0&2\\\\-1&0&1\\end{bmatrix}$ responds to vertical edges. Two problems:\n- Is a hand-designed filter **optimal** for *your* task? No guarantee.\n- You'd have to design a different filter for every problem.\n\nThe CNN idea: don't choose filters a priori — **let the data and the optimization learn the optimal filters**. The kernel entries $\\theta_1,\\dots,\\theta_9$ become **learnable weights**, trained by [[Neural Network#Training a neural network|gradient descent]] to map images to their labels as well as possible.\n\n## Convolution recap\nA **convolution is a weighted moving sum**: slide a kernel (filter) across the input; at each location take the **dot product** of the kernel with the overlapping patch; record the value. The result is a **feature map** (a.k.a. feature activation map). Just as a Sobel kernel produces an edge map, a learned kernel produces a learned feature map.\n\n## Why convolution fits images\n- **Local connectivity** — neighboring pixels are correlated; meaning comes from local structure, not isolated pixels. A kernel acts on a local $k{\\times}k$ region, so it directly exploits this.\n- **Spatial structure** — convolution is a spatial operation, so spatial relationships are preserved (cat-like features end up next to dog-like features).\n- **Channels (depth)** — grayscale = 1 channel, RGB = 3, hyperspectral = k. The spatial axes (W, H) carry *position*; the depth axis carries *channel/color* — they mean different things.\n\n## Fully-connected vs. convolutional layer\n- **Fully connected (FC):** every unit connects to *every* unit in the previous layer (dense). Spatial information is thrown away (recall MNIST flattening 28×28 into 784 inputs), and the parameter count **scales with the input size**.\n- **Convolutional:** each unit connects to only a **local $k{\\times}k$ region** — the kernel. The $k^2$ kernel values are the learnable weights, and the **same kernel slides across the whole input** → one feature map. Two wins: **local connectivity** (respects image structure) and **weight sharing** (one filter reused everywhere).\n\n## From image to feature volume\n- One $k{\\times}k$ filter on a $W{\\times}H$ image → one **$W{\\times}H$ 2D feature map**.\n- Apply **C different filters** → C feature maps → stack into a **$W{\\times}H{\\times}C$ volume**. So the first conv layer turns a 2D image into a **3D volume**: spatial dims = input size, depth = number of filters.\n- **Convolution on a volume:** the input is now $W{\\times}H{\\times}C$, so each filter is **3D** — $k'{\\times}k'{\\times}C$, **local in space but full in depth** (it spans all C channels). Slide it spatially → one 2D feature map; $C'$ such filters → a $W{\\times}H{\\times}C'$ volume. Repeat layer by layer.\n- A **nonlinearity** (ReLU / max) sits between conv layers — the same $W\\mathbf{x}\\to\\max(0,\\cdot)$ pattern as a plain [[Neural Network]] — which is what builds higher and higher abstraction.\n\n## Counting parameters\n- One filter over C channels: $k^2 \\cdot C$ weights.\n- A conv layer of $C'$ filters: $k^2 \\cdot C \\cdot C'$ weights.\n- Example: a $7{\\times}7$ filter on RGB ($C=3$) → $7\\cdot7\\cdot3 = 147$ parameters; 5 such filters → $147\\cdot5 = 735$.\n\nThe key point: because of **weight sharing**, the count depends only on **filter size × number of filters** — **not** on the input image size, unlike an FC layer.\n\n## What weight sharing means\nPhysically: we expect a feature (say a \"chair detector\") to appear *anywhere* in the image, so the **same filter should fire wherever the pattern occurs** — there's no reason to use a different filter for a chair in the left corner vs. the right. One shared kernel per feature is therefore enough, and it keeps the parameter count low.\n\n**Exception — registered/aligned inputs.** When images are pre-aligned, location-specific filters can help. Face-recognition kiosks first **warp** the face so eyes/nose/mouth land at canonical locations; then **DeepFace** (Facebook AI) — the first face recognition to beat human accuracy — used location-specialized CNN features. Modern networks are powerful enough that plain weight sharing works without this trick.\n\n## Convolution is differentiable\nTraining needs gradients (see [[Neural Network#Training a neural network|training]]), so every layer must be differentiable. A convolution is just a **dot product** of the filter with the overlapping patch — a linear operation — so it's trivially differentiable (the derivative w.r.t. a filter weight is the corresponding input value).\n\n## Pooling\nA **pooling** layer aggregates a local region of a feature map into a single value. **2×2 max-pooling with stride 2**: slide a non-overlapping 2×2 window over the map and keep the **max** of each window → an $n{\\times}n$ map becomes $\\tfrac{n}{2}{\\times}\\tfrac{n}{2}$.\n\n- **No learnable parameters** — it's a fixed, deterministic operation (you only choose the window size *k* and stride).\n- **Applied per feature map** (each channel independently) — unlike convolution, which spans the whole depth.\n- **Differentiable** — the gradient routes only to the location that won the max (gradient 1 there, 0 elsewhere) — the same \"max gate\" pattern from [[Neural Network#Gate patterns|backprop]].\n\nThree reasons to pool, least → most important:\n1. **Invariance / keep the most informative values** in noisy data.\n2. **Less computation & memory** — smaller maps downstream.\n3. **The real reason: a bigger receptive field, cheaply.** Pooling widens each unit's view of the input **without adding parameters** (see below).\n\n## Receptive field\nThe **receptive field** of a unit is the region of the *input image* it \"sees\" — its footprint. A unit in the first conv layer sees only a small $k{\\times}k$ patch; a unit one layer deeper aggregates the receptive fields of all the units feeding it, so **deeper units see broader regions**.\n\nWhy this matters: a 3×3 patch of white fur can't tell a white cat from a white dog — you need a **global, holistic view**. So lower layers learn local features (edges, corners) and deeper layers, with wider receptive fields, learn textures → object parts → whole objects. **The magic word for deep networks is *context*** — deep layers must see enough of the image to reason about it.\n\nGrowing the receptive field by stacking conv layers costs more parameters each layer. **Pooling is the shortcut**: it collapses a region into one unit, instantly widening the receptive field with *zero* new parameters. (But don't pool *everything* at once — you'd lose information and skip the learning; the art is balancing context, computation, and enough parameters to actually learn.)\n\n## 1×1 convolution\nA **1×1 convolution** has spatial size 1 but full channel depth — so it's a dot product across channels at each pixel. Its use: **change the number of channels** while keeping spatial size, in a *learnable* way. E.g. a 56×56×64 map → apply 32 different 1×1 filters → 56×56×**32**. Handy for **multimodal fusion** — line up the channel dimensions of, say, an audio stream (64) and a video stream (32) before combining them.\n\n## The classification head: flatten → fully connected → softmax\nThe conv/ReLU/pool stack outputs feature maps; a classifier needs one number per class. Two final steps:\n\n1. **Flatten + fully-connected layers.** Once pooling has shrunk the maps (e.g. 4×4 × 100 channels = 1,600 values), **flatten** them and add a couple of **fully-connected layers** ending in output nodes = number of classes. Unlike conv units (local), every FC unit sees the **whole image** — exactly what you need for a holistic class decision.\n2. **Softmax.** ReLU outputs are unbounded $[0,\\infty)$, but classification wants a **peaky probability distribution** (the ground truth is one-hot — a delta function). Softmax turns the raw scores $z$ into probabilities:\n$$\\text{softmax}(z)_i = \\frac{e^{z_i}}{\\sum_j e^{z_j}}$$\nDividing by the sum makes it sum to 1 (a probability); exponentiating **exaggerates differences**, making the output peaky. It's a **differentiable approximation of max** — $e^{100}\\gg e^{98}$, so the largest logit dominates, but smoothly enough to backprop through.\n\n## What's next\nFull CNN architectures (and the precise receptive-field arithmetic — each extra 3×3 stride-1 conv grows it by 2, pooling/stride multiply it, dilation grows it without adding parameters) — later lectures. CNN features also **transfer** extremely well across tasks → see [[Transfer Learning]].\n\n## Related pages\n- [[Neural Network]]\n- [[Transfer Learning]]\n- [[Generalization & Model Validation]]\n- [[Feature Detection]]\n- [[ML Architecture Families]]\n- [[Recognition & Vision Tasks]]\n"},{"id":"Generalization & Model Validation","folder":"Machine Learning","content":"**Summary**: What we want from a model isn't accuracy on data we've seen — it's **generalization** to unseen data. To get it (and to choose hyperparameters honestly) we split data into train / validation / test, tune on validation, and never touch test until the end.\n\n**Last updated**: 2026-05-29\n\n---\n\nThe real goal of any machine-learning model — a [[Neural Network]] included — is **generalization**: performing well on examples it has **never seen**, not just on the data it was trained or tuned on.\n\n## The three-way split\nDivide the dataset into three disjoint parts:\n\n- **Training set** — used to *learn the weights* (run [[Neural Network#Training a neural network|gradient descent]] on it).\n- **Validation set** — used to *choose hyperparameters* (learning rate, architecture, how much to fine-tune in [[Transfer Learning]], etc.). Train with one hyperparameter setting, measure on validation, repeat, keep the best. This is **cross-validation**.\n- **Test set** — used **once**, at the very end, to estimate true generalization. It stands in for \"unseen data.\"\n\n## Why not just tune on the test set?\nEven if you *have* test labels, you must not pick hyperparameters by test performance. If you do, you've effectively **fit the test set** — your numbers look great, but you've lost the one honest estimate of how the model does on genuinely unseen data.\n\n> **The radiologist analogy.** Train a network on a hospital's X-rays, tune until it scores well on the test X-rays — great accuracy. But a **new patient** walks in whose scans the model has never seen. Will it still work? That question — performance on the truly unseen — is *generalization*, and you can only estimate it if the test set was never used to make choices.\n\nSo: **train on train, tune on validation, report on test (once).** Test performance is a measure not just of accuracy but of **generalization**.\n\n## Why generalization is hard → regularization\nA model with enough parameters can memorize the training data (fit it perfectly) yet fail on new data — **overfitting**. Ensuring generalization is exactly what **overfitting and regularization** address.\n\n*(Regularization techniques — covered in the next lecture — will be added here.)*\n\n## Related pages\n- [[Neural Network]]\n- [[Transfer Learning]]\n- [[Convolutional Neural Network (CNN)]]\n- [[ML Overview]]\n"},{"id":"ML Architecture Families","folder":"Machine Learning","content":"**Summary**: Broad families of ML models — linear, tree-based, instance-based, kernel, probabilistic, neural — with their mechanisms, assumptions, and use cases.\n\n**Last updated**: 2026-05-29\n\n---\n\n# Broad Categories\n- [[#Linear Models|Linear models]]: creating a straight-line (or hyperplane) using the features to predict the output\n- [[#Tree-based Models|Tree-based models]]: recursively splitting data on feature thresholds (like a tree)\n- [[#Instance-based Models|Instance-based]]: find the most similar existing case\n- [[#Kernel Methods|Kernel methods]]: mapping data to another dimensional space to find the optimal boundary between classes\n- [[#Probabilistic Models|Probabilistic models]]: making prediction based on likelihood\n- [[#Neural Networks|Neural networks]]: making inference using stacked neural layers\n# Linear Models\n**Core mechanism** -- Predict the output with a weighted sum of input features plus a bias term. Training the model to find the right weight that minimize the prediction error\n## Key Assumptions\n- Linear relationship between features and target\n- features are independent of each other\n## Classic Algorithms\n- Linear regression\n- logistic regression\n- ridge regression\n- lasso regression\n## Common Characteristic\n- Fast to train\n- scale well to large datasets\n- interpretable features\n## Use Case\n- price or score prediction\n- explainability matters as much as accuracy\n# Tree-based Models\n**Core mechanism** -- split the data based on feature thresholds with leave node holds a prediction\n## Key Assumptions\n- features used to split can effectively separate the data\n## Classic Algorithms\n- Decision trees\n- Random forests\n- XGBoost, LightGBM, CatBoost\n## Common Characteristic\n- can handle non-linear relationships \n- can handle messy and noise data\n- good interpretability (trace the path of each tree)\n- overfitting easily\n- hard to handle high-dimensional sparse data\n## Use Case\n- customer churn prediction\n- Fraud detection\n# Instance-based Models\nTODO...\n\n# Kernel Methods\n**Core mechanism** -- mapping data to higher-dimensional space via a **kernel function** (the \"kernel trick\"), creating non-linear decision boundary which makes different classes linearly separable, then find the maximum-margin boundary between them\n## Key Assumptions\n- valid kernel exist for the problem\n- sensitive to feature scaling (TODO, need more explanation on this part)\n## Classic Algorithms\n- Support Vector Machines (SVM)\n- Support Vector Regression (SVR)\n- Kernel Ridge Regression\n- Kernel PCA\n## Common Characteristic\n- effective in high-dimensional spaces\n- Memory-efficient\n- Low interpretability\n## Use Case\n- Text classification\n- Gene expression and cancer classification\n- Protein structure and sequence analysis\n# Probabilistic Models\n**Core mechanism** -- making prediction by finding the most likely outcome given the observed evidence (Bayes' theorem)\n## Key Assumptions\n- data follows probability distribution\n- more assumptions very depending on the algorithms\n## Specific Algorithms\n- Naive Bayes\n- Hidden Markov Models\n- Gaussian Mixture Models\n- Bayesian networks\n## Common Characteristic\n- very sensitive to the breaks of assumptions\n- high interpretability\n## Use Case\n- ...\n# Neural Networks\n**Core mechanism** -- stack layers of neurons and non-linear activation functions to make prediction. And train the model via backpropagation. See [[Neural Network]] for the foundations (perceptron → MLP, why the nonlinearity matters, training by gradient descent).\n## Key Assumptions\n- scenario dependent \n## Specific Algorithms\n- [[Convolutional Neural Network (CNN)]]\n- RNN\n- LSTM\n- Transformers\n- diffusion\n- auto-encoder \n## Common Characteristic\n- high data demand\n- significant computing power\n- low interpretability\n## Use Case\n- Large Language Model\n- Computer Vision\n- Speech to text\n"},{"id":"ML overview","folder":"Machine Learning","content":"**Summary**: What machine learning is, key terms, the three types (supervised / unsupervised / reinforcement), and the end-to-end ML pipeline.\n\n**Last updated**: 2026-04-20\n\n---\n\n**Source:** [Types of Machine Learning – GeeksforGeeks](https://www.geeksforgeeks.org/machine-learning/types-of-machine-learning/)\n# What is Machine Learning?\nMachine Learning is teaching algorithm and system to learn patterns, make decisions and completing repetitive task for human. The training process usually require a large scale of data in different form.\n# Terms\n- Features: info used by algorithm to make prediction\n- Labels: the ground truth answer\n- Training: teaching model with the answer\n- Inferencing: machine predicting the future\n# Types of Machine Learning\n![[types_of_machine_learning_tree_signed.svg|697]]\n## Supervised Learning\ntrained on \"Labeled Dataset\"\n- **Classification**: predict categorical outputs\n- **Regression**: predict continuous values\n## Unsupervised Learning\ndeal with unlabeled data, meaning there are no predefined outputs\n- **Clustering**: grouping data points into clusters based on their similarity\n- **Dimensionality Reduction Techniques**: feature reduction\n- **Association Rule Learning**: relationships identification\n## Reinforcement Learning\nagent that makes a sequence of decisions through trial and error and actively interacting with an environment\n# The ML Pipeline\n1. Defining the scope of the problem\n2. Data Collection\n3. Data Processing (raw data -> clean data)\n4. Feature Engineering: finding useful info to make prediction\n5. Model Selection: identify the right [[ML Architecture Families|architecture]]\n6. Training: train model\n7. Evaluation: using direct and clear metrics to evaluate model (such as accuracy, precision/recall, F1 for classification, MSE/RMSE) — and on the right data split, to measure [[Generalization & Model Validation|generalization]] rather than memorization\n8. Deployment and monitoring\n\n## Related pages\n- [[Generalization & Model Validation]]\n- [[ML Architecture Families]]\n- [[Neural Network]]"},{"id":"Nearest-Neighbor Classification","folder":"Machine Learning","content":"**Summary**: Classify a new point by the label(s) of its closest training point(s). Nearest-neighbor (NN) uses the single closest; **k-nearest-neighbors (kNN)** takes a majority vote among the *k* closest. Simple and flexible, but expensive in time and memory.\n\n**Last updated**: 2026-05-29\n\n---\n\nOnce every image (or patch) is a **vector** — e.g. a [[Image Retrieval (Bag of Words)|bag-of-words histogram]] — classification is just retrieval with labels attached.\n\n## Nearest neighbor (NN)\nMap a labeled training set into the feature space. For a **novel test point**, find the **closest** training point and assign **its label**. The implicit decision boundary is the Voronoi diagram of the training points.\n\n*Problem:* a test point near a class boundary can be decided by a single, possibly noisy, neighbor.\n\n## k-nearest neighbors (kNN)\nGeneralize: find the **k closest** training points and let their labels **vote**; assign the **majority** label. Larger *k* is more robust (the \"ask many people, not one\" principle) and dampens the effect of outliers.\n\n- Typical *k* for kNN classification is **small** (5, 7, 11).\n- **Caveat:** this *k* is unrelated to the *k* in [[k-means Clustering|k-means]] (which is often in the thousands). The field just reuses the letter.\n\n## Advantages\n- **Simple** to implement\n- **Flexible** — works with any feature representation and any distance/similarity measure\n- **Strong baseline** — does well in practice with enough representative data\n- **Great sanity check:** to test whether a learned feature space is meaningful, run kNN and inspect the neighbors — if they look similar to the query, the features captured something real. Often the *first line of attack* on an unknown learning problem.\n\n## Limitations\n- **Compute:** every query must compute distances to *all* training points and sort them — cost grows with training-set size.\n- **Memory:** you must keep the entire training set around, since you don't know in advance which point is closest.\n- In practice no one runs exact kNN at scale; **approximate nearest-neighbor** methods cut the time and storage cost dramatically.\n\n## Related pages\n- [[Image Retrieval (Bag of Words)]]\n- [[k-means Clustering]]\n- [[Bayesian Classification (MAP & ML)]]\n- [[Discriminative vs Generative Methods]]\n"},{"id":"Neural Network","folder":"Machine Learning","content":"**Summary**: Neural networks learn features automatically from (image, label) pairs instead of relying on hand-crafted features. A network is a composition of linear transformations (weights + bias) interleaved with nonlinearities; the nonlinearity is what lets it build progressively more abstract representations. This page covers what a network *is* and why it's expressive, then how it's *trained* — cost, gradient descent, SGD, momentum, and backpropagation.\n\n**Last updated**: 2026-05-29\n\n---\n\n## Motivation: learning features vs. hand-crafting them\nTraditionally, recognition meant **hand-crafting features** (SIFT, HOG, spatial pyramids, textons, SURF, LBP…) and feeding them to a classifier. HOG → pedestrian detection (Dalal & Triggs 2005) was an early ML-for-vision win. But hand-crafting uses **domain expertise** and must be redone for every new problem.\n\nNeural networks remove that burden. You **design the architecture once** (number of layers, widths, etc.); then, given training data, the network **learns the features automatically, end-to-end**. To switch from cat-vs-dog to car-vs-bike you don't redesign features — you just collect labeled images.\n\nTwo reasons this is powerful:\n- **Hierarchical, expressive features** — lower layers learn edges/gradients/blobs; deeper layers learn textures → object parts → whole objects. The architecture *encourages* this; we don't hand-specify it.\n- **Transferable** — features learned for one task transfer to others. Take a trained network and **fine-tune** it on a new task with much less data.\n\n## From biology to the perceptron\nThe idea is loosely inspired by **biological neurons** (dendrites → nucleus → axon → synapses) and the Hubel–Wiesel hierarchy (simple → complex → hypercomplex cells). An artificial neuron — the **perceptron** — takes inputs, weights them, sums, and applies a function:\n- Classic perceptron output: $\\text{sign}(\\mathbf{w}\\cdot\\mathbf{x} + b)$.\n- The version used here (with a ReLU): output $= \\max(0,\\ \\mathbf{w}\\cdot\\mathbf{f})$ — if the weighted sum is positive, pass it through; if negative, output 0.\n\n## Multi-layer perceptron (MLP)\nPut several neurons in a layer: each takes the **same inputs** but has its **own weights**. The layer's action is a **matrix–vector product** followed by the nonlinearity:\n$$\\mathbf{f}' = \\max(0,\\ W\\mathbf{f})$$\nwhere the rows of $W$ are the individual neurons' weights. Feed each layer's output into the next and repeat. The full network is a **composition of linear transformations with nonlinearities** in between.\n\n## Why the nonlinearity is essential\nWithout it, stacking layers is pointless: $W_2(W_1 x) = (W_2 W_1)x$ — two linear layers collapse into **one** linear transformation, no more expressive than a single layer. A nonlinearity between layers is what lets the network lift raw intensities → textures → parts → abstract concepts (cat/dog). This **nonlinearity sits between every pair of layers**.\n\n## Activation functions\n- **ReLU** — $\\max(0, x)$, the **R**ectified **L**inear **U**nit; most common today.\n- **Sigmoid** — $\\sigma(x) = 1/(1+e^{-x})$; popular historically.\n- **tanh** — $\\tanh(x)$.\n- **Leaky ReLU** — $\\max(0.1x, x)$.\n- **ELU** — $x$ if $x>0$, else $\\alpha(e^x - 1)$.\n\n## The bias term\nIn practice each neuron also has a **bias**: $\\max(0,\\ \\mathbf{w}\\cdot\\mathbf{f} + b)$. Without it, the learned function is forced through the **origin** (input 0 → output 0), restricting the function space. The bias lifts that restriction — a zero input can map to a nonzero output — adding flexibility. So the full network is:\n$$f = W_3\\,\\max(0,\\ W_2\\,\\max(0,\\ W_1 x + b_1) + b_2) + b_3$$\n\n## Counting learnable parameters\nFor a net with input 3 → hidden 4 → hidden 4 → output 1:\n- **Weights** (one per connection): $4{\\times}3 + 4{\\times}4 + 1{\\times}4 = 32$\n- **Biases** (one per neuron): $4 + 4 + 1 = 9$\n- **Total learnable parameters:** $32 + 9 = 41$\n\n(The input is *given*, so input nodes aren't learnable.) Modern networks have hundreds of layers and millions–billions–trillions of parameters.\n\nImplementation is just a few lines — each layer is a dot product + bias + activation:\n```python\nf = lambda x: 1.0/(1.0 + np.exp(-x)) # sigmoid activation\nx = np.random.randn(3, 1) # input (3x1)\nh1 = f(np.dot(W1, x) + b1) # hidden layer 1 (4x1)\nh2 = f(np.dot(W2, h1) + b2) # hidden layer 2 (4x1)\nout = np.dot(W3, h2) + b3 # output (1x1)\n```\n\n## Universal approximation: why neural networks are powerful\n- **Universal function approximators** (Cybenko, 1989): a **two-layer** network (one hidden layer) with *enough* neurons can approximate *any* continuous function to any desired accuracy.\n- The catch: \"enough\" can be **exponential** in the number of neurons for a shallow net. Adding **depth** drastically reduces the neurons needed — which is why modern networks are **deep** (many layers) rather than merely **wide**. Each extra layer applies more nonlinearity → more abstraction.\n### Why it's true (the box construction)\nAn intuitive 1-D proof. Any continuous $f(x)$ can be approximated as a **sum of thin rectangular boxes** (a histogram of the curve):\n$$f(x) \\approx \\sum_i w_i\\, I(a_i < x < b_i)$$\nwhere $I(\\cdot)$ is 1 inside the interval and 0 outside, and $w_i$ is the box height. Each **box** is built from **4 ReLUs**:\n$$I(a Caveat: this is an **existence** result — it says a good network *exists*, not that gradient descent will *find* it, nor that it will *generalize*. Finding the weights is the job of [[#Training a neural network|training]].\n\n---\n\n## Training a neural network\nThe network is a function with millions of unknown weights. Training = find the weights (and biases) that map inputs to their correct labels, by **minimizing a cost** with **gradient descent**.\n\n### The cost function\nUsing the **MNIST** digit task as the running example (28×28 = **784** input units → hidden layer(s) → **10** one-hot output nodes, one per digit), the network maps an input $x$ to an output vector $a$, and we want $a$ to match the label $y(x)$. The standard loss is the **quadratic / mean-squared-error (MSE) / L2** cost:\n$$C(w,b) = \\frac{1}{2n}\\sum_x \\lVert y(x) - a\\rVert^2$$\na sum of squared residuals over all $n$ training examples.\n\n(Aside on encoding: **one-hot** — digit $k$ → node $k$ = 1, rest 0 — is convenient because it lets the outputs look like probabilities later, e.g. via softmax. You *could* encode 10 classes in 4 binary nodes, but one-hot is the simpler default.)\n\n### Gradient descent\nPicture the cost as a landscape over the parameters; drop a ball and let it **roll down the valley**. For a small step $\\Delta v$ in parameter space, the change in cost is\n$$\\Delta C \\approx \\nabla C \\cdot \\Delta v, \\qquad \\nabla C = \\Big(\\tfrac{\\partial C}{\\partial v_1}, \\tfrac{\\partial C}{\\partial v_2}, \\dots\\Big)$$\nTo make $\\Delta C$ as **negative** as possible, take the step **opposite** the gradient. That gives the **update rule**:\n$$v \\to v' = v - \\eta\\,\\nabla C \\qquad\\Longleftrightarrow\\qquad w_k \\to w_k - \\eta\\,\\tfrac{\\partial C}{\\partial w_k}, \\quad b_l \\to b_l - \\eta\\,\\tfrac{\\partial C}{\\partial b_l}$$\nThe **learning rate** $\\eta$ sets the step size: **too small** → correct direction but painfully slow; **too large** → overshoot into a worse minimum. Each step is tiny and dumb, but enough of them reach a good solution — \"power in numbers,\" just like the network itself.\n\n### Stochastic gradient descent (SGD)\nThe exact gradient averages over the *whole* dataset, $\\nabla C = \\frac1n\\sum_x \\nabla C_x$, which is **O(n)** — far too slow when $n$ is millions or billions. Instead, draw a random **mini-batch** of $m$ samples and use its average as an estimate:\n$$\\frac{1}{m}\\sum_{j=1}^{m}\\nabla C_{x_j} \\approx \\frac{1}{n}\\sum_x \\nabla C_x = \\nabla C$$\nOver many steps the sampling noise tends to cancel. The mini-batch size is also bounded by **GPU memory**. Because the gradient is now a random estimate, this is **stochastic** gradient descent — the standard optimizer for neural networks.\n\n### Pitfalls of gradient descent\n- **Local minima & saddle points.** Wherever the gradient is **zero**, the ball has no push and gets **stuck**. A saddle point isn't a minimum but still has zero gradient. In practice, neural-network losses have *far more saddle points than local minima*, and SGD tends to settle at a **good saddle point** that generalizes well — part of why big networks work.\n- **Ill-conditioning.** If the loss is **steep in one direction and shallow in another** (a ski-slope valley), the step follows the steep wall, so you **jitter across the walls while crawling along the floor**. Quantified by the **condition number** — the ratio of the largest to smallest singular value of the **Hessian** (the matrix of second derivatives). A large ratio = badly conditioned = slow.\n- **SGD noise.** Mini-batch gradients are noisy approximations, so even on a nice bowl the path **meanders** toward the minimum. Bigger batches give cleaner gradients but cost more memory/time — a trade-off bounded by hardware.\n\n### Momentum\nDon't step on the *current* gradient alone — keep a **running mean of recent gradients** (a \"velocity\") and step on that:\n$$v_{t+1} = \\rho\\,v_t + \\nabla f(x_t), \\qquad x_{t+1} = x_t - \\alpha\\,v_{t+1}$$\n(With $\\rho = 0$ this is plain SGD.) Momentum helps three ways at once: **noise** averages out → a smoother path; **flat/zero-gradient regions** (local minima, saddles) still get pushed through, because past gradients carry the ball forward; and **ill-conditioned jitter** across the steep walls cancels while motion along the floor accumulates.\n\n**Learning-rate scheduling** complements this: be aggressive with $\\eta$ early, then **decay** it as you near the minimum (often with a small inner search over candidate step sizes).\n\n### Backpropagation\nGradient descent needs $\\partial C/\\partial w$ and $\\partial C/\\partial b$ for *every* parameter — there can be millions. Computing these naively is intractable; **backpropagation** is the efficient method.\n\nIt exploits the **layer-to-layer structure**. A neuron's output depends *only* on the previous layer:\n$$a^l_j = \\sigma\\!\\Big(\\underbrace{\\textstyle\\sum_k w^l_{jk}\\,a^{l-1}_k + b^l_j}_{z^l_j}\\Big)$$\nso the whole network is a **composition of functions**, $f(g(x))$. Gradients of a composition come from the **chain rule**:\n$$\\frac{dz}{dx} = \\frac{dz}{dy}\\cdot\\frac{dy}{dx}, \\qquad \\text{(multivariate)}\\quad \\frac{\\partial z}{\\partial x_i} = \\sum_k \\frac{\\partial z}{\\partial y_k}\\,\\frac{\\partial y_k}{\\partial x_i}$$\nApplying the chain rule *naively* across all layers produces an explosive number of derivatives. **Backpropagation = applying the chain rule in a careful order, reusing the values already computed in the forward pass**, so the whole gradient costs about the same as one forward pass.\n\nTwo things to keep straight:\n- **Backpropagation only *computes* gradients.** **SGD** is what *trains* the network (it uses those gradients in the update rule).\n- (Overfitting / regularization come in a later lecture.)\n\n#### Worked example\nTake $f(x,y,z) = (x+y)\\,z$ with $x={-}2,\\ y=5,\\ z={-}4$. The computational graph has an **add** node $q = x+y$ and a **multiply** node $f = q\\,z$.\n\n**Forward pass** (fill node values): $q = -2+5 = 3$, then $f = 3 \\times (-4) = -12$.\n\n**Backward pass** (fill gradients, output → inputs), using only the local rule for each node:\n- $\\dfrac{\\partial f}{\\partial f} = 1$ (the output w.r.t. itself).\n- Multiply node $f = q z$: each input's gradient is the **other** input's value. So $\\dfrac{\\partial f}{\\partial z} = q = 3$ and $\\dfrac{\\partial f}{\\partial q} = z = -4$.\n- Add node $q = x+y$: it just **passes the gradient through** ($\\partial q/\\partial x = \\partial q/\\partial y = 1$). By the chain rule $\\dfrac{\\partial f}{\\partial x} = \\dfrac{\\partial f}{\\partial q}\\dfrac{\\partial q}{\\partial x} = -4$, and likewise $\\dfrac{\\partial f}{\\partial y} = -4$.\n\nNotice **no derivative was actually computed** — each node just looked up forward-pass values and applied a fixed rule. That's the bookkeeping that makes backprop cheap.\n\n#### Gate patterns\nEvery node type has a simple backward behavior:\n- **add gate → gradient *distributor*** — copies the incoming gradient unchanged to both inputs.\n- **multiply gate → gradient *switcher*** — each input receives the *other* input's value × the upstream gradient (it \"switches\" the two values).\n- **max gate → gradient *router*** — sends the whole gradient to the **larger** input only; the other gets 0.\n\nAny operation gets such a rule, so backprop is just: go layer-by-layer from output to input, apply each node's rule. (This is the basis of a homework problem — solve it *with backprop*, not by writing out the full chain rule.)\n\n## Related pages\n- [[Convolutional Neural Network (CNN)]]\n- [[Transfer Learning]]\n- [[Generalization & Model Validation]]\n- [[Recognition & Vision Tasks]]\n- [[Discriminative vs Generative Methods]]\n- [[ML Architecture Families]]\n- [[ML Overview]]\n- [[Image Retrieval (Bag of Words)]]\n"},{"id":"Transfer Learning","folder":"Machine Learning","content":"**Summary**: Reuse a network pretrained on a large dataset (e.g. ImageNet) for a new task with less data. Because neural-network features are hierarchical and generic at lower layers, you can keep most of them and only retrain the parts that need to specialize — how much you retrain scales with how much data you have.\n\n**Last updated**: 2026-05-29\n\n---\n\nA practical reason [[Neural Network|neural networks]] (especially [[Convolutional Neural Network (CNN)|CNNs]]) are so useful: their learned features **transfer**. The hierarchical, expressive features learned for one task can be **reused** for a new task — so you don't need the huge labeled dataset again; a small amount of data can re-target them.\n\n## The setup\nTake a **source model** $H_s$ trained on a large **source dataset** — the classic one is **ImageNet** (≈1M images, 1000 classes), widely used as a pretraining base. Transfer it to a **target model** for your **target task**, which usually has far fewer images and different classes. Use $H_s$ as the **initialization** for the target network.\n\n## How much to retrain — scales with your data budget\nGoing from least to most data, retrain progressively more of the network:\n\n| Data available | What to retrain | Why |\n|---|---|---|\n| **Very little** | Only the **final classification layer** | Swap the 1000-way head for your *k*-way head; train just those new connections — few weights, so little data suffices. |\n| **A bit more** | Also the **fully-connected layers** | FC layers have the whole-image receptive field, so they hold **task-specific** features (cat-vs-dog). Re-learning them re-targets the task (e.g. → car-vs-bike). |\n| **More** | Also the **deeper conv layers** | These (wide receptive field via pooling) capture **parts** — ears, eyes, legs — useful but not fully task-specific. |\n| **Lots** | **Fine-tune the whole network** | Initialize all layers from $H_s$, then re-optimize everything. |\n\nIntuition: **convolutional layers extract generic features; fully-connected layers extract task-specific ones.** So with little data you keep the generic conv features and only relearn the task-specific top.\n\n## The learning rate = inertia vs. responsiveness\nWhen fine-tuning, the **learning rate** decides how far you move from the pretrained weights toward the new data:\n- **High learning rate** for layers you want to **relearn from scratch** (the new classification layer) — quickly absorb the new task.\n- **Low learning rate** for layers you want to **preserve** (intermediate conv layers) — respond to new data a little, but don't forget the good ImageNet features.\n\nIt also depends on **source↔target similarity**: similar domains → gentler fine-tuning (fewer layers, smaller learning rate); very different domains + enough data → retrain more, higher learning rate. Choosing the learning rate is itself a hyperparameter search — done on a [[Generalization & Model Validation|validation set]].\n\n## Related pages\n- [[Convolutional Neural Network (CNN)]]\n- [[Neural Network]]\n- [[Generalization & Model Validation]]\n- [[Recognition & Vision Tasks]]\n"},{"id":"k-means Clustering","folder":"Machine Learning","content":"**Summary**: k-means is an unsupervised algorithm that groups data points into *k* clusters by minimizing the within-cluster squared distance. In the bag-of-words pipeline it builds the **visual vocabulary** — the cluster centers become the \"visual words.\"\n\n**Last updated**: 2026-05-29\n\n---\n\n## Why cluster?\nAfter [[Image Retrieval (Bag of Words)|extracting features]], a large dataset gives a *huge* cloud of points in a high-dimensional space (e.g. 1M images × 1k patches ≈ 1 billion points). Most of that is redundant — many patches look alike. **Clustering** replaces each dense neighborhood of points with a single **prototype** (the cluster center), cutting memory and compute while keeping most of the expressive power. Points in one cluster are assumed to share similar properties.\n\nClustering is **unsupervised learning**: we're given unlabeled points and must discover structure. Simple axis-aligned rules don't recover semantically meaningful groups, so we pose it as a learning problem — most commonly **k-means**.\n\n## The goal (objective)\nFind the cluster centers that **minimize the sum of squared Euclidean distances** between points $x_i$ and their nearest cluster center $\\bar c_k$:\n\n$$D(X, C) = \\sum_{\\text{cluster } C_k} \\; \\sum_{\\text{point } i \\in C_k} (x_i - \\bar c_k)^2$$\n\n## The algorithm\n*k* (the number of clusters) is given by the user. Then:\n\n1. **Randomly initialize** *k* cluster centers (\"means\")\n2. **Iterate until convergence:**\n - **Assign** each data point to the **nearest** cluster center (this partitions the space — each center \"owns\" a set of points)\n - **Recompute** each center as the **mean (centroid)** of the points assigned to it (the center \"jumps\" to the new location)\n3. **Convergence** = the centers stop moving much between iterations.\n\nAlgorithmically trivial: alternate *assign* ↔ *recenter* until things settle.\n\n## Choosing k\n*k* is an **empirical hyperparameter** — you generally don't know the right value in advance. In practice, try a few values and keep the one that gives good **downstream** results (retrieval/classification quality).\n\n## Caveats\n- **No guarantee** of convergence to the optimum — a bad random initialization (or awkward data) can give poor clusters. Still, k-means **works very well in practice**.\n- It's the **first tool to reach for** with unlabeled, high-dimensional data: cluster, then check that points in a cluster really do look alike (well-behaved data) vs. mixed (poorly separated data).\n\n## Role in bag of words\nThe cluster centers are the **visual words** (a.k.a. **codewords**) — the vocabulary. Choosing *k* = 1000 gives a 1000-word vocabulary that can approximately represent any patch, collapsing a billion patches down to 1000 prototypes. This is step 2 of the [[Image Retrieval (Bag of Words)#The four-step pipeline (bag of features)|bag-of-features pipeline]].\n\n## Related pages\n- [[Image Retrieval (Bag of Words)]]\n- [[Nearest-Neighbor Classification]]\n- [[ML Overview]]\n"},{"id":"Deployment","folder":"Web & Backend Development","content":"**Summary**: Web servers, deployment environments and strategies (blue-green, rolling, canary), Docker containers, and AWS (EC2, S3).\n\n**Last updated**: 2026-04-06\n\n---\n\n# Web Server\n## Computer vs. Web Server\n- web server: a computer with CPU, motherboard, disk storage, power \n- difference between a computer and web server\n\t- web server a computer with specific compatibility \n\t- web server is computer, but not all computers are web servers\n## Common Web Servers\n- Apache HTTP Server\n- Internet info servervice\n- Nginx Web Server\n## Web Server user story\n1. user enter URL\n2. DNS return the IP address\n3. browser sents HTTP request to the web server using the IP address specified by the domain name server\n4. the web server return the page to the IP address of your computer\n5. your browser render \n\nWeb Service Terminologies\n- SMTP Server -- Simple Mail Transfer Protocol server: emails transactions\n- FTP Server - File Transfer Protocol: standard network protocol used for the transfer of computer files between a client and a server on a computer network\n- ISP -- Internet Service Provider: companies who propvide you service in terms of internet connection to connect to the internet\n- DNS -- Domain Name System: When someone type in domain name to find the IP that hosts your site. When you register the domain name, your IP address should be put in a DNS along with your domain name\n# Deployment\nDefinition: activities that make a software system available for use which you will publish the content to the machine that hosts our web application, **remotely**\n## Deployment Scenario\n### individual developer\n- runnable on locally computer\n- using local machine(own computer) & local network\n### Company & Organization\n- More machines, all in a server room\n- deploy on those things\n### Renting a server\n- rent a server\n- purchase machines, and rent a room for storage costs money\n- hire hardware engineers and guards costs money\n- publish our content to the machine that hots our web application, remotely\n### Modern Cloud Service\n - Pay for the amount we used\n- AWS, Azure, GCP\n## Environment\nOnce we have implemented some features, others need to have access to your application\nneeds to push our application to some other servers/Data Center\nEx.\n- local/dev env\n- QA env\n- UAT\n- Pre-Production/Staging Env\n- Production Env\nWhy many\n- human error\n- hold an additional application QA\n### Spring Profiles\n- core feature of the framework -- allowing us to map our beans to different profiles -- dev, test, prod\n- define profiles ()\n\t- application.yml -default\n\t- application-dev.yml - Dev\n\t- application-qa.yml - QA\n- Use Profiles\n\t- set spring.profile.active \n\t- JVM Parameters\n## Deployment consideration\n- will user still be able to access your application\n\t- downtime - when we close and start a new application, downtime?\n- will you allow all users to use those new features\n\t- Control Experiment\n- what if something goes wrong with the new version of your application\n\t- Rollback - we go back to the previous functional version\n## Deployment Strategies\n- Big Bang Deployment - Take the entire application down and then new version of the application is deployed\n- Blue-Green Box Deployment -- two versions\n\t- Blue version (old and stable)\n\t- Green version (new)\n\t- once the green version is tested and certified to work (shift the traffic from Blue to Green)\n- Rolling Deployment -- Keep one version but replace the old version with a new version during deployment\n- Canary Deployment -- keep both stable and new version, with the stable version serving most users and the new version serving a small pool of test users\n\n# Docker\nwhile the program has no problem on deploying on my computer, it doesn't means that it has no problem in deploying to other computer\n## Virtual Machine vs. Container\n### Virtual Machine \n- multiple VM on a server to reduce the underutilized hardware resources\n- Allow organization to install multiple OS in multiple environment\n- creating a VM layer where separate application can be ran separately with custom Operating system and own version control system\n### Docker\n- A container runs upon a computer's kernel (light-weight, efficient)\n\n## Docker Components\n### DockerFile\ninstruction on making the docker image\n### Docker Daemon\n- listens for Docker API request\n- Manage images, containers, networks and volumes \n### Docker Client\n- Docker CLI\n### Docker Registry\n- A registry stores Docker Images (DockerHub)\n### Docker Desktop \n- GUI to build, run image and container\n- contains Docker Daemon & Docker Client\n## Docker Objects\n### Images\n- read only template with instructions to create a Docker Container\n- based on other images\n- images provide by others\n- images act as a stack of layers\n### Containers\n- A runnable instance of an image\n### Network\n- Makes container to connect to and communicate with each other, or to non-Docker workloads\n\t- makes container to connect to and communicate with each other, or to non-Docker workloads \n### Volume\n- Storage Spaces for the container\n\n\ndocker build --> create an image from the dockerfile\ndocker run --> create an container out form the docker image\ndocker start\ndocker stop\ndocker log\ndocker push\ndocker pull\n\n![[dockerFile Demo.mov]]\n\n# AWS (Modern Cloud Service)\nEC2 - Classic Virtual Machine that is hosted in AWS instead of your data center\n- Compute + Storage\n- Compute = CPU + RAM\n- Storage = Hard Disk (Block storage)\n- Network Interface\n\nS3 - Simple Storage Service\n- Object Based Storage (file storage, media storage)\n- Not OS or DB storage\n- File up to 5 TB\n- Unlimited Storage (if you pay)\n- Bucket\n\t- name must be globally unique across all AWS users\n\t- when bucket created, go with a region which should be close to users to reduce latency\n\t\t- can't change upon creation\n\t- 100 buckets per account by default\n\t- Object in bucket\n\t\t- Key Value Pair\n\t\t- S3 Versioning is enabled, then if the same object is pushed to the bucket again, the new object will get a unique Version ID\n\t\t- \n## Why\n- Cost Saving - pay as you go\n- Fast start - Boot new server instances in min\n- Easy to scale up/down\n## Pricing Options\n- On Demand -- fixed rate by hour\n- Reserved -- Capacity Reservation with discount\n- Spot -- Big whatever the price you want for instance capacity\n- Dedicated Hosts -- Enable you to use your eligible software licenses from vendors\n## [EC2 Families](https://www.geeksforgeeks.org/devops/amazon-ec2-instance-types/): Handle different workflows\n - T: Cheap General Purpose\n - M: General Purpose\n## EC2 Storage\n- Instance Store\n\t- Ephemeral Storage -- goes away after instance got terminated\n- Elastic Block Storage (EBS)\n\t- Highly available and scalable storage volumes \n## Network Interface\nthe point of interconnection between a computer/server and a private or public network\n\n**AWS ENI** (Elastic Network Interface) -- virtual network card that providing:\n- IP Address: private and public\n- Security Groups: which port is exposed and which is not\n\t- All Inbound traffic is blocked by default\n\t- All Outbound traffic is allowed\n\t- STATEFUL -- when inbound rule allowing traffic in, that traffic is automatically allowed back out\n\t- change to security group take effect immediately\n\t- each security group can be attach to different resources\n- Mac Address\n\n## Usual Practice\n- Start our EC2 instance\n- Connect to the machine\n\t- install docker\n\t- pull image\n\t- start container\n- configure our security group and request info using HTTP\n- Key pair (login credential creation)\n\n## Related pages\n- [[Distributed System]]\n- [[Software Development Lifecycle & System Design]]\n- [[MAVEN Java Dev Op]]\n"},{"id":"Distributed System","folder":"Web & Backend Development","content":"**Summary**: Monolith vs. microservices, distributed-system trade-offs, service discovery / API gateway, and observability.\n\n**Last updated**: 2026-05-29\n\n---\n\n**Common Challenge for Monolithic Application**\n- Scalability: how to scale individual components within a single monolithic system (MUST SCALE THE ENTIRE SYSTEM)\n- Performance Bottlenecks: the entire application depends on the services that with the worst performance\n- Maintainability: Codebase becomes larger and harder to manage & New features increase the risk of breaking shit\n\nMonolithic vs. Microservices\n- Monolithic: Single application with tightly coupled modules with One codebase, one database\n- Microservices Architecture: independent services, each with its own functionality and database. Services communicate via APIs\n# Definition of Distributed System\n- A system where multiple services run independently across different machines\n- Different services work together to achieve a common goal. \n- Pro \n\t- Scalability — can scale certain service individually \n\t- Flexibility services can be deployed and updated independently \n\t- Fault Tolerance — if one service fails, others can continue operating \n- Con\n\t- Complexity — requires managing and coordinating multiple services \n\t- Network Latency — adds overhead due to internal service communication \n\t- Data Consistency — hard to keep data synchronized across multiple services\n## Distributed System vs. Microservices \nDistributed system is a broader concept where components run on multiple machines. And Microservices are one kind where services are **small, independent and loosely coupled**. \n# Breaking Monolithic Architecture\nCommon SOP\n- Identify boundaries: separated by business functionality or bounded context\n- Service independence\n\t- Independently deployable and scalable\n\t- Avoid tight coupling between services\n- Service communication\n\t- Service interact via REST APIs, gRPC, or message queues\n\t- Synchronous vs. Asynchronous communication trades offs\nQuestion to ask\n- What services should be independent?\n- How do we ensure smooth communication?\n- How do we manage data consistency across services?\n# Microservices 101\n\n## Database management\n- each Microservice manage its own database and schema\n- Potential Challenges: \n\t- Transaction management issues — 2 PC design, SAGA design\n\t- Data duplication \n\t- Slow performance —Asyn, Multi-threading\n## Components\n- Service Discovery: enable services to find each other dynamically as the service scale dynamically \n- Service Registry: centralized directory where services register their locations with a service name\n\t- no hardcode IP address\n\t- enable automatic load balancing \n- API Gateway: manage external request and routes them to services (Client <--> Backend)\n\t- Example: Spring Cloud Gateway\n\t\t- Route: defines where and how request should be forward\n\t\t- Predicate: a condition that matches incoming HTTP requests \n\t\t- Filter: modify requests or responses before forwarding to the destination service\n- Core Services: connect directly to database but not to other services\n- Composite services: connect to one or more core services but not connect to database\n## Observability\nIt is extremely important to implement **Logging**, **Monitoring**, and **Tracing** because we want the ability to monitor and understand the internal state of a system from the outside based on the data it generates\n### Real-world tools\n- Logging: ELK Stack\n- Metrics Monitoring: Prometheus + Grafana\n- Tracing and Service Monitoring: Kiali\n\n[https://medium.com/@jyoti1308/designing-proximity-service-yelp-7472e1f20cee](https://medium.com/@jyoti1308/designing-proximity-service-yelp-7472e1f20cee)\n\n## Related pages\n- [[Deployment]]\n- [[Software Development Lifecycle & System Design]]\n"},{"id":"Error Handling & Validation","folder":"Web & Backend Development","content":"**Summary**: Handling exceptions across the MVC layers — what can go wrong per layer, status-code mapping, logging, and Spring's @ControllerAdvice / @ExceptionHandler.\n\n**Last updated**: 2026-05-29\n\n---\n\nBugs and errors are inevitable regardless of developer skill. While some problems like `OutOfMemoryError` are unrecoverable system-level failures, most issues are situations the program didn't anticipate. Exceptions give us a structured way to catch and recover from these.\n\nJava distinguishes between checked exceptions (foreseeable environmental failures like I/O and database issues — the compiler forces you to handle them) and unchecked exceptions (programming logic errors like null references — they surface at runtime). In a web application, both types can occur across every layer.\n\nWe need a systematic approach to handle these exceptions at the right layer, log them with enough context to trace root causes, and return consistent, meaningful responses to users -- never exposing raw stack traces or whitelabel error pages.\n\n# Exception Occurrence by Service Layer\nIn [[JSP (Jakarta Server Pages)#MVC|MVC]] framework with different Service Layer(Repo, Service, Controller), we want to make sure we are clear with two questions: what can go wrong? best practice to handle them\n## Repository Layer\nThe Repository is responsible for interacting with database. Any Exception around database, such as connection failures, query errors, timeouts, constrain violations.\n\n**Best Practice:**\n- catch all client error and throw custom exception\n\t- Ex. query from user is not found\n- Throw default exception\n\t- Ex. let Spring throw the DataAccessException\n## Service Layer\nThe service layer is used to handle business logic. Any Exception around these should be handled, such as Business logic error, Data integrity, External services error\n\n**Service Error CheatSheet:**\n- Client did something wrong (invalid field, business rule violation) -> 400 with error message\n- Concurrency conflict (ex. two users modify same thing) -> Retry or Non-recoverable\n- [[#Repository Layer]] issue -> Let it propagate upward to [[#Controller Layer]]\n- Code error -> Non-recoverable\n\n**Best Practice:**\n- client error should be thrown using custom exception and additional info\n- Any non-recoverable exception should be propagated\n## Controller Layer\nThe controller layer handled incoming HTTP request, so handle any exception related to HTTP-related check. The controller is the first line of defense where the incoming HTTP request hits the application and it's where we catch and translate the errors into proper status code\n\n**Controller Error CheatSheet:**\n- client side problem (sent a `POST` to a `GET` or hits non-existing URL) -> 405 (Method Not Allowed) / 404 (Not Found)\n- \"you send me garbage\" (Required Field Error, Invalid Data in the request, Deserialization Error) -> 400 (bad Request)\n- Code Error -> 500 (Internal Server Error) (make sure we log the full stack trace)\n\n**Best Practice:**\n- handle anything related to http issues\n- All exception should be handled properly\n\t- Error Response with different Stat\n\t- consistent format\n\n## Service is used to handle business logic\n- Business logic error\n- Data integrity\n- External service error\n\nTypes of Exception\n- Request invalid with conflicting fields: 400 with error message\n- Business logic violation: 400 with error message\n- Concurrency/Race Condition: Retry or Non-Recoverable\n- Repository Layer Error: propagate Exception\n- Code Error: Non-recoverable\n\nBest Practice in Service layer\n- Any client errors should be thrown using a custom exception with additional information\n- Any non-recoverable exceptions should be propagated\n\t- why: this type of exception is typically caused by system or underlying infrastructure issues\n\t- for non-recoverable exceptions, they should be propagated directly rather than attempting to handle them\n## Bubble up mechanism\nExceptions bubble up through layers, with each layer adding additional context. At the end, toward the client, we provide clear and consistent status codes. Throughout the process, we log details for internal transparency across all layers.\n![[error_handling_dual_track.svg|697]]\n# Exception Handling\nWhile we have define a systematic way of logging exceptions, how do handling them so that:\n- for user: understand situation \n- for developer: details with root cause\n\nso that: **we never give user a whitelabel Error Page or StackTrace**\n\n**Core strategies:**\n- Logging: log messages in internal window\n- Error Response: Response to user\n- Retry: try again baby!!\n- Ignore: do nothing \n- Throw next exceptions: adding additional info\n## Exception Handling Strategy - Logging\n- Logs are records of a program's execution, used to troubleshoot and monitor its status\n- Crucial aspect of exception handling in web application\n\t- Logging allows developers to track issues, diagnose problems, and monitor the application's health\n\t- Proper Logging includes error message, stack trace, and contextual information to aid in debugging and maintenance\n- SLF4J or Log4J to standardize the process in java \n- Logging in python\n## Exception Handling Strategy - Error Response\n- Spring provides the application developer with a default exception handling mechanism\n\t- If we visit the API using browser client, it will return a \"white label error page\"\n\t- if we visit the API using machine client, it will return a JSON response\n- ErrorMvcAutoConfiguration - inject 4 beans\n\t- ErrorPageCutomizer\n\t- BasicErrorController\n\t- DefaultErrorViewResolver\n\t- DefaultErrorAttributes\n## Exception Handling Strategy - Retry\n- The retry mechanism can improve the resilience of web application by automatically reattempting failed operations \n- Good with dealing with transient issue such as network timeouts or temporary service unavailability \n- this strategy itself it anti-pattern (if ignore or handle unappricately, more issues will arise)\n- This strategy should include the following consideration \n\t- Back-off policy\n\t- Limited on the number of retries\n\t- Handling idempotency to avoid duplicate operations\n## Exception Handling Strategy - Ignore\n- Sometimes it is appropriate to ignore certain exceptions if they are deemed non-critical or expected under specific conditions\n\t- when deleting a user account, it is non-critical if the user's session does not exist\n- This strategy helps maintain the flow of the application without interruption\n- This strategy should be implemented carefully to ensure exception are not masked (choose wisely on what to surpressing and what to show/logging)\n## Exception Handling Strategy - New Exception\n- Re-throwing exceptions allows higher-level components to handle errors appropriately\n- (translate an exception)\n- This is useful when lower-level components cannot effectively manage the exception or when additional context needs to be provided before handling it\n- By re-throwing exceptions, developers can maintain a clean separation of concerns and ensure that exception-handling logic is centralized\n# Logging\n## motivation \n- debugging and troubleshooting\n\t- To record exception and errors\n\t- To display objects (request and response)\n- Performance monitoring\n\t- server speed\n- Health and maintenance\n\t- system health\n- Core business checkpoint\n\t- validation (missing properties)\n\t- status check (only active use can perform actions)\n## Logging format \n- Date and Time: Millisecond precision and easily sortable\n- Log Level: ERROR, WARN, INFO, DEBUG, or TRACE\n- Process ID\n- \"-\" separator to distinguish the start of actual log messages\n- Thread name: Enclosed in square brackets \n- Logger name: source of class name\n- The log message\n# Error Response\n## @ExceptionHandler\n- works at @Controller level\n- It is used within a controller to handle exceptions thrown by methods in that controller\n- so we\n\t- Capture specific exceptions and return custom responses\n\t- Support handling multiple exception types\n- returns a ResponseEntity or custom messages, allowing flexibility in determine \n- Drawbacks: only active for the specific controller\n# @HandlerExceptionResolver\n- Old approach to the problem\n- Resolve any exceptions thrown by the application\n- Allow us to implement a uniform exception handling mechanism\n# @ControllerAdvice\n- Popular choice\n- consolidate multiple, scatter @ExceptionHandler into global error handling component\n- Enables a mechanism that make use of ResponseEntity\n\n## Related pages\n- [[Spring Framework]]\n- [[JSP (Jakarta Server Pages)]]\n- [[Unit Testing]]\n"},{"id":"Git — Version Control Overview","folder":"Web & Backend Development","content":"**Summary**: Git basics — commits, the three stages, HEAD, essential commands, branching, merge vs. rebase, and conflict resolution.\n\n**Last updated**: 2026-04-06\n\n---\n\n\nGit is a **change-tracking system** — a form of **Version Control (Source Control)**.\nIt tracks modifications, stores history, and manages collaboration. Git is optimized for **line-by-line tracking**, not binary files.\n\n---\n\n# Core Advantages\n\n- **Tracking Changes** — view detailed logs of what changed and why \n- **Revert & Recovery** — restore previous versions easily \n- **Team Collaboration** — multiple developers can work in parallel \n- **Backup** — remote repositories keep extra copies of your work \n\n---\n\n# Commit\n\nA **commit** is a snapshot of your entire project at a specific moment.\n\nEach commit includes:\n\n- **Identifier** — unique SHA-1 ID \n- **Message** — description of the change \n- **Metadata** — author, timestamp, parent commit(s)\n\n---\n\n# Three Working Stages\n\n- **Working Directory** — your actual project files \n- **Staging Area (Index)** — where changes are prepared \n- **Repository** — the official stored history (committed state)\n\n---\n\n# HEAD Pointer\n\n**HEAD** points to *the latest commit of the currently checked-out branch*.\n\n---\n\n# Version Control Implementation\n\n## Repository\n\n- Stores all files and their entire history \n- Tracks file states \n- Contains complete project metadata \n\n## Distributed System\n\nEvery developer has a **full copy** of the repository.\n\n- No central server required \n- Works offline \n- Full commit history is shared\n\n---\n\n# Essential Git Commands\n\n---\n\n## Repository Management\n\n```bash\ngit init # Initialize a new repository\ngit status # Show current branch, staged changes, and unstaged changes\n```\n\n---\n\n## Basic Workflow\n\n```bash\ngit add . # Stage all modified files\ngit add # Stage specific file\ngit commit -m \"message\" # Commit staged changes\ngit diff # Show unstaged changes\ngit diff --staged # Show staged changes\n```\n\n---\n\n## History & Logging\n\n```bash\ngit log # Full commit history\ngit log --graph # Visual branch diagram\ngit log --oneline # One-line-per-commit view\ngit log --all # Logs from all branches\ngit reflog # Shows every HEAD movement (great for recovery)\n```\n\n---\n\n## Undoing Changes\n\n```bash\ngit revert # Safe: creates a commit that undoes another\ngit reset # Dangerous: rewrites history\n```\n\n### Reset Modes\n\n- **--soft** → Move HEAD only, keep changes staged \n- **--mixed** (default) → Move HEAD, unstage changes \n- **--hard** → Move HEAD and discard all changes permanently \n\n---\n\n## File Recovery\n\n```bash\ngit restore # Discard working directory changes\ngit restore --staged # Unstage a file\n```\n\n---\n\n## Branch Operations\n\n```bash\ngit branch # List local branches\ngit branch -a # List local + remote branches\ngit checkout -b # Create and switch to new branch\ngit switch # Modern branch switching\ngit checkout # Traditional branch switching\ngit branch -d # Delete merged branch\ngit merge # Merge branch into current\n```\n\n---\n\n## Stashing Changes\n\n```bash\ngit stash # Save uncommitted changes\ngit stash list # View saved stashes\ngit stash push -m \"message\" # Save stash with description\ngit stash pop # Apply & remove latest stash\ngit stash apply # Apply stash without removing\n```\n\n---\n\n## Remote Operations\n\n```bash\ngit push -u origin main # Push commits to remote (+ set upstream)\ngit pull # Fetch + merge remote updates\ngit fetch # Fetch without merging\n```\n\n---\n\n# Branch Naming Conventions\n\nUse consistent prefixes:\n\n- `feature/` \n- `bugfix/` \n- `hotfix/`\n\nReference: https://conventional-branch.github.io/\n\n---\n\n# Solving Merge Conflicts\n\nA merge conflict occurs when **two commits modify the same part of a file**.\n\nSteps:\n\n1. Open conflict file \n2. Manually resolve \n3. Stage the file \n4. Commit the merge resolution \n\n---\n\n# Git Rebase vs Merge\n\n### **Merge**\n\n- Combines histories \n- Creates a *merge commit* \n- Keeps branching timeline intact \n- Best for shared/public branches (safe)\n\n### **Rebase**\n\n- Rewrites history by moving commits \n- Produces a cleaner, linear history \n- Best for local work before pushing\n\n## Related pages\n- [[Software Development Lifecycle & System Design]]\n"},{"id":"HTML & CSS","folder":"Web & Backend Development","content":"**Summary**: HTML document structure and semantic tags, forms and tables, plus CSS selectors, the box model, positioning, and flexbox.\n\n**Last updated**: 2026-04-06\n\n---\n\n**HTML (HyperText Markup Language)** is a **descriptive language** used to define the structure and layout of a web page through plaintext files.\n# Basic Document Structure\n- **``**: The root element that wraps all page content.\n- **``**: Contains **metadata** and information not visible as primary content, such as titles, CSS styles, and scripts.\n- **``**: Encloses all the content intended for display to the user.\n# HTML Elements and Tags\n- **Composition**: Elements are generally composed of an **opening tag** (`<>`), the **content**, and a **closing tag** (``).\n- **Void Elements**: Special cases that use a **single tag** and contain no content, such as `` or `
`.\n- **Attributes**: Provide additional information to define an element's **behavior or appearance** (e.g., `id`, `class`, `src`, `href`).\n- **Special Characters**: Since characters like `<` or `&` are reserved for HTML syntax, **character entities** (e.g., `<`, `&`) must be used to display them as text.\n# Content and Text Structuring\nHTML provides **semantic tags** that help browsers and search engines understand the meaning and layout of page components.\n## Structural Semantic Tags\n- **`

`**: Introductory content, logos, or navigation.\n- **`

`**: A block containing navigation links.\n- **`

`**: The **primary content** of the document.\n - **`

`**: Self-contained compositions like blog posts or news.\n - **`

`**: Groups of related content under a heading.\n - **`

`**: A **generic container** used for grouping and styling when no semantic tag applies.\n- **`

`**: Content indirectly related to the main flow, such as sidebars.\n- **`