Linear Decision Boundary
Classify data points using a linear decision boundary.
Given weights w and bias b, classify each point x using: f(x)=sign(wâ‹…x+b)
where sign(z)=+1 if z≥0, and −1 if z<0.
Return a list of predictions (+1 or −1).
Example:
X = [[1, 2], [-1, -2], [2, 0]] w = [1, 1] b = 0
[1, -1, 1]
- We calculate the dot product of each point x in X with the weight w:
- For x=[1,2], wâ‹…x=(1)(1)+(1)(2)=3
- For x=[−1,−2], w⋅x=(1)(−1)+(1)(−2)=−3
- For x=[2,0], wâ‹…x=(1)(2)+(1)(0)=2
- We add the bias b to each result:
- For x=[1,2], wâ‹…x+b=3+0=3
- For x=[−1,−2], w⋅x+b=−3+0=−3
- For x=[2,0], wâ‹…x+b=2+0=2
- We apply the sign function to each result to get the predictions:
- For x=[1,2], sign(3)=+1
- For x=[−1,−2], sign(−3)=−1
- For x=[2,0], sign(2)=+1
- The final output is [1,−1,1]
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
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)=sign(w⋅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 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)=sign(wâ‹…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)=sign(wâ‹…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.