\documentclass{article}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}
\usepackage[top=2cm, bottom=4.5cm, left=2.5cm, right=2.5cm]{geometry}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    urlcolor=blue
}
\usepackage{amssymb}
\usepackage{enumerate}
\usepackage{xcolor}
\usepackage{tikz}

\setlength\parindent{0pt}

% Edit these as appropriate
\newcommand\course{CS 1420}
\newcommand\hwnumber{2}                      % <-- homework number
\newcommand\duedate{Thursday, February 5, 2026 at 12:00pm \textbf{(Noon)}}

\begin{document}
   \begin{center}
      \huge\textbf{Homework \hwnumber}
   \end{center}

   \begin{center}
        \large{Due: \duedate}
   \end{center}

\section*{Written Assignment}

\subsection*{Problem 1: Halfspaces}
(6 points)

\bigskip
Let $\mathcal{X} = \{0, 1\}^d$ and $\mathcal{Y} = \{-1, 1 \}$. Define a halfspace $h: \mathcal{X} \to \mathcal{Y}$ for the following functions: 
\begin{enumerate}
    \item \textbf{Conjunction}: Output is 1 if and only if all $d$ attributes are 1.
    \item \textbf{Majority}: Output is 1 if and only if more than half of the $d$ attributes are 1.
\end{enumerate}

Make sure to explain why you have chosen your weights and why they exhibit the desired behavior. You can assume that there is a bias term and that you can express your weights and bias in terms of $d$.

\medskip
\textit{Note:} For this assignment, the function $\operatorname{sign}: \mathbb{R} \to \{-1, 0, 1\}$ is given by
\begin{equation}\label{sign}
    \operatorname{sign}(x) = \begin{cases}
        1 & \text{if } x > 0 \\
        0 & \text{if } x = 0 \ \textsc{(Should not happen to achieve 100\% accuracy)}\\
        -1 & \text{if } x < 0.
    \end{cases}
\end{equation}

% TODO: add your solution here!
%
%
%
%
%
%

\subsection*{Problem 2: More Halfspaces}
(4 points)

\bigskip
Consider the function $h_{\text{equiv}}: \{0, 1\}^2 \to \{-1, 1 \}$ (ie. $x_1, x_2 \in \{0, 1\}$) given by
\begin{equation}\label{h_equiv}
    h_{\text{equiv}}(x_1,x_2) =
    \begin{cases}
        1 & \text{ if } x_1 = x_2,\\
        -1 & \text {otherwise.}
    \end{cases}
\end{equation}
Show that $h_{\text{equiv}}$ cannot be represented as a halfspace with a bias term.

\medskip
\textit{Hint:} In class, we showed that XOR cannot be represented with a halfspace. Try a similar argument.

% TODO: add your solution here!
%
%
%
%
%
%

\subsection*{Problem 3: Decision Boundaries}
(4 points)

\bigskip
Recall that the projection of a vector ${\bf x}$ onto a vector ${\bf w}$ is given by

\begin{equation}\label{proj}
    \operatorname{proj}_{\mathbf{w}} \mathbf{x} = \frac{\langle \mathbf{w}, \mathbf{x} \rangle}{\|{\bf w}\|_2^2} \mathbf{w}.
\end{equation}

$\operatorname{proj}_{\mathbf{w}} \mathbf{x}$ can be pictured as the component of ${\bf x}$ that lies in the direction of ${\bf w}$:

\begin{center}
\begin{tikzpicture}
    % Graph
    \draw[->] (-2,0) -- (2,0) node[right] {};
    \draw[->] (0,-2) -- (0,2) node[above] {};
    
    % Line
    \draw[thin,black!60] (-2,-1) -- (2,1);
    
    % Vector w
    \draw[->,black!50] (0,0) -- (-1,2) node[above right] {$\mathbf{w}$};
    
    % Random vector x
    \draw[->,black!50] (0,0) -- (1,1) node[above left] {$\mathbf{x}$};

    % Projection
    \draw[->,black!40] (0,0) -- (-1/5,2/5) node[above left] {$\operatorname{proj}_{\mathbf{w}} \mathbf{x} $};
    \draw[-,black!50,dotted] (1,1) -- (-1/5,2/5) node[above left] {$\operatorname{proj}_{\mathbf{w}} \mathbf{x} $};
\end{tikzpicture}
\end{center}

\medskip
Consider a halfspace classifier of the form $h_{{\bf w}}({\bf x}) = \text{sign}(\langle {\bf w}, {\bf x} \rangle)$ where $h: \mathbb{R}^d \to \{-1, 1\}$, $\mathbf{w}, \mathbf{x} \in \mathbb{R}^d$, and there is no bias term.
The distance from an example ${\bf x}$ to the decision boundary is defined as the distance from the example ${\bf x}$ to the point ${\bf a}$ on the decision boundary with minimum distance to the example ${\bf x}$. $\|\cdot\|_2$ denotes $L^2$ norm, given by 
$\| \mathbf{x} \|_2 = \sqrt{x_1^2 + \ldots + x_d^2}$ for $x \in \mathbb{R}^d$.

\medskip
Prove that the distance from an arbitrary example ${\bf x}$ to the decision boundary defined by ${\bf w}$ is
\begin{equation}\label{dist}
\frac{|\langle{\bf w}, {\bf x} \rangle|}{\|{\bf w}\|_2}.
\end{equation}

\medskip
\textit{Reminder:} The decision boundary of a halfspace classifier is the set of points in $\mathcal{X}$ where the classifier's output changes from -1 to 1, i.e., the solution to $\langle{\bf w}, {\bf x}\rangle = 0.$

% TODO: add your solution here!
%
%
%
%
%
%

\subsection*{Problem 4: Least Squares Invertibility}
(4 points)

\bigskip
The following proposition was given in lecture without proof.
Suppose we have a dataset of $m$ examples each with $d$ features $\mathbf{x}_1, \ldots, \mathbf{x}_m \in \mathbb{R}^d$, where $m \geq d$. We know that
satisfying the following equality is equivalent to satisfying the least squares condition:
\begin{equation}\label{leastsquares}
    A \mathbf{w} = \mathbf{b}, \quad \text{where } A = \sum^m_{i=1} \mathbf{x}_i \mathbf{x}_i^\textrm{T} \text{ and } \mathbf{b} = \sum^m_{i=1} y_i \mathbf{x}_i.
\end{equation}
This can be expressed more directly in matrix form by defining
\begin{equation}\label{matrixform}
    A = \begin{pmatrix}
        \vdots & \vdots & \vdots \\
        \mathbf{x_1} & \cdots & \mathbf{x_m} \\
        \vdots & \vdots & \vdots
    \end{pmatrix} \begin{pmatrix}
        \vdots & \vdots & \vdots \\
        \mathbf{x_1} & \cdots & \mathbf{x_m} \\
        \vdots & \vdots & \vdots
    \end{pmatrix}^\textrm{T},
    \quad \text{and} \quad
    \mathbf{b}= \begin{pmatrix}
        \vdots & \vdots & \vdots\\
        \mathbf{x_1} & \cdots & \mathbf{x_m} \\
        \vdots & \vdots & \vdots
    \end{pmatrix} 
    \begin{pmatrix}
        y_1 \\
        \vdots\\
        y_m
    \end{pmatrix}.
\end{equation}
Show that $A$ is invertible (i.e. $A$ has full rank) if and only if $\mathbf{x_1, \cdots x_m}$ span $\mathbb{R}^d$. Use the fact that for any matrix $B$, $\operatorname{rank}(B) = \operatorname{rank}(B^T)$.

\medskip
\textit{Note:} If you're new to proofwriting or unsure of what constitutes a complete argument, don't hesitate to ask questions!

% TODO: add your solution here!
%
%
%
%
%
%


\subsection*{Problem 5: Logistic Regression} (7 points)\\ \\
Suppose we collect data on a set of restaurants in Providence. For each restaurant, we've measured the average spiciness level of their most popular dish (on a scale of 1 to 100), $x_1$, and the average number of menu items in their signature tasting menu, $x_2$. Each restaurant also has a label indicating whether or not it received a ``Gold Fork" award from a prestigious food magazine. From this data, we decide to fit a logistic regression and determine that $\mathbf{w} = (0.05, 1, -6 )$, where the last component is the bias.

\begin{enumerate}[a.]

\item What is the probability that a restaurant with a dish spiciness level of $20$ and an average of $3.8$ tasting menu items gets a ``Gold Fork"?
\item How many average tasting menu items would the restaurant in part (a) need in order to have a $50\%$ chance of getting a ``Gold Fork"?
\item Suppose we want to extend our logistic regression model to predict all possible award tiers (Gold Fork, Silver Fork, Bronze Fork, etc.). Why should we use the softmax function in this case, but not previously? 
\end{enumerate} 

% TODO: add your solution here!
%
%
%
%
%
%


\newpage

\section*{Programming Assignment}
\subsection*{Introduction}

Steve decides to assemble a very high-brow assortment of sweet treats for a party. Not wanting to appear unrefined, he realizes he needs the perfect wine pairings for his confection charcuterie, and he's asked you---with the help of machine learning---to help him choose which ones!

\medskip
Steve was able to find some public data about various wines, but we need your help to determine how people would rate the bottles at his local Trader Joe's on a scale from 1 to 10.

\medskip
In this assignment, you'll implement linear regression and use your model to predict wine quality. The book sections relevant to this assignment are 9.2 on page 123, and 9.3 on page 126. 

\subsection*{Stencil Code \& Data}

You can find the stencil code and dataset for this assignment on GitHub Classroom at this \href{https://classroom.github.com/a/Eg4tAWDs}{link}. For more details, please see the  \href{https://docs.google.com/document/d/1RbsJ_IKfzuAyL7yDma4Z7bCVTwiNJfPAHbBAd2WeIEE/edit?usp=sharing}{download/submission guide}.

\medskip
We have provided the following stencil code:
\begin{itemize}
	\item \texttt{main.py} is the entry point of program which will read in the dataset, run the model, and print the results.
	
	\item \texttt{models.py} contains the \texttt{LinearRegression} model you will be implementing.
\end{itemize}

You should not modify any code in \texttt{main.py}. If you do for debugging or other purposes, please make sure any additions are commented out in the final handin. The autograder will run on an unmodified version of \texttt{main.py}. All the functions you need to fill in reside in \texttt{models.py}, marked by \texttt{TODO}s. You can see a full description of them in the section below. To run the program, run \texttt{python main.py} in a terminal with the course environment set up.


\subsection*{Datasets}
\subsubsection*{UCI Wine Quality}
For the Linear Regression model, you will be using the UCI Wine Quality Dataset,\footnote{P. Cortez, A. Cerdeira, F. Almeida, T. Matos and J. Reis. \\
Modeling wine preferences by data mining from physicochemical properties. In Decision Support Systems, Elsevier, 47(4):547-553, 2009.}
which contains information about various attributes of a wine and its corresponding quality rating out of 10. It includes 4898 examples, which will be split into training and testing datasets using the \texttt{sklearn} library (you do not have to worry about this, as we have implemented it for you---you will be doing this in the next assignment!). Each example contains 12 attributes, and your model will train on the first 11 attributes (and a 12th bias term) to predict the last value. More information about the dataset can be found at \url{https://archive.ics.uci.edu/ml/datasets/Wine+Quality}.

\subsection*{The Assignment}
In \texttt{models.py}, there are three functions you will implement. They are:

\begin{itemize}
\item \texttt{LinearRegression}:
\begin{itemize}
	\item[\textendash] {\bf train\_solver()} uses matrix inversion to find the optimal set of weights for the given data.
	\item[\textendash] {\bf predict()} predicts the values of test data points using the trained weights.
	\item[\textendash] {\bf squared\_error()} is a helper function that calculates the sum squared difference between two arrays.
\end{itemize}
In addition, three methods are provided for you. You should not change them.
\begin{itemize}
	\item[\textendash] \texttt{train()} calls  \texttt{train\_solver()}, which will train your model based on your implementation of matrix inversion.
	\item[\textendash] \texttt{loss()} computes the squared error loss of the predicted labels over a dataset.
	\item[\textendash] \texttt{average\_loss()} computes the average squared error loss per prediction over a dataset.
\end{itemize}
\end{itemize}

\textit{Note:} You are not allowed to use any off-the-shelf packages that have already implemented these models, such as scikit-learn or any linear regression functions. We're asking you to implement them yourself.

\subsection*{Linear Regression}
    Linear Regression learns linear functions of the inputs: 
    \begin{equation}\label{linreg}
        h_{\bf w}(\bf{x}) = \langle {\bf w} , {\bf x} \rangle.
    \end{equation}
    \textit{Note:} the bias term can be included here by padding the data with an extra feature of 1. This has been already done for you in the stencil.

    \medskip
    As we are using squared loss, the ERM hypothesis has weights
    \begin{equation}\label{erm}
        {\bf w} = \text{argmin}_{\bf w} \sum_{i = 1}^{m}(y_{i} - h_{\bf w}(\bf{{\bf x}_i}))^{2}.
    \end{equation}
\subsubsection*{Squared Loss} 
    \texttt For this assignment, we will be evaluating and training the Linear Regression model using sum squared loss (or L2 loss). Recall that the L2 loss function is defined as:
    \begin{equation}\label{l2}
        L_S(h_{\bf w}) = \sum\limits_{i=1}^m(y_{i}-h_{\bf w}({\bf x}_{i}))^{2},
    \end{equation}
    where $y_{i}$ is the target value of $i^{th}$ sample and $h_{\bf w}({\bf x}_{i})$ is the predicted value of that sample given the learned model weights. Your model should seek to minimize this loss through matrix inversion to learn the ERM hypothesis.
    
    \subsubsection*{Matrix Inversion}
    
    You can assume that the examples in the training data are linearly independent.
    In that case, we showed in lecture that you can use matrix inversion to compute the vector of weights $\bf{w}$ that minimizes the squared loss. The equation to find {\bf w}, for a set of data points $X$ and their labels ${\bf y}$ is
    \begin{equation}\label{matinv}
        {\bf w} = (X^T X)^{-1} X^T {\bf y}.
    \end{equation}
    
    \textit{Note:} $X$ here is a matrix of examples stacked row-wise (i.e. ${\bf x_1}$ is the first row of $X$ and so on). In lecture we saw that with $X$ as a matrix of examples stacked column-wise (i.e. ${\bf x_1}$ is the first column of $X$ and so on), the equation is equivalently:
    \begin{equation}\label{matinv2}
        {\bf w} = A^{-1}{\bf b} = (XX^T)^{-1}X{\bf y}.
    \end{equation}
    Implement the solution for ${\bf w}$ in \texttt{LinearRegression}, using the \texttt{np.linalg.pinv} function to calculate matrix inverses.

\subsection*{Project Report}

Each programming assignment in this course will be accompanied by a short report in which you will answer a few guiding questions. These questions are included to promote critical thinking about the results of your algorithms, both mathematically and societally. By the end of this course you will not only be able to implement common machine-learning algorithms but also develop intuition as to how the results of a given algorithm should be interpreted and can impact the world around you.

\medskip
The next section outlines some guiding questions that you should answer in your report. We ask that your final report be a PDF file named \texttt{report.pdf}, which must be handed in along with your code. You may use any program to create the PDF file, but we highly recommend using \LaTeX. We have provided an example report available on our course website to get you started.

\medskip
In future reports, you may need to write new code that generates some output (potentially a value or graph) that you will want to include in your writeup. For example, you may be asked to contrast the results of running the same algorithm on different datasets or to explore the effect of changing a certain hyperparameter in your algorithm. Please leave any code that you use in your final handin but make sure that it is \textbf{not} run by default when your program is run.  

\subsubsection*{Guiding Questions}
\begin{itemize}

    \item Linear regression analysis makes several assumptions. For one, all observations in the data must be independent of each other (e.g., the data should not include more than one observation on any individual/unit). Furthermore, the data should avoid including extreme values since these will skew the results and create a false sense of relationship in the data. In general, linear regression gives more weight to cases that are far from the average. Can you think of any examples or datasets in which this might pose an issue?
    \item In \href{https://statmodeling.stat.columbia.edu/2012/07/08/is-linear-regression-unethical-in-that-it-gives-more-weight-to-cases-that-are-far-from-the-average/}{this discussion post}, the argument is posed that there is no ethically neutral statistical method, with specific reference to linear regression. What is the basis for this argument? Do you agree or disagree? Why?
    \item Suppose a machine learning researcher at a company learns a model to automate the hiring process. This company sells software based on this model to other companies looking to expedite their hiring. However, it is later discovered that the algorithm heavily favors members of a certain class unfairly. 
    \begin{enumerate}[a)]
    \item In this situation, who should be to blame for the unfair hiring? 
    \item On whom does the responsibility fall to check the fairness of automated systems?
    \end{enumerate}
\end{itemize}


\subsection*{Grading Breakdown}
We expect that the \texttt{LinearRegression} model should have a training loss of less than 0.55 on the training dataset.

\medskip
As always, you will primarily be graded on the correctness of your code and not based on whether it does or does not achieve the accuracy targets.

\medskip
The grading breakdown for the assignment is as follows:
\begin{center}
\begin{tabular}{| l | r |}
	\hline
	Written Assignment & 25 points \\
	Programming & 19 points \\
	Report & 13 points \\
	\hline
	Total & 57 points \\
	\hline
\end{tabular}
\end{center}

\subsection*{Handing in}
You will hand in both the written assignment and the coding portion on gradescope, separately. 

The your written assignment will be uploaded to gradescope under "Homework 2". Submit your hw2 github repo containing all your source code and your project report on gradescope under "Homework 2 Code". For questions, please consult the \href{https://docs.google.com/document/d/1RbsJ_IKfzuAyL7yDma4Z7bCVTwiNJfPAHbBAd2WeIEE/edit?usp=sharing}{download/submission guide}.

\medskip
If you have questions on how to set up or use Gradescope, ask on Edstem! For this assignment, you should have written answers for Problems 1, 2, 3, 4, and 5.


\subsubsection*{Anonymous Grading}

You need to be graded anonymously, so do not write your name anywhere on your handin. 


\subsection*{Academic Integrity}
The \href{https://cs.brown.edu/courses/csci1420/assets/docs/collaboration.pdf}{CSCI 1420 Collaboration Policy} applies to this assignment.
As outlined in the \href{https://college.brown.edu/design-your-education/academic-policies/academic-code}{Brown Academic Code} and the \href{https://graduateschool.brown.edu/academics-research/rules-regulations/academic-code}{Brown Academic Code, Graduate Student Edition}, attempting to pass off another's work or AI-generated work as your own can result in failing the assignment, failing this course, or even dismissal or expulsion from Brown.  More than that, you will be missing out on the goal of your education, which is the cultivation of your own mind, thoughts, and abilities.  Please review this course's collaboration policy and if you have any questions, please contact the instructor.
\end{document}
