How unit 5 is examined
This unit covers newer and non-parametric methods; density estimation (Parzen window, Gaussian mixture) carries most marks, then fuzzy classification, with one question each on kNN, histogram rules and neuro-fuzzy.
Recent advances in Pattern Recognition
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Recent advances are the modern methods that extend classical statistical pattern recognition to harder data: kernel machines, soft computing, deep learning and structural methods.
Key points.
- Classical methods assume clean, low-dimensional, well-separated data, whereas recent methods handle noisy, high-dimensional and overlapping classes.
- Support vector machines, fuzzy and neuro-fuzzy systems and neural networks learn complex boundaries from examples.
- Density estimation and mixture models replace fixed distribution assumptions with data-driven ones.
- <mark>Recent advances aim at better accuracy on real, uncertain data through soft computing and learning from data.</mark>
Structural PR
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Structural (syntactic) pattern recognition describes a pattern by its parts and their relations, and classifies it by matching that structure against a grammar.
Key points.
- A pattern is broken into primitives such as strokes or edges, and the primitives are joined by relations to form the description.
- A grammar $G=(V_N,V_T,P,S)$ defines the allowed structures of each class, and a parser checks whether a pattern belongs to the class.
- It suits patterns with clear structure such as handwriting, fingerprints and chromosomes, but it is weak against noise.
- <mark>A pattern is assigned to the class whose grammar can generate its primitive string.</mark>
SVMs
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. A support vector machine is a classifier that finds the hyperplane $w^Tx+b=0$ with the maximum margin between two classes.
Key points.
- The margin is $2/\|w\|$, so maximising it means minimising $\tfrac12\|w\|^2$ subject to $y_i(w^Tx_i+b)\ge 1$.
- Only the points on the margin, called support vectors, decide the boundary.
- Kernels such as the RBF or polynomial kernel handle non-linear data by mapping it to a higher-dimensional space, and a soft margin with parameter $C$ tolerates overlap.
- <mark>SVM chooses the separating hyperplane with the largest margin.</mark>
FCM
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Fuzzy C-Means is a clustering method in which every point belongs to every cluster with a membership degree between 0 and 1.
Key points.
- It minimises $J=\sum_i\sum_k u_{ik}^m\|x_i-c_k\|^2$ with fuzzifier $m>1$ and memberships of each point summing to 1.
- Memberships and centres are updated alternately: $u_{ik}=1/\sum_j(d_{ik}/d_{ij})^{2/(m-1)}$ and $c_k=\sum_i u_{ik}^m x_i/\sum_i u_{ik}^m$.
- <mark>Unlike hard K-means, FCM allows a point to belong partly to several clusters.</mark>
Soft computing and Neuro-fuzzy techniques
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. Soft computing is a set of tolerant, approximate methods (fuzzy logic, neural networks, genetic algorithms); a neuro-fuzzy system combines the learning of a neural network with the human-like reasoning of fuzzy logic.
Key points.
- Fuzzy logic gives interpretable IF-THEN rules but cannot learn, while a neural network learns but is a black box, so the hybrid gets both.
- ANFIS is a five-layer network (fuzzification, rule strength, normalisation, consequent, output) whose membership and consequent parameters are tuned by backpropagation and least squares.
- Fuzzy MLP feeds fuzzified features or memberships into a multilayer perceptron and outputs class memberships.
- Applications are control systems, medical diagnosis, forecasting and character recognition.
<mark>A neuro-fuzzy system is a fuzzy inference system whose parameters are learned like a neural network.</mark>
Asked: [7 marks] (Nov 2023) Describe about the Neuro-Fuzzy and its Techniques.
Real-life examples
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. Real-life examples are the everyday applications where patterns are recognised automatically from data.
Key points.
- Speech recognition, handwriting and OCR, and face or fingerprint recognition are classic uses.
- Medical diagnosis from ECG and X-ray images, and spam or fraud detection, classify patterns into categories.
- Remote sensing, industrial inspection and biometric security use image classification.
- <mark>Every application follows sensing, feature extraction and classification.</mark>
Histograms rules
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. A histogram estimates a density by dividing the range into equal bins and counting the samples in each: $\hat p(x)=n_j/(nh)$ for $x$ in bin $j$ of width $h$.
Key points.
- Bin width $h$ is the smoothing rule: narrow bins give a spiky estimate and wide bins hide the shape.
- Sturges rule sets the number of bins as $k=1+\log_2 n$, so $n=32$ samples give $k=6$ bins.
- Normalisation divides the count by $nh$ so that the total area is 1 and the histogram is a valid density.
- Construction: find the range, choose $k$ and $h=(\max-\min)/k$, count samples per bin, then divide by $nh$ and draw the bars.
- Bins must not overlap, must cover all data, and their edges must be fixed before counting.
==Sturges rule: number of bins $k=1+\log_2 n$, height $=n_j/(nh)$.==
Asked: [7 marks] (Nov 2023) State and explain the rules of Histogram in detail.
Density Estimation
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>
Definition. Density estimation is finding the probability density $p(x)$ of a variable from samples $x_1,\dots,x_n$ without knowing its form; parametric methods assume a form (Gaussian mixture), non-parametric ones use the data directly (Parzen, kNN, histogram).
Formula. For a region of volume $V$ holding $k$ of $n$ samples: $p(x)\approx \dfrac{k/n}{V}$.
Parzen window. With window function $\varphi(u)=1$ if $|u|\le\tfrac12$ (else 0) and bandwidth $h$:
$$\hat p(x)=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{h}\,\varphi\!\left(\frac{x-x_i}{h}\right)$$
Key points.
- The Parzen window (kernel density estimation) places a window of width $h$ on every sample and averages them, so it is a smoothed histogram centred at the point.
- The window $\varphi$ must be non-negative and integrate to 1; a Gaussian window gives a smooth estimate.
- A small $h$ gives a noisy, spiky estimate with high variance, and a large $h$ over-smooths with high bias.
- As $n\to\infty$ with $h\to0$ and $nh\to\infty$, the estimate converges to the true density.
- Parzen fixes the volume and counts $k$, while kNN fixes $k$ and grows the volume.
- Gaussian mixture model (GMM): $p(x)=\sum_{k=1}^{K}\pi_k\,N(x\mid\mu_k,\Sigma_k)$ with $\pi_k\ge0$, $\sum_k\pi_k=1$, a weighted sum of Gaussian components.
- GMM parameters $(\pi_k,\mu_k,\Sigma_k)$ are estimated by the EM algorithm: the E-step computes each component's responsibility for a point, and the M-step re-estimates weights, means and covariances; repeat until the likelihood stops rising.
- GMM is used for soft clustering, density estimation, speaker and image modelling.
Example. Samples $\{2,3,4,10,11\}$, box window $h=2$, at $x=3$: points within $[2,4]$ are 2, 3, 4, so $k=3$, $n=5$.
| Given | Working | Result |
|---|---|---|
| $n=5,\ h=2,\ x=3$ | $\hat p=\frac{1}{5}\cdot\frac{3}{2}$ | 0.3 |
Answer frame. Parzen: open with the definition and $\hat p(x)$; draw a box or Gaussian window over samples; develop points 1-5 (window, effect of $h$, link to kNN); close with applications. GMM: open with the weighted-sum definition; write the pdf; then EM steps and uses. For "any three", give definition, formula and one use for each.
Pitfall: Forgetting the $1/h$ factor, so the estimate does not integrate to 1.
Asked: [14 marks] (Jun 2020) Write short note on any three: i) Parzen window ii) Density estimation iii) Learning iv) Adaptation v) Cluster validation Asked: [7 marks] (Dec 2020, Jun 2020) Write a short note on Gaussian mixture model. / Explain the concept of Gaussian mixture model. Asked: [7 marks] (Dec 2020) Explain the term Parzen window, density estimation in brief.
Nearest Neighbor Rule
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>
Definition. The k-nearest neighbour method classifies a point by the majority class among its $k$ nearest training samples, using a distance such as Euclidean $d=\sqrt{\sum(x_i-y_i)^2}$.
Key points.
- kNN estimation fixes $k$ and grows a volume $V$ around $x$ until it holds $k$ samples, giving $\hat p(x)=\dfrac{k/n}{V}$; for $n=5$, $k=3$ and 1-D radius 1 ($V=2$) this gives 0.3.
- kNN rule: find the $k$ nearest neighbours, count votes per class and assign the majority class; $k=1$ is the nearest neighbour rule.
- Choose an odd $k$ to avoid ties; small $k$ gives jagged, noisy boundaries and large $k$ smooths them.
- It needs no training but is slow at test time, and features should be scaled.
<mark>kNN assigns the class most common among the $k$ nearest samples.</mark>
Asked: [7 marks] (Jun 2020) How the k-nearest neighbour method works? Explain with KNN estimation and KNN rule.
Fuzzy classification
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>
Definition. Fuzzy classification assigns a pattern a degree of membership $\mu\in[0,1]$ in each class, using fuzzy sets and IF-THEN rules, instead of a crisp yes or no.
Diagram.
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 596 80" width="596" height="80" role="img" aria-label="Fuzzy classification: input X, Fuzzification F, rule inference R, defuzzification D, class C"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah3)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah3)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah3)"/><path class="e" d="M446,40 L535,40" marker-end="url(#ah3)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">X</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">C</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Fuzzy classification: input X, Fuzzification F, rule inference R, defuzzification D, class C</figcaption></figure>
Key points.
- Fuzzy classes are needed because real classes overlap and are ambiguous (for example "tall" or "warm"), and a crisp boundary forces an arbitrary and brittle decision.
- A fuzzy set is defined by a membership function $\mu_A(x)$, such as a triangular or Gaussian curve, giving the degree of belonging.
- Fuzzy rules have the form IF $x_1$ is High AND $x_2$ is Low THEN class is A, with AND taken as min and OR as max.
- Steps: fuzzify the inputs, evaluate the rules, aggregate the rule outputs, then defuzzify (for example the centroid $\sum x\mu/\sum\mu$) or pick the class of highest membership.
- Fuzzy decision making combines the membership of goals and constraints, $\mu_D=\min(\mu_G,\mu_C)$, and picks the alternative with the highest $\mu_D$.
- Applications are medical diagnosis, washing-machine control, and image and speech classification.
Answer frame. Open with why crisp classes fail on overlap and define fuzzy sets; draw the pipeline; develop points 2-4; give one example; close with the advantage of graded, human-like decisions. For decision making, stress point 5 and defuzzification.
Asked: [7 marks] (Dec 2020) Why use Fuzzy classes? What is the Fuzzy classification process? Asked: [7 marks] (Jun 2020) What do you mean by fuzzy decision making?
Last-minute revision
- Parzen estimate: $\hat p(x)=\frac1n\sum\frac1h\varphi\!\left(\frac{x-x_i}{h}\right)$; small $h$ spiky, large $h$ smooth.
- General density estimate: $p(x)\approx (k/n)/V$; Parzen fixes $V$, kNN fixes $k$.
- GMM: $p(x)=\sum\pi_k N(x|\mu_k,\Sigma_k)$, $\sum\pi_k=1$, fitted by EM (E-step responsibilities, M-step parameters).
- Sturges rule: $k=1+\log_2 n$; histogram height $n_j/(nh)$.
- kNN: majority vote of $k$ nearest; use odd $k$; $k=1$ is the nearest neighbour rule.
- Fuzzy classification: fuzzify, infer with rules, aggregate, defuzzify.
- Fuzzy decision: $\mu_D=\min(\mu_G,\mu_C)$.
- Neuro-fuzzy: ANFIS five layers, trained by backpropagation plus least squares.
- SVM margin is $2/\|w\|$; FCM memberships sum to 1 with fuzzifier $m>1$.
- Structural PR: primitives plus grammar and parser.
Memory hooks
- Parzen = "P for Place a window on every sample; K for Keep count, then grow volume".
- GMM = weighted sum of bells, tuned by EM (Expect, then Maximise).
- Fuzzy pipeline: F-R-D (Fuzzify, Rules, Defuzzify).
- ANFIS = five layers: Fuzzify, Rule, Normalise, Consequent, Output.
- Sturges = 1 plus log-two of n.
Coverage checklist
- Recent advances in Pattern Recognition: definition and key points (no past questions).
- Structural PR: primitives, grammar (no past questions).
- SVMs: margin and kernels (no past questions).
- FCM: fuzzy memberships and update rules (no past questions).
- Soft computing and Neuro-fuzzy techniques: Nov 2023 neuro-fuzzy question.
- real-life examples: applications (no past questions).
- Histograms rules: Nov 2023 histogram rules question.
- Density Estimation: Jun 2020 any-three note, Gaussian mixture model (Dec 2020, Jun 2020), Parzen window (Dec 2020).
- Nearest Neighbor Rule: Jun 2020 kNN question.
- Fuzzy classification: Dec 2020 fuzzy classes question, Jun 2020 fuzzy decision making.