1 Linear Regression and Convexity
The loss function of linear regression is
L(w) = ||y − Xw||22 = (y − Xw)T(y − Xw) = (yT − wTXT)(y − Xw)
= wTXTXw − wTXTy − yTXw + yTy
hence
Therefore, ∇wL(w) = 2XTXw − 2XTy, ∇2wL(w) = ∇w(∇wL(w)) = 2XTX ≥ 0. Hence, is a convex function.
2 Gaussian Distribution and the Curse of Dimensionality
2.2
The equation ) works for
4πr2 = S3−1(r).
Intuitively, this equation should hold for ∀m ∈ N,n ≥ 2. Consider Vm(r + ∆r) − Vm(r), which is equivalent to the volume of an m-d spherical shell that is outside of the sphere with radius r and inside of the sphere with radius r + ∆r. When ∆r → 0, the shell can be approximated by a plate with base area Sm−1(r) and thickness ∆r, i.e., Vm(r + ∆r) − Vm(r) → Sm−1(r)∆r when r → 0, therefore
2.3
We know that Vm(r) is only dependent on rm, in other words, (1). We also know from
2.2 that
When r = 1, S¯m−1 = Sm−1(r) = mVm(1), hence Sm−1(r) = rm−1 (mVm(1)) = rm−1S¯m−1.
2.4
Because ||x||2 = r,
2.5
Let . When ; when
as r ↗. Therefore, ρm(r) is maximal if and only if√ √ r = rˆ. √ √
On the other hand, when m → ∞, m − 1 → m, hence ˆr = m − 1σ → mσ.
2.6
2
We know , where (1+
)). By Taylor’s expansion, ln(1 + . We know that ϵ ≪ rˆ, hence 0,
). Therefore, ),
2.7
As we learned in 2.5, when we are sampling from a high-dimensional Gaussian distribution, i.e., m is large enough,
√
ρm(r) is maximal when√ r = rˆ ≈ mσ > σ, hence most of the sampled points reside out of the σ neighborhood, at radius ˆr ≈ mσ. √
When we sample from a low-dimensional Gaussian distribution,√ ρm(r) is maximal when r = m − 1σ. When m ∈ {1,2}, 0 ≤ m − 1σ ≤ σ, hence most of the sampled points reside within the σ neighborhood.
2.8
When x is at the origin, ; when x is on the sphere of radius ˆ
). The probability density at ||x||2 = rˆ is much smaller than that of ||x||2 = 0. However, ρm(rˆ) >
ρm(0) because as r ↗, Sm−1(r) grows much faster than pr(x) decreases.
To verify my conjecture, I sampled 100 points from Gaussian distributions Nm(0,1) where m = 1,2…40, calculating the means and standard deviations in each group and plotted the two metrics as functions of m. The results are as follows:
√ √
From Figure 1, we observe that Avg{||x||2} ∝ m (actually, Avg√{||x||2} ≈ m), which is consistent with our
conjecture that most of the sampled points reside around the radii mσ for any m.
The standard deviation of the norms does not change significantly as m increases, which implies that the standard deviation is likely to be independent of the dimension of the distribution.
Figure 1: means and standard deviations of 100 sampled points from Gaussian distributions of dimensions 1-40.
3 Ridge Regression
3.1
When (X,y) are strongly linearly correlated, standard linear regression is preferrable over ridge regression. The illustration is as follows:
Figure 2: Setting 1 of (X,y) and the corresponding linear regression and ridge regression model.
This is because the fitting of data can be nicely down simply by minimizing the objective , whereas the penalty of ridge regression on the norms of weights prevents the minimization, which results in a worse fit of the data points.
3.2
When there are outliers in (X,y), the linear regression model can be highly sensitive to the outliers, while the ridge regression model remains robust and fit the majority of the points (as shown in Figure 3). Therefore, ridge regression is preferrable over linear regression when there does not exist a strong linear relation among all the data in (X,y).
Figure 3: Setting 2 of (X,y) and the corresponding linear regression and ridge regression model.
3.3
, from 1, we know ∇wLRidge(w) = 2XT(Xw − y) + ηIw where η > 0, thus
0, so LRidge(w) is a convex function.
T
Let ∇wLRidge(w) = 0, then we have (2XTX+ηI)w = 2XTy, henceTherefore, the close-form solution of ridge regression is (2XTX + ηI)−12XTy.
3.4
(a)
Under the extreme case of multicollinearity, where some features are identical to others, the columns of the matrix XT will no longer be linearly independent. Consequently, det(XTX) = det(XT)det(X) = 0, therefore XTX is not invertible. Considering the closed-form solution to vanilla linear regression (XTX)−1XTy requires to take the inversion of XTX, we will no longer be able to compute this solution.
(b)
Because (XTX)T = (X)T(XT)T = XTX, XTX is a symmetric matrix, hence XTX is orthogonally diagonalizable, i.e., XTX can be decomposed as XTX = V −1ΣV where V is orthogonal and Σ is a diagonal matrix.
On the other hand, V −1V = V −1IV , hence 2XTX + ηI = V −1(2Σ + ηI)V . We know from the last problem that det(XTX) can be 0, which makes it impossible to calculate the closed-form solution to vanilla linear regression.
Therefore, det(XTX) = det(V −1)det(Σ)det(V ) = 0, where det(V −1),det(V ) ̸= 0, hence det(Σ) = 0. Let Σ =
Σ1 2Σ1 + η
Σ2 2Σ2 + η
… , where Π = 0, then 2Σ + ηI = … . When η is large
Σk 2Σk + η enough ( 0, hence det(2XTX+ηI) = det(V −1)det(2Σ+ηI)det(V ) > 0, 2XTX +ηI is invertible, hence the closed-form solution of ridge regression can always be obtained when η is large enough.
This implies another benefit of using ridge regression is that when the dataset suffers from multicollinearity, ridge regression can always be used to obtain a solution.
4 Locality Sensitive Hashing (LSH)
4.1
We set c = 1 and perform a binary search of r in the range [0,m] until for some r the query returns nothing, and for r + 1, the query returns some point x′. The returned point x′ is the nearest neighbor of q. The time complexity of this algorithm is O(logm), and the query is called for at worst 2logm times.
4.2
Assume d(xi,xj) = r′, then , then Pr(h(xi) = h(xj)) =
. Because . Similarly, when .
4.3
When d(xi,xj) ≤ r,
Pr(g(xi) = g(xj)) = Pr(h1(xi) = h1(xj) ∧ h2(xi) = h2(xj) ∧ ··· ∧ hk(xi) = hk(xj))
= Pr(xi[a1] = xj[a1] ∧ xi[a2] = xj[a2] ∧ ··· ∧ xi[ak] = xj[ak]) = Pr(xi[a1] = xj[a1])Pr(xi[a2] = xj[a2])…Pr(xi[ak] = xj[ak]) ≥ pk1
Similarly, when .
4.4
Pr(∃b,gb(xi) = gb(xj)) = Pr(g0(xi) = g0(xj) ∨ g1(xi) = g1(xj) ∨ ··· ∨ gl−1(xi) = gl−1(xj))
= 1 − Pr(g0(xi) ̸= g0(x) ∧ g1(xi) ̸= g1(x) ∧ ··· ∧ gl−1(xi) ̸= gl−1(x))
= 1 − Πlb−=01(1 − Pr(gb(xi) = gb(xj)))
When ; when .
4.5
(a) Because d(x′,q) ≤ r, we know from 4.4 that
ln(p )
where . Let , because (1 ,
.
(b) Let X be the number of x’s in X such that d(x,q) ≥ cr and gb(x) = gb(q). By Markov inequality, Pr(X ≥ 4l) ≤ . We know
Therefore, .
(c) Now we consider the scenario where both events happen. Because for any data point x ∈ X, it is impossible that d(x,q) ≤ r while d(x,q) ≥ cr, hence the domain of the two events are disjoint, the two events are independent. Therefore, lower bound of the probability that both events happen is equal to
4.6
We know that the second event in 4.5 happend with certainty, i.e., there are at most 4l x’s ∈ X such that gb(x) = gb(q),d(x,q) ≥ cr. Therefore, we need to check at least 4l + 1 points from the collected points to guarantee we can have a point x′ such that gb(x′) = gb(q),d(x′,q) ≤ cr.
On the other hand, we are guaranteed that such a data point x′ exists, because the first event in 4.5 happen for certain, i.e., ∃x′ ∈ X,b ∈ {0,1,…,l − 1} such that gb(x′) = gb(q),d(x′,q) ≤ r → d(x′,q) ≤ cr.
5 Programming Problem: Linear Regression
5.1
After checking all the scatter plots, we picked out the three features that look the most linearly related to price on the scatter plots: LSTAT, RM, and INDUS. The plots are as follows:
Figure 4: Scatter plots of LSTAT vs MEDV(left), RM vs MEDV(middle), and INDUS vs MEDV(right)
5.2
According to the correlation matrix, the 3 features that are most linearly related to the house price are: LSTAT(r = −0.74), RM(r = 0.7), and PTRATIO(r = −0.51). This is slightly different from our results in 5.1, but the discrepancy is understandable, as the difference between the Pearson scores of PTRATIO(r = −0.51) and INDUS(r = −0.48) is very small.
5.3
According to 3.3, we can know the closed-form solution to linear regression min and ridge regression are w = (XTX)−1XTy and w = (2XTX + ηI)2XTy, respectively.
After implementing these two solutions in Python, we obtained the coefficients corresponding to each feature as follows:
Consider the absolute values of the coefficients, as η ↗, the larger absolute values get smaller (like CHAS and RM), whereas the smaller absolute values get larger (like INDUS). In other words, larger η leads to the averaging of the norms of the regression weights.
η linear regression ridge regression
features 0 15.0 45.0 90.0
CRIM -0.099324 -0.100648 -0.101396 -0.101484
ZN 0.052251 0.054632 0.059028 0.062642
INDUS 0.004516 0.012958 0.018062 0.020644
CHAS 2.957261 2.272783 1.575958 1.107609
NOX 1.127938 0.457674 0.343826 0.287127
RM 5.854198 5.728152 5.424074 5.008160
AGE -0.014957 -0.010094 -0.002772 0.006178
DIS -0.920844 -0.896985 -0.842988 -0.770484
RAD 0.159519 0.163084 0.164232 0.162159
TAX -0.008934 -0.008982 -0.008940 -0.008670
PTRATIO -0.435674 -0.406149 -0.345226 -0.260870
B 0.014905 0.015518 0.016406 0.017465
LSTAT -0.474751 -0.484274 -0.506287 -0.534369
Table 1: The coefficients corresponding to different features under different η’s. Note linear regression can be viewed as a special case of ridge regression where η = 0.
5.4
We calculated the root mean square error (RMSE) of train and test set under different η’s according to the formula . The result are as follows:
η linear regression ridge regression
dataset 0 15.0 45.0 90.0
train set 4.8206 4.8263 4.8526 4.9076 test set 5.2092 5.1912 5.1895 5.2128
Table 2: RMSE of train set and test set under different η’s.Note linear regression can be viewed as a special case of ridge regression where η = 0.
It is worth noticing that as η gets larger, the train set RMSE gets larger as well, whereas the test set RMSE decreases at first and increases at the end.
A possible explanation to this phenomenon is: on the train set, RMSE is perfectly consistent with the objective of linear regression, therefore linear regression results in a smaller RMSE than ridge regression; on the test set, the penalty of ridge regression on large weights improves the generalizability of the model, therefore the RMSE on test set is smaller when η gets larger. However, when η is too large, the model will focus too much on minimizing the weights instead of fitting the data points, resulting in high RMSE on both train set and test set.
5.5
We picked out the 3 most significant features as noted in 5.3, clipped the data by keeping only those 3 features, and trained a linear regression model and a ridge regression model (η = 45.0) on the clipped data. Afterwards, we calculated the RMSE on train and test set under the new model. The results are as follows:
Table 3: RMSE of train set and test set under different η’s.Note linear regression can be viewed as a special case of ridge regression where η = 0.
Compared to the RMSE we obtained in 5.4 where we used all 13 features for training and prediction, the RMSE obtained with only 3 features increases by at most 9%. This implies by using only the top3 most significant features to predict the house prices, we can still obtain a comaparable performance compared to that of using all features, while cutting down the dimension of the feature space and saving computing power considerably.
