6.6.1 Linear Regression

In statistics we use two different names for tasks that map some input features into some output value: we use the word regression when the output is real-valued, and classification when the output is one of a discrete set of classes.

You may already be familiar with linear regression from a statistics class. The idea is that we are given a set of observations, each observation associated with some features, and we want to predict some real-valued outcome for each observation. Let's see an example from the domain of predicting housing prices. Levitt and Dubner (2005) showed that the words used in a real estate ad can be used as a good predictor of whether a house will sell for more or less than its asking price. They showed, for example, that houses whose real estate ads had words like fantastic, cute, or charming, tended to sell for lower prices, while houses whose ads had words like maple and granite tended to sell for higher prices. Their hypothesis was that real estate agents used vague positive words like fantastic to mask the lack of any specific positive qualities in the house. Just for pedagogical purposes, we created the fake data in Fig. 6.17.

| Number of vague adjectives | Amount house sold over asking price |

| --- | --- |

| 4 | 0 |

| 3 | $1000 |

| 2 | $1500 |

| 2 | $6000 |

| 1 | $14000 |

| 0 | $18000 |

Fig. 6.18 shows a graph of these points, with the feature (# of adjectives) on the x-axis, and the price on the y-axis. We have also plotted a regression line, which is the line that best fits the observed data. The equation of any line is $ y = mx + b $; as we show on the graph, the slope of this line is m = -4900, while the intercept is 16550. We can think of these two parameters of this line (slope m and intercept b) as a set of weights that we use to map from our features (in this case x, numbers of adjectives) to our output value y (in this case price). We can represent this linear function using w to refer to weights as follows:

$$ price=w_{0}+w_{1}*Num\_Adjectives $$

Thus Eq. 6.46 gives us a linear function that lets us estimate the sales price for any number of these adjectives. For example, how much would we expect a house whose ad has 5 adjectives to sell for?

The true power of linear models comes when we use more than one feature (technically we call this multiple linear regression). For example, the final house price probably depends on many factors such as the average mortgage rate that month, the number of unsold houses on the market, and many other such factors. We could encode each of these as a variable, and the importance of each factor would be the weight on that variable, as follows:

$$ price=w_{0}+w_{1}*Num\_Adjectives+w_{2}*Mortgage~Rate+w_{3}*Num\_Unsold\_Houses $$

In speech and language processing, we often call each of these predictive factors like the number of adjectives or the mortgage rate a feature. We represent each observation (each house for sale) by a vector of these features. Suppose a house has 1 adjective in its ad, and the mortgage rate was 6.5 and there were 10,000 unsold houses in the city. The feature vector for the house would be $ \vec{f} = (1, 6.5, 10000) $. Suppose the weight vector that we had previously learned for this task was $ \vec{w} = (w_0, w_1, w_2, w_3) = (18000, -5000, -3000, -1.8) $. Then the predicted value for this house would be computed by multiplying each feature by its weight:

$$ price=w_{0}+\sum_{i=1}^{N}w_{i}\times f_{i} $$

In general we will pretend that there is an extra feature $f_{0}$ which has the value 1, an intercept feature, which make the equations simpler with regard to that pesky $w_{0}$, and so in general we can represent a linear regression for estimating the value of y as:

$$ y=\sum_{i=0}^{N}w_{i}\times f_{i} $$

linear regression:

Taking two vectors and creating a scalar by multiplying each element in a pairwise fashion and summing the results is called the dot product. Recall that the dot product $ a \cdot b $ between two vectors a and b is defined as:

dot product:

$$ a\cdot b=\sum_{i=1}^{N}a_{i}b_{i}=a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n} $$

Thus Eq. 6.49 is equivalent to the dot product between the weights vector and the feature vector:

$$ y=w\cdot f $$

Vector dot products occur very frequently in speech and language processing; we will often rely on the dot product notation to avoid the messy summation signs.

Learning in linear regression

How do we learn the weights for linear regression? Intuitively we'd like to choose weights that make the estimated values y as close as possible to the actual values that we saw in the training set.

Consider a particular instance $x^{(j)}$ from the training set (we'll use superscripts in parentheses to represent training instances), which has an observed label in the training set $y_{obs}^{(j)}$. Our linear regression model predicts a value for $y^{(j)}$ as follows:

$$ y_{pred}^{(j)}=\sum_{i=0}^{N}w_{i}\times f_{i}^{(j)} $$

We’d like to choose the whole set of weights $ W $ so as to minimize the difference between the predicted value $ y_{\text{pred}}^{(j)} $ and the observed value $ y_{\text{obs}}^{(j)} $, and we want this difference minimized over all the $ M $ examples in our training set. Actually we want to minimize the absolute value of the difference (since we don’t want a negative distance in one example to cancel out a positive difference in another example), so for simplicity (and differentiability) we minimize the square of the difference. Thus the total value we want to minimize, which we call the \textit{sum-squared error}, is this cost function of the current set of weights $ W $:

$$ cost(W)=\sum_{j=0}^{M}\left(y_{pred}^{(j)}-y_{obs}^{(j)}\right)^{2} $$

We won’t give here the details of choosing the optimal set of weights to minimize the sum-squared error. But, briefly, it turns out that if we put the entire training set into a single matrix X with each row in the matrix consisting of the vector of features associated with each observation $x^{(i)}$, and put all the observed $y$ values in a vector $\vec{y}$, that there is a closed-form formula for the optimal weight values W which will minimize cost(W):

$$ \boldsymbol{W}=(\boldsymbol{X}^{T}\boldsymbol{X})^{-1}\boldsymbol{X}^{T}\vec{y} $$

Implementations of this equation are widely available in statistical packages like SPSS or R.