<jupyter_start><jupyter_text>Linear modelsIn this notebook I will try and implement linear regression for 2-dim data and some of it's basic implementations, such as: -LSM-Gradient descent-Stohastic Gradient descent-Gradient descent with momentum-Nesterov Accelerated Gradient descent-AdaGrad-AdaDelta@article {url = {https://ruder.io/optimizing-gradient-descent/index.htmlstochasticgradientdescent}}@article {url = {https://habr.com/ru/post/318970/}}@article {url = {https://ruder.io/optimizing-gradient-descent/index.htmlstochasticgradientdescent}}  Step 1: generating data<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
np.random.seed(0) # fix seed for reproducibility.

mean = [-1, 1] # mean of normal distribution. Try others.
cov = [[1, -0.8], 
       [-0.8, 1]] # covariance of normal distribution
sample = np.random.multivariate_normal(mean, cov, size=1000) # 1000 normally distributed samples

# TODO: compare with normalized normal distribution; also with other distributions; also add outliers
plt.rcParams['figure.figsize'] = [15,8]

x, y = sample[:, 0], sample[:, 1]  # separate samples on feature x and target y

# Visualize dataset
plt.scatter(x, y)
plt.xlabel('x')
plt.ylabel('y')
plt.show()
X = np.array([np.array([1, xi]) for xi in x])
X[:3], y[:3], X.shape, y.shape<jupyter_output><empty_output><jupyter_text>Some basic functions-prediction ( X, theta): $y = \theta^TX$ -MSE score (y, $\hat{y}$)<jupyter_code>def predict(X, theta):
    return np.dot(X, theta)

def l2_score(y, y_hat):
    return sum((y - y_hat) ** 2) / (2 * len(y))<jupyter_output><empty_output><jupyter_text>Simple MSENote: This is an analytical algorhytm. Thought it finds the best solution, it's complexity is: O(n) = $(n^\theta) + n^{2.4} $<jupyter_code>def MSE_weights(X, y):
    return np.linalg.inv(X.T @ X) @ (X.T @ y)
theta_mse = MSE_weights(X, y)

#plot
edges = np.array([x.min(), x.max()])
line = theta_mse[0] + theta_mse[1] * edges
plt.plot(edges, line, 'r-')
plt.scatter(x, y)
plt.xlabel('x')
plt.ylabel('y')
plt.show()<jupyter_output><empty_output><jupyter_text>MSE scoreThis is as good as it gets<jupyter_code>prediction = predict(X, theta_mse)
l2_score(prediction, y)<jupyter_output><empty_output><jupyter_text>Gradient descentThe main idea behind gradient descent is that we can easily find the direction of function's fastest decrease - Jacobian matrix transforms our space so that (1, 1, ..., 1) turns into the fector pointing to the fastest increase direction. We multiply it by -1 and get decrease.$\theta = \theta + \alpha \nabla J(\theta)$$\nabla J(\theta) = \sum_m(y - h_\theta(X))X$Note: $ O(n) = i * n^3 $<jupyter_code>class GradientDescent:
    def __init__(self, X, y, l_rate=0.001, iters=100, starting_point=np.array([0]*2)):
        self.le_rate = l_rate
        self.iters = iters
        self.starting_point = starting_point
        self.X = X
        self.y = y
    
    def fit(self): 
        theta = np.array(self.starting_point) # init theta with any scalar or vector
        m = len(X)
        history = [theta] # list of theta values on each iteration 
        cost = [l2_score(y, predict(X, theta))] # list of cost function values on each iteration
    
        for i in range(self.iters):
            history.append(theta)
            cost.append(l2_score(y, predict(X, theta)))
            theta = theta + self.le_rate * (np.sum((y - np.dot(X, theta.T)) * X.T, axis = 1)) # gradient descent itself, vectorized
            
            
        self.theta, self.cost, self.history = theta, np.array(cost), np.array(history)
        
    def predict(self):
        return self.theta, np.array(self.cost), np.array(self.history)


gd = GradientDescent(X, y, 0.0001, 100, [5, 10])
gd.fit()
gd_theta, gd_cost, gd_hishory = gd.predict()


extremes = np.array([np.min(x), np.max(x)])
line = gd_theta[0] + extremes * gd_theta[1]
plt.plot(extremes, line, 'r-')
plt.scatter(x, y)
plt.xlabel('x')
plt.ylabel('y')
plt.show()
prediction = predict(X, gd_theta)
l2_score(prediction, y)<jupyter_output><empty_output><jupyter_text>FOR FURTHER EXTENSIONS HERE  Stohastic gradient<jupyter_code>class StohasticGD:
    def __init__(self, X, y, le_rate, starting_point, iters=100, batch_size=1):
        self.X = X
        self.y = y
        self.le_rate = le_rate
        self.iters = iters
        self.starting_point = starting_point
        self.batch_size = batch_size
    
    
    def fit(self):
        theta = np.array(self.starting_point)
        history = []
        cost = []
        data = []
        
        for i in range(self.iters):
            history.append(theta)
            cost.append(l2_score(predict(self.X, theta), self.y))
            batch_indeces = np.random.choice(X.shape[0], size=self.batch_size, replace=False)
            data.append((self.X[batch_indeces][:,1], self.y[batch_indeces]))
            
            theta = theta + self.le_rate * (np.sum((y[batch_indeces] - np.dot(X[batch_indeces], theta.T))\
                                                   * X[batch_indeces].T, axis = 1))
            
        return theta, np.array(cost), np.array(history), np.array(data)
sgd = StohasticGD(X, y, 0.001, [5, 10], iters=10000, batch_size=5)
sgd_theta, sgd_cost, sgd_hishory, sgd_data = sgd.fit()
print(sgd_theta)

prediction = predict(X, sgd_theta)
score = l2_score(prediction, y)
print(score)

extremes = np.array([np.min(x), np.max(x)])
line = sgd_theta[0] + extremes * sgd_theta[1]
plt.plot(extremes, line, 'r-')
plt.scatter(x, y)
plt.xlabel('x')
plt.ylabel('y')
plt.show()<jupyter_output>[ 0.2010682  -0.75904178]
0.17265632537588804
{'fraction_non_alphanumeric': 0.1421193232413179, 'fraction_numerical': 0.023330365093499554, 'mean_word_length': 3.507223113964687, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 24, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '501467', 'license': 'MIT', 'n_tokens_mistral': 2144, 'n_tokens_neox': 1989, 'n_words': 483, 'path': 'Linear_models.ipynb', 'repo_name': 'EgorAbrosimov-creativity/optimizationHandsOn', 'size': '5615'}