Linear Decision Boundary

easyFREESupport Vector MachinesMachine Learning 1

Classify data points using a linear decision boundary.

Given weights $w$ and bias $b$ , classify each point $x$ using: $f(x) = \text{sign}(w \cdot x + b)$

where $\text{sign}(z) = +1$ if $z \geq 0$ , and $-1$ if $z < 0$ .

Return a list of predictions ( $+1$ or $-1$ ).

Example

Input

X = [[1, 2], [-1, -2], [2, 0]]
w = [1, 1]
b = 0

Output

[1, -1, 1]

Reasoning

Inputs: X holds three 2-D points, one per row; w $= (1, 1)$ is the weight vector (one weight per feature) and b $= 0$ is the bias. Together they define the boundary line $w \cdot x + b = 0$ , here $x_1 + x_2 = 0$ .
Score each point with $z = w_1 x_1 + w_2 x_2 + b$ $z = w_{1} x_{1} + w_{2} x_{2} + b$ :
- $(1, 2)$ : $z = 1 + 2 + 0 = 3$
- $(-1, -2)$ : $z = -1 - 2 + 0 = -3$
- $(2, 0)$ : $z = 2 + 0 + 0 = 2$
Apply the sign: $\text{sign}(3) = +1$ , $\text{sign}(-3) = -1$ , $\text{sign}(2) = +1$ , giving [1, -1, 1], one label per row of X, in order.
Geometric view: $z$ says which side of the line a point falls on. $(1, 2)$ and $(2, 0)$ lie above $x_1 + x_2 = 0$ ; $(-1, -2)$ lies below it.
Notice: a point exactly on the line has $z = 0$ and is labelled $+1$ because $\text{sign}(0) = +1$ , so the output never contains $0$ .

Constraints

X: 2D list (n_samples x n_features)
w: list of weights (same length as features)
b: scalar bias
Return list of +1 or -1 predictions
sign(0) = +1

Learn this in

ClassificationML Study Plan Support Vector MachinesML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Gradient Boosting Residual Stephard Random Feature Subspacemedium

Concept primer

Background Knowledge

The problem involves using a linear decision boundary to classify data points. This concept is fundamental to Support Vector Machines (SVMs), a type of supervised learning algorithm used for classification and regression tasks. In the context of SVMs, the goal is to find a hyperplane (a line in two dimensions or a plane in three dimensions) that separates the data into different classes. The linear decision boundary is the equation of this hyperplane, which is used to make predictions on new, unseen data.

The equation $f(x) = \text{sign}(w \cdot x + b)$ represents the linear decision boundary, where $w$ is the weight vector, $x$ is the input data point, $b$ is the bias term, and $\text{sign}(z)$ is the sign function. The sign function returns $+1$ if the input $z$ is greater than or equal to zero, and $-1$ otherwise. This function is used to determine the class label of the input data point.

In the context of SVMs, the weight vector $w$ and bias term $b$ are learned during the training process, and the linear decision boundary is used to make predictions on new data. The linear decision boundary is a simple yet powerful concept that can be used to classify data points into different classes.

Algorithm/Approach

The general approach to solving this problem involves using the given weight vector $w$ and bias term $b$ to compute the linear decision boundary for each input data point $x$ . This can be done by implementing the equation $f(x) = \text{sign}(w \cdot x + b)$ in code. The algorithm pattern involves iterating over each input data point, computing the linear decision boundary, and returning the predicted class label.

Step-by-Step Strategy

To implement the solution, follow these steps:

Define the weight vector $w$ and bias term $b$ as given in the problem statement.
Define a function to compute the dot product of two vectors.
Define a function to compute the sign function.
Iterate over each input data point $x$ and compute the linear decision boundary using the equation $f(x) = \text{sign}(w \cdot x + b)$ .
Return the predicted class label for each input data point.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Incorrectly computing the dot product of the weight vector $w$ and input data point $x$ .
Incorrectly implementing the sign function.
Failing to handle edge cases, such as when the input data point $x$ is zero.

Time & Space Complexity

The expected time complexity of the solution is O(n), where n is the number of input data points, since we need to iterate over each data point to compute the linear decision boundary. The expected space complexity is O(n), since we need to store the predicted class labels for each input data point. However, the actual time and space complexity may vary depending on the specific implementation and the size of the input data.

solution.py

Python 3.13

Test results