<jupyter_start><jupyter_text>Applied Machine Learning Linear Models  Recap- We have some dataset- We identify the problem and define the loss function- Then we minimize the total loss (empirical risk, or objective) using available (training) data- We vary parameters to minimize the objective function- The minimizing parameters are then used to predict unknown values  A text classification problemLets consider the **20 newsgroups** dataset:<jupyter_code>from sklearn.datasets import fetch_20newsgroups
data = fetch_20newsgroups()
text, label = data['data'][0], data['target_names'][data['target'][0]]
print(label)
print('----')
print(text[:300])<jupyter_output>rec.autos
----
From: <EMAIL> (where's my thing)
Subject: WHAT car is this!?
Nntp-Posting-Host: rac3.wam.umd.edu
Organization: University of Maryland, College Park
Lines: 15

 I was wondering if anyone out there could enlighten me on this car I saw
the other day. It was a 2-door sports car, looked to be<jupyter_text>A linear model for classificationLet us consider a function that tells if the `text` comes from `rec.autos`<jupyter_code>weight('car')*has('car', text) + weight('dog')*has('dog', text) + rest<jupyter_output><empty_output><jupyter_text>Alternatively say `car` is `0` and `dog` is `1`:<jupyter_code>weight(0)*feature(0) + weight(1)*feature(1) + rest<jupyter_output><empty_output><jupyter_text>How do we find those `weight` ($w$) for all the words?  Gradient Descent- Last time we used `opt.fmin` and it magically found the solution- The method is simple though- Start with random weights $w_0$- Iterate: $w_{i+1} = w_{i} - \alpha \times \nabla \mathsf{objective}(w_i)$- All we need to know is the gradient of objective  Gradient of loss- Last time we considered a regression problem and used $(y-p)^2$- The gradient w.r.t $p$ is obvious: $- 2 (y - p)$  Gradient checkHow can we ensure the gradient is correct?<jupyter_code>def loss(y, p):
    return (y-p)**2

def gradient(y, p):
    return -2*(y-p)

p = 0.1
y = 0.3
eps = 0.001
gradient(y, p), (loss(y, p+eps) - loss(y, p-eps)) / (2*eps)<jupyter_output><empty_output><jupyter_text>Gradient descent in code<jupyter_code>current_p = random.random()
alpha = 0.1

for i in range(5):
    current_p = current_p - alpha*gradient(y, current_p)
    print(i, current_p)
current_p = random.random()
alpha = 0.1

xs = list(range(20))
ys = []
for _ in xs:
    current_p = current_p - alpha*gradient(y, current_p)
    ys.append(current_p)
    
plt.plot(xs, ys); plt.hlines(y, xs[0], xs[-1]);<jupyter_output><empty_output><jupyter_text>Classification loss- We will use something called **logistic loss**<jupyter_code>def loss(y, p):
    return np.log2(1.0 + np.exp(-y*p))
    
loss(-1, -100.0), loss(-1, +100.0)<jupyter_output><empty_output><jupyter_text>Logistic Regression in sklearn<jupyter_code>model = sklearn.linear_model.SGDClassifier(loss='log', tol=1e-6)
example_1 = [1,0]; label_1 = [1]
example_2 = [0,1]; label_2 = [0]
model.fit([example_1, example_2], np.ravel([label_1, label_2]))
model.coef_<jupyter_output><empty_output><jupyter_text>Overfitting- We can always come up with a model that fits data perfectly<jupyter_code>weight('<EMAIL>')<jupyter_output><empty_output><jupyter_text>- For some reason that's not what we want. Why?- First, we need to measure if such a thing happens  Splitting the data- Obviously we should not test what we fit against- We should fit (train) the model on some part of data- Next, we check the model against the rest  Leave-on-out- Generate as many samples as there are examples- Gives you a good estimate if you don't have a lot of data- Gets impractical on huge datasets<jupyter_code>loo = sklearn.model_selection.LeaveOneOut()
for train, test in loo.split([1,2,3,4,5]):
    print(train, test)<jupyter_output><empty_output><jupyter_text>Cross validation- Split the dataset into a few (say 5) non-overlapping parts- Four parts go to training data and one part goes to test data- Do the above 5 times to train the model and test it- Makes a decent way to *detect* overfitting  Cross validation in sklearnLet's consider indices of data<jupyter_code>xval = sklearn.model_selection.KFold(n_splits=3)
for train, test in xval.split([1,2,3,4,5,6]):
    print(train, test)<jupyter_output>[2 3 4 5] [0 1]
[0 1 4 5] [2 3]
[0 1 2 3] [4 5]<jupyter_text>This thing is an ill-posed problem- A mathematical problem is ill-posed when the solution is not unique- That's exactly the case of regression/classification/...- We need to make the problem well-posed: *regularization*  Structural risk minimization- Structural risk is empirical risk plus regularizer- Instead of minimizing empirical risk we find some tradeoff- Regularizer is a function of model we get- $\mathsf{objective} = \mathsf{loss} + \mathsf{regularizer}$  Regularizer- A functions that reflects the complexity of a model- What is the complexity of a set of 'if ... then'?- Not obvious for linear model but easy to invent something  $\ell_1$ regularizer- Derivative is const- Forces weight to be zero if it doesn't hurt performance much - Use if you believe some features are useless<jupyter_code>classification_model = sklearn.linear_model.SGDClassifier(loss='log', penalty='l1');
regression_model = sklearn.linear_model.SGDRegressor(penalty='l1');<jupyter_output><empty_output><jupyter_text>$\ell_2$ regularizer- Derivative is linear- Forces weights to get *similar* magnitude if it doesn't hurt performance much- Use if you believe all features are more or less important<jupyter_code>classification_model = sklearn.linear_model.SGDClassifier(loss='log', penalty='l2');
regression_model = sklearn.linear_model.SGDRegressor(penalty='l2');<jupyter_output><empty_output><jupyter_text>Elastic net- Just a weighted sum of $\ell_1$ and $\ell_2$ regularizers- An attempt to get useful properties of both<jupyter_code>regression_model = sklearn.linear_model.SGDRegressor(penalty='elasticnet')<jupyter_output><empty_output><jupyter_text>Limitations of linearity- In low-dimensional spaces linear models are not very 'powerful' (can we define that?)- The higher dimensionality, the more powerful linear model becomes  Sparse features- We say features are sparse when most of the values are zero- Examples: visited hosts, movies that user liked, ...- Sparse features are efficient in high-dimensional setting<jupyter_code>[0, 0, ..., 1, ..., 0, 0, 1, 0];<jupyter_output><empty_output><jupyter_text>One hot encoding, hashing trick- One way to encode categorical things like visited hosts- We enumerate all the hosts- We put 1 to position of every host, 0 otherwise- Hashing trick: instead of enumerating them just hash<jupyter_code>print(hash('hse.ru'))
print(hash('hse.ru') % 2**16)<jupyter_output><empty_output><jupyter_text>Hashing vectorizer in sklearn<jupyter_code>from sklearn.feature_extraction.text import HashingVectorizer

vectorizer = HashingVectorizer(n_features=10, binary=True)
features = vectorizer.fit_transform(['hello there', 'hey there'])
print(features.todense())<jupyter_output>[[0.         0.70710678 0.         0.         0.         0.
  0.         0.70710678 0.         0.        ]
 [0.         0.         0.         0.         0.70710678 0.
  0.         0.70710678 0.         0.        ]]
{'fraction_non_alphanumeric': 0.11031042128603104, 'fraction_numerical': 0.024944567627494457, 'mean_word_length': 4.925287356321839, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 64, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '622584', 'license': 'Apache-2.0', 'n_tokens_mistral': 2433, 'n_tokens_neox': 2288, 'n_words': 794, 'path': 'machine-learning/HSE-AML-2.ipynb', 'repo_name': 'alexlaw19/hse-coursera', 'size': '7238'}