CS/ECE/ME532 Assignment 1 Notes

Assignment 1 - Binary Classifier and Polynomial Vector Space

1. Binary Classifier

a) Expressing y as an inner product

The decision rule for the binary classifier is based on the sign of $x1a1 + x2a2 - b$ . We can express this as an inner product $y = x^T w$ , where:

$x = \begin{bmatrix} x1 \ x2 \ 1 \end{bmatrix}$ is the feature vector.
$w = \begin{bmatrix} a1 \ a2 \ -b \end{bmatrix}$ is the weight vector.

Thus, $y = x1a1 + x2a2 - b = x^T w$ .

b) Decision Boundary as a Straight Line

The decision boundary is defined by $x1a1 + x2a2 = b$ . To show this is a straight line in the $x1$ - $x2$ plane, we can rearrange the equation to solve for $x_2$ :

$x2 = -\frac{a1}{a2}x1 + \frac{b}{a_2}$

This is in the form of a straight line $y = mx + c$ , where:

Slope: $m = -\frac{a1}{a2}$
Intercept with the vertical axis ( $x2$ ): $c = \frac{b}{a2}$

c) Feature Matrix X

Given the four data samples, the feature matrix X is constructed as follows:

$X = \begin{bmatrix} 0 & 0.4 & 1 \ 0.2 & 0.1 & 1 \ 0.5 & 0.6 & 1 \ 0.9 & 0.8 & 1 \end{bmatrix}$

Each row represents a data sample, with columns corresponding to $x1$ , $x2$ , and a 1 for the bias term.

d) Sketching the Decision Boundary and Classifying Data

Given $a1 = 1$ , $a2 = 2$ , and $b = 1$ , the decision boundary equation is:

$x1 + 2x2 = 1$

Or, solving for $x_2$ :

$x2 = -\frac{1}{2}x1 + \frac{1}{2}$

This is a straight line with a slope of -1/2 and a y-intercept of 1/2. To classify the data points:

(0, 0.4): 0 + 2(0.4) = 0.8 < 1, Class -1
(0.2, 0.1): 0.2 + 2(0.1) = 0.4 < 1, Class -1
(0.5, 0.6): 0.5 + 2(0.6) = 1.7 > 1, Class 1
(0.9, 0.8): 0.9 + 2(0.8) = 2.5 > 1, Class 1

The points (0, 0.4) and (0.2, 0.1) are classified as -1, and (0.5, 0.6) and (0.9, 0.8) are classified as 1.

e) Linear Classifier Script

The linear classifier script classifies 5000 data points with two features. The decision boundary observed is a straight line, which separates the two classes.

f) Changing Classifier Weights

Changing the classifier weights to $w = \begin{bmatrix} 1.6 \ 2 \ -1.6 \end{bmatrix}$ alters the slope and position of the decision boundary. This leads to a different linear separation of the data points, resulting in a different classification for some points.

2. Polynomial Vector Space

a) P as a Vector Space

To show that $P$ is a vector space, we need to verify the vector space axioms:

Closure under addition: If $p, q \in P$ , then $p + q$ is also a polynomial of degree $ \leq n$ , so $p + q \in P$ .
Closure under scalar multiplication: If $p \in P$ and $c \in \mathbb{R}$ , then $cp$ is also a polynomial of degree $ \leq n$ , so $cp \in P$ .
Commutativity of addition: For all $p, q \in P$ , $p + q = q + p$ .
Associativity of addition: For all $p, q, r \in P$ , $(p + q) + r = p + (q + r)$ .
Existence of additive identity: The zero polynomial $0$ is in $P$ (can be viewed as a polynomial of degree - $\infty$ ), and for all $p \in P$ , $p + 0 = p$ .
Existence of additive inverse: For every $p \in P$ , there exists $-p \in P$ such that $p + (-p) = 0$ .
Distributivity of scalar multiplication with respect to vector addition: For all $a \in \mathbb{R}$ and $p, q \in P$ , $a(p + q) = ap + aq$ .
Distributivity of scalar multiplication with respect to scalar addition: For all $a, b \in \mathbb{R}$ and $p \in P$ , $(a + b)p = ap + bp$ .
Associativity of scalar multiplication: For all $a, b \in \mathbb{R}$ and $p \in P$ , $a(bp) = (ab)p$ .
Existence of multiplicative identity: For all $p \in P$ , $1p = p$ .

b) Inner Product Definition

To show that $p^Tq = \int_{-1}^{1} p(x)q(x) dx$ is an inner product, we need to verify the following properties:

Symmetry: $p^Tq = q^Tp$ since $\int{-1}^{1} p(x)q(x) dx = \int{-1}^{1} q(x)p(x) dx$ .
Linearity: $(ap + bq)^Tr = a(p^Tr) + b(q^Tr)$ for any scalars a, b. This holds because integration is linear.
Positive-definiteness: $p^Tp \geq 0$ and $p^Tp = 0$ if and only if $p = 0$ . Since $p(x)^2 \geq 0$ for all $x$ , $\int{-1}^{1} p(x)^2 dx \geq 0$ . If $\int{-1}^{1} p(x)^2 dx = 0$ , then $p(x) = 0$ for all $x \in [-1, 1]$ , so $p$ is the zero polynomial.

c) Orthogonal Polynomials

To check for orthogonality, we need to compute the inner product of each pair of polynomials:

$p1(x) = x$ , $p2(x) = 1 - x$ , $p_3(x) = 3x^2 - 1$

$p1^Tp2 = \int{-1}^{1} x(1 - x) dx = \int{-1}^{1} (x - x^2) dx = [\frac{x^2}{2} - \frac{x^3}{3}]_{-1}^{1} = (\frac{1}{2} - \frac{1}{3}) - (\frac{1}{2} + \frac{1}{3}) = -\frac{2}{3}$ . Not orthogonal.
$p1^Tp3 = \int{-1}^{1} x(3x^2 - 1) dx = \int{-1}^{1} (3x^3 - x) dx = [\frac{3x^4}{4} - \frac{x^2}{2}]_{-1}^{1} = (\frac{3}{4} - \frac{1}{2}) - (\frac{3}{4} - \frac{1}{2}) = 0$ . Orthogonal.
$p2^Tp3 = \int{-1}^{1} (1 - x)(3x^2 - 1) dx = \int{-1}^{1} (3x^2 - 1 - 3x^3 + x) dx = [x^3 - x - \frac{3x^4}{4} + \frac{x^2}{2}]_{-1}^{1} = (1 - 1 - \frac{3}{4} + \frac{1}{2}) - (-1 + 1 - \frac{3}{4} + \frac{1}{2}) = 0$ . Orthogonal.

Thus, $p1(x)$ and $p3(x)$ are orthogonal, and $p2(x)$ and $p3(x)$ are orthogonal.