AI & Signal Processing (EC-802 (A)) - Unit 2 Short Notes

UNIT 2: AI & SIGNAL PROCESSING (EC-802 A)

Based on exhaustive analysis of May 2023 Paper A, these notes cover all tested topics in the exact sequence of the approved blueprint.

I. ARTIFICIAL INTELLIGENCE FOUNDATIONS & TECHNIQUES

A. Core Concepts and Definitions

Artificial Intelligence (AI)

• Definition: The science and engineering of creating intelligent machines, particularly intelligent computer programs. It aims to synthesize human-like capabilities such as learning, reasoning, problem-solving, perception, and language understanding.

• Relationship & Differentiation:

  | Feature | Artificial Intelligence (AI) | Machine Learning (ML) | Deep Learning (DL) | | :--- | :--- | :--- | :--- | | Scope | Broadest field; encompasses ML & DL. | Subset of AI. | Subset of ML. | | Core Idea | Create systems that can perform tasks requiring human intelligence. | Systems that learn from data without explicit programming. | ML using multi-layered neural networks (deep architectures). | | Dependency | Can use rules-based systems (non-ML). | Requires data to learn patterns. | Requires large data & significant compute. | | Example | Chess-playing program (rule-based). | Spam filter (learns from email data). | Image recognition (CNNs), NLP (Transformers). |

Types of Machine Learning

1. Supervised Learning:

   • Characteristics: Learns from labeled training data (input-output pairs). Goal is to learn a mapping function f: X → Y.

   • Applications: Classification (spam/ham), Regression (house price prediction).

2. Unsupervised Learning:

   • Characteristics: Learns from unlabeled data. Finds hidden patterns or intrinsic structures.

   • Applications: Clustering (customer segmentation), Dimensionality Reduction (PCA).

3. Reinforcement Learning (RL):

   • Characteristics: Agent learns to make decisions by performing actions in an environment to maximize a cumulative reward. Learns via trial-and-error.

   • Applications: Game playing (AlphaGo), Robotics, Autonomous driving.

Intelligence: Natural vs. Artificial

AI and Knowledge

• Role of Knowledge: Knowledge is the information an AI system uses to reason, make decisions, and solve problems. It forms the basis of an AI agent's "intelligence."

• Declarative vs. Procedural Knowledge:

  | Declarative Knowledge | Procedural Knowledge | | :--- | :--- | | What to know. Facts, concepts, relationships. | How to do something. Skills, procedures, methods. | | Example: "The capital of France is Paris." | Example: "How to calculate the derivative of a function." | | Represented as data (facts, rules in a KB). | Represented as code, rules, or strategies. |

[!TIP] Exam Focus: Be prepared to draw clear comparisons (AI/ML/DL, Natural/Artificial, Declarative/Procedural). Use tabular formats in answers for clarity.

B. Knowledge Representation & Reasoning

Utility Theory

• Concept: A framework for rational decision-making under uncertainty. An agent assigns a utility (a numerical measure of preference/happiness) to each possible outcome. The rational choice is the action that maximizes expected utility.

• Importance: Provides a mathematical foundation for building rational agents. It quantifies preferences and allows trade-offs between risky options.

• Example: A medical diagnosis agent assigns high utility to correct treatment and low utility to incorrect treatment or unnecessary procedures. It chooses the test/treatment path with the highest expected utility based on probabilities of diseases.

Logical Inference: Forward vs. Backward Chaining

[!TIP] Common Pitfall: Confusing the starting point and search direction. Remember: Forward = from Facts, Backward = from Goal.

C. Probabilistic Graphical Models

Markov Models

• Definition: A stochastic model describing a sequence of possible events where the probability of the next event depends only on the current state (Markov Property).

• Components:

  • States: A finite set of conditions the system can be in.

  • State Transition Probabilities: P(State_t+1 | State_t).

  • Initial State Distribution.

  • Output/Observation Probabilities (for Hidden Markov Models - HMMs).

• Markov Property (Memoryless): P(S_{t+1} | S_t, S_{t-1}, ..., S_1) = P(S_{t+1} | S_t).

• Applications in AI:

  • Speech Recognition: HMMs model phoneme sequences.

  • Bioinformatics: Modeling DNA/protein sequences.

  • Natural Language Processing: Part-of-speech tagging.

  • Robot Localization: Tracking position over time.

Bayesian Networks (Belief Networks)

• Structure: A directed acyclic graph (DAG).

  • Nodes: Represent random variables (discrete/continuous).

  • Edges: Represent direct conditional dependencies (causal or probabilistic influence).

  • Conditional Probability Tables (CPTs): Associated with each node, quantifying P(Node | Parents).

• Importance: Provides a compact, graphical representation of the joint probability distribution P(X1, X2, ..., Xn). Enables reasoning under uncertainty by computing posterior probabilities given evidence (e.g., P(Disease | Symptoms)).

• Example (Medical Diagnosis):

  
  [Pollution] --> [Cancer] <-- [Smoking]
  
  

  • Nodes: Pollution (High/Low), Smoking (Yes/No), Cancer (Yes/No).

  • CPT for Cancer specifies P(Cancer | Smoking, Pollution).

  • Inference: Given patient is a smoker (Smoking=Yes) and lives in high pollution area (Pollution=High), compute P(Cancer=Yes | Evidence).

D. Machine Learning Paradigms & Methods

Machine Learning: Overview

• Learning Model Definition: A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

  • Task (T): What the system does (e.g., classification, regression).

  • Performance Measure (P): How success is quantified (e.g., accuracy, error rate).

  • Experience (E): The source of learning data.

• Factors Affecting Learning:

  1. Data Quality & Quantity: Garbage in, garbage out. Need sufficient, representative, clean data.

  2. Algorithm Choice: Different algorithms have different inductive biases (assumptions).

  3. Bias-Variance Trade-off: Fundamental tension.

     • High Bias: Underfitting, oversimplified model, misses patterns.

     • High Variance: Overfitting, models noise, poor generalization.

  4. Feature Engineering: Representation of data is critical.

  5. Hyperparameter Tuning: Settings not learned by the algorithm (e.g., learning rate, tree depth).

Comparative Analysis: Decision Trees vs. Naive Bayes

II. SIGNAL PROCESSING: ANALYSIS & DESIGN

A. Discrete Fourier Transform (DFT) Fundamentals

Core Properties and Theorems

1. Circular Convolution Property

• Statement: The circular convolution of two finite-length sequences x1(n) and x2(n) of length N is equivalent to the multiplication of their DFTs.

$$x_1(n) \circledast x_2(n) \longleftrightarrow X_1(k) \cdot X_2(k)$$

where `\circledast` denotes N-point circular convolution.

• Proof Sketch:

  1. Define circular convolution: (x1 ⊛ x2)(n) = Σ_{m=0}^{N-1} x1(m) x2((n-m) mod N).

  2. Take its DFT: DFT{(x1 ⊛ x2)(n)} = Σ_{n=0}^{N-1} [Σ_{m=0}^{N-1} x1(m)x2((n-m) mod N)] W_N^{nk}.

  3. Interchange sums: = Σ_{m=0}^{N-1} x1(m) [Σ_{n=0}^{N-1} x2((n-m) mod N) W_N^{nk}].

  4. Substitute l = (n-m) mod N: = Σ_{m=0}^{N-1} x1(m) W_N^{mk} [Σ_{l=0}^{N-1} x2(l) W_N^{lk}].

  5. Recognize inner sum as X2(k) and outer sum as X1(k). Hence, = X1(k) X2(k).

• Relationship to Linear Convolution: Linear convolution x1(n) * x2(n) of length L1 and L2 produces a sequence of length L1+L2-1. To compute linear convolution using DFT:

  1. Zero-pad both sequences to length N ≥ L1+L2-1.

  2. Compute N-point DFTs: X1(k), X2(k).

  3. Multiply: Y(k) = X1(k) X2(k).

  4. Compute inverse DFT: y(n) = IDFT{Y(k)}.

  • Result: y(n) is the linear convolution of the original sequences.

  \boxed{\text{Linear Convolution} \rightarrow \text{Zero-pad to } N \geq L_1+L_2-1 \rightarrow \text{DFT} \rightarrow \text{Multiply} \rightarrow \text{IDFT}}

2. DFT of Real and Even Sequences

• Statement: If a sequence x(n) is real and even (x(n) = x(-n) = x(N-n) for n=1,...,N-1), then its DFT X(k) is also real and even.

• Proof Sketch:

  1. DFT definition: X(k) = Σ_{n=0}^{N-1} x(n) W_N^{nk}, where W_N = e^{-j2π/N}.

  2. For real x(n): X^*(k) = Σ_{n=0}^{N-1} x(n) W_N^{-nk} = X((-k) \mod N). This gives conjugate symmetry: X(k) = X^*(-k).

  3. For even x(n): The DFT sum becomes X(k) = x(0) + 2 Σ_{n=1}^{N/2-1} x(n) \cos(2πkn/N) + [x(N/2) \cos(πk) if N even].

  4. The expression is purely real (no imaginary j term). From step 2, real + conjugate symmetry implies even symmetry: X(k) = X(-k).

• Implication: For a real-even sequence, you only need to compute the first half (k=0 to N/2) of the DFT spectrum, as the second half is a mirror image. The values are real numbers, simplifying computation.

Applied DFT Problems: Modulation Property

• Modulation in Time Domain ↔ Frequency Shift:

  If g(n) = W_N^{-kn0} x(n) (multiplication by a complex sinusoid), then

$$G(k) = X((k - k_0) \mod N)$$

*   **Interpretation:** Multiplying `x(n)` by `W_N^{-kn0}` **shifts** its DFT `X(k)` **circularly** to the right by `k0` positions.

• Example from Past Paper (May 2023):

  Given X(k) = [5, 6, 1, 2, 9] for N=5, and g(n) = W_5^{-2n} x(n).

  Here, k0 = 2. Therefore,

  G(k) = X((k - 2) mod 5).

  • G(0) = X(-2 mod 5) = X(3) = 2

  • G(1) = X(-1 mod 5) = X(4) = 9

  • G(2) = X(0) = 5

  • G(3) = X(1) = 6

  • G(4) = X(2) = 1

  \boxed{G(k) = [2, 9, 5, 6, 1] \quad \text{for } k=0,1,2,3,4}

B. Multirate Signal Processing & Filter Banks

Quadrature Mirror Filter (QMF) Banks

• Concept & Purpose: A special type of two-channel filter bank used for subband coding. It splits an input signal into two complementary frequency bands (lowpass and highpass) and reconstructs it perfectly (or nearly) from the decimated subbands. Primary application: data compression (e.g., JPEG2000, MP3).

• Structure:

  • Analysis Bank: Input → H0(z) (lowpass) & H1(z) (highpass) → Downsample by 2 (M=2) → Subband signals Y0(m), Y1(m).

  • Synthesis Bank: Subbands → Upsample by 2 → G0(z) & G1(z) → Sum → Output \hat{x}(n).

• Perfect Reconstruction (PR) Condition: For alias-free PR, the synthesis filters must satisfy:

  G0(z) = H0(-z) and G1(z) = -H1(-z) (for linear phase QMFs). The overall transfer function should be T(z) = \hat{X}(z)/X(z) = c z^{-k} (a pure delay).

• Diagram Placeholder:

  DiagramCANVAS: Draw a two-channel filter bank block diagram. Show input x(n) splitting into two paths. Top path: Analysis LPF H0(z) → Downsample by 2 (↓2) → Y0(m). Bottom path: Analysis HPF H1(z) → Downsample by 2 → Y1(m). Then, Y0(m) → Upsample by 2 (↑2) → Synthesis LPF G0(z) → + → Output x̂(n). Y1(m) → Upsample by 2 → Synthesis HPF G1(z) → - (negative sign) → +. Label all components clearly.

Classification of Filter Banks in Multirate Systems

C. Advanced Interpolation & Sampling Rate Conversion

Spline Interpolation

• Principle: Uses piecewise polynomial (splines) to interpolate between data points, ensuring smoothness at the joins (knots). A k-th order spline uses polynomials of degree k with continuous derivatives up to order k-1 at knots.

• Common Type: Cubic Spline (k=3). It provides a twice-continuously differentiable (C^2) curve, offering a good balance between smoothness and computational cost.

• Use Cases for Smooth Signal Reconstruction:

  • Audio Resampling: Avoiding Gibbs-like oscillations from high-order polynomial interpolation.

  • Computer Graphics & CAD: Generating smooth curves from discrete points.

  • Numerical Solutions of ODEs: Interpolating solution points.

  • Advantage over Lagrange: Reduces Runge's phenomenon (oscillations at edges for high-degree polynomials).

Computationally Efficient Sampling Rate Converters

• Architecture for Rational Rate Conversion (I/D): To change sampling rate by a rational factor I/D (interpolation by I, then decimation by D):

  1. Interpolation (Upsampling by I): Insert I-1 zeros between samples. This creates I copies of the original spectrum, centered at k=0, ±I, ±2I,....

  2. Lowpass Filtering (Anti-imaging): Use a single filter H(z) with cutoff π/I to remove the image spectra. This filter must also suppress aliasing from the subsequent decimation.

  3. Decimation (Downsampling by D): Keep every D-th sample.

• Efficiency via Polyphase Decomposition: The combined interpolation-filter-decimation operation can be implemented using the polyphase decomposition of the filter H(z). This structure:

  • Reduces computation: Operates at the lower of the input or output rate.

  • Reduces memory: Only needs to store D (or I) phases, not the full filter.

  • Enables efficient implementation of arbitrary rational converters.

  \boxed{\text{Efficient Converter} = \text{Polyphase Filter Bank Structure operating at } \min(R_{in}, R_{out})}

D. IIR & FIR Filter Structures & Realizations

Basic FIR and IIR Filter Structures

Parallel All-Pass Realization of IIR Transfer Functions

• Concept: Any stable, rational transfer function H(z) can be decomposed into a sum of all-pass filters and a constant:

$$H(z) = K + \sum_{i=1}^{K} \frac{\alpha_i + z^{-1}}{1 + \alpha_i z^{-1}}$$

where each term `(α_i + z^{-1})/(1 + α_i z^{-1})` is an **all-pass filter** (magnitude response = 1, phase is variable).

• Advantages:

  1. Stability Guaranteed: Since all-pass filters are stable (poles inside unit circle), the parallel sum is stable.

  2. Linear Phase Possible: For specific choices of α_i (all real), the overall H(z) can have generalized linear phase.

  3. Low Sensitivity: Coefficient changes affect phase more than magnitude, useful in equalizer design.

  4. Modular Structure: Easy to adjust individual all-pass sections.

Fractionally Spaced Equalizers (FSE)

• Concept: An equalizer whose tap spacing T_s is a fraction (e.g., T_s = T/2, T/4) of the symbol period T, i.e., it samples the continuous-time received signal above the Nyquist rate for the symbol rate.

• Advantages over Symbol-Spaced Equalizer (SSE):

  1. Robustness to Timing Phase Errors: An FSE with T/2 spacing is inherently timing-phase agnostic. It can recover the correct sampling phase automatically, unlike SSE which is highly sensitive to the exact sampling instant.

  2. Better Performance in Dispersive Channels: By oversampling, it can better track and compensate for channel distortion, especially with non-minimum phase channels.

  3. Avoids Aliasing: The oversampling factor provides a margin against spectral nulls.

• Implementation: Typically a linear FIR filter with T_s < T. The output is decimated to symbol rate after equalization.

Viterbi Detector (Brief)

• Application: Implements Maximum Likelihood Sequence Estimation (MLSE) for channels with memory (e.g., intersymbol interference - ISI).

• Principle: Finds the most probable sequence of transmitted symbols x given the received sequence y, by solving:

$$\hat{x} = \arg\max_x P(x|y) = \arg\max_x P(y|x)P(x)$$

It uses the **Viterbi Algorithm**—a dynamic programming approach that efficiently finds the optimal path through a **trellis diagram** representing all possible state sequences (states = previous `L` symbols, where `L` is channel memory).

• Relation to Equalization: An MLSE Viterbi detector is the optimal (but complex) alternative to linear equalizers (like FSE). It makes hard decisions on sequences, not individual symbols, combating error propagation.

III. SYNTHESIS: CROSS-CUTTING THEMES & EXAM PRIORITIES

A. High-Frequency Exam Topics (Directly from May 2023 Paper A)

• AI Section: ALL topics from I(A) through I(D) were explicitly asked. Expect definitions, comparisons, and examples.

• Signal Processing Section: ALL topics from II(A) through II(D) were explicitly asked. Expect proofs, computations, and explanations.

• Integrated Questions: None present in May 2023, but be prepared to conceptually link AI decision models (e.g., Bayesian inference) with signal detection/equalization problems.

B. Foundational Proofs & Derivations (Exam-Critical)

1. DFT Circular Convolution Property – Proof Required. (4 marks)

   • Must show step-by-step derivation starting from definitions. Key step: substitution l = (n-m) mod N.

2. DFT of Real and Even Sequence – Proof Required. (3 marks)

   • Must show how the DFT sum reduces to a real cosine sum and derive even symmetry.

3. Modulation Property Application: Be fluent in computing G(k) from X(k) for g(n)=W_N^{-kn0}x(n). This was a 7-mark numerical problem.

C. Comparative Analysis Questions

• Decision Tree vs. Naive Bayes: Know the underlying principle (rule-based vs. probabilistic), the critical Naive Bayes independence assumption, and when each is suitable (interpretability vs. speed/baseline).

• Forward vs. Backward Chaining: Know the starting point (facts vs. goal), search strategy (breadth vs. depth), and typical application domains (monitoring vs. diagnosis).

• Basic FIR vs. IIR Structures: Know Direct Forms, Cascade/Parallel forms. Understand stability (FIR always stable) and sensitivity (Cascade/Parallel better).

• Types of Machine Learning: Be ready to list Supervised, Unsupervised, RL with one clear example for each and their key characteristic.

[!TIP] Final Exam Strategy: The May 2023 paper had no choice—all questions were compulsory. Structure your answers with clear headings, definitions in bold, key formulas in \boxed{}, and use tables for comparisons. For proofs, write "Given..." and state the property clearly before deriving. For numerical DFT problems, show the modulation property formula first.