Gradient Vectors in Optimization

Lecture 3: Optimisation Theory

• This section examines optimisation theory, focusing on continuous and differentiable functions.
• The core problem is to find the w that minimises or maximises f(w).
• The function f is often a loss function, measuring the difference between model predictions and actual values.
• Minimising the loss function leads to the best model within a set of models.

1.1 Basic Definitions

• Gradient: The gradient of a differentiable function f : Rd → R is a function ∇f: Rd → Rd, defined by the partial derivatives of f with respect to each component of w.
• Directional Derivative: The directional derivative Vuf(w) represents the rate of change of f at w in the direction of the unit vector u. This is helpful for finding the direction of maximum increase.
• Hessian Matrix: The Hessian matrix H(w) is a square matrix of the second-order partial derivative of f, providing information about the curvature of the function. It's symmetric for twice continuously differentiable functions.

Taylor Expansion

• The Taylor expansion approximates a differentiable function around a point w_k.
• The expansion can be used to approximate the function at other nearby points.

Positive and Negative Definiteness

• A symmetric matrix B is called positive definite if w^TBw > 0 for any vector w ≠ 0.
• A symmetric matrix B is called negative definite if w^TBw < 0 for any vector w ≠ 0.

Quadratic functions

• Quadratic functions are common in data science, often appearing as loss functions.
• They are represented by scalar equations, vector equations, and Taylor expansions, all equivalent in their representation.
• Several forms for quadratic functions can be useful in their application.

Necessary and Sufficient Conditions for an Optimum

• Necessary conditions for an optimum of a function involve the gradient being zero at the optimum point.
• Sufficient conditions for a minimum require that the Hessian is positive definite.
• Sufficient conditions for a maximum require that the Hessian is negative definite.
• Points where the gradient is zero can be a local maximum, minimum, or a saddle point.
• A continuous function on a closed and bounded subset S of Rd will have both a global maximum and minimum.

Lecture 4: Gradient Descent Methods

• The goal is to optimise functions of the form f : Rd → R, such as cost functions relating model fit to data.
• Gradient descent is used to tackle optimisation problems defined as non-analytically solvable or to avoid complex analytical calculations, finding optima of differentiable functions.
• Euclidean ball: The Euclidean ball represents a neighborhood around a point in ℝ^d.
• Local and global minima/maxima: Local extrema are the extreme values of a function within any local neighborhood of a point. Global extrema are the extreme values of a function over its entire domain.

Distances

• A distance is a non-negative number between two points.
• A distance between x and y is |a| multiplied by the distance, where ‘a’ is any real number.
• The distance between two points x and y is not greater than the sum of the distance between them and a third point z.
• p-norms: A type of distance measure useful in many application areas.

Convex Functions

• A function f is convex if for all p, q∈ Rd, any point on the line segment between p and q has a value less than or equal to the weighted average of f(p) and f(q).
• A strictly convex function is when the inequality is strictly less than.
  • Convexity is a crucial concept in understanding the properties of loss functions.

Lecture 5: Properties of Loss Functions

• Distance measures: The definition of a loss function depends on a choice of distance measure.
• Different distances between model predictions and data points will result in model optima in different locations.
• A loss function's behaviour and properties can depend on its specific form.

Lecture 6: Important Probability Densities

• Normal probability density function (or Gaussian): A distribution over the set of real numbers with an important role in many fields of application.
• Univariate normal density: A specific type of normal distribution.
• Multivariate normal probability density function: A generalisation of the normal distribution to several random variables.

Lecture 4.6: Maximum Likelihood Method

• It estimates parameters in a probability model, given a set of observations.
• Maximising the probability or probability density of observing this data with respect to the parameters is the key concept.

Lecture 4.7: Conditional Likelihood Method

• This estimates conditional probability densities, especially useful when a subset of variables is used to predict another.
• This is done often by considering a probability density for the entire set of random variables, then separating this by marginal probability and conditional probability distributions.
• This calculation can be crucial in practical applications.

Lecture 4.4: Expectation, Variance, and Covariance

• In statistical distributions, these are important measures to determine measures of location, dispersion, and relationship between variables in the dataset.
• Expectation: The expected value is the average outcome.
• Covariance: Measures the linear relationship between two random variables.

Lecture 4.5: Important Probability Densities

• Overview of specific probability distributions, including Gaussian (normal) distributions, which are extremely important in data science.
• Describes the probability density function for a multivariate (k-dimensional) case.

Lecture 7: Linear Regression & Normal Equation

• Linear Regression: A model that describes a linear relationship between dependent and independent variables in a data set.
• Normal Equation: A method of finding optimal weight parameters in a linear regression model (explicit solution). It's used when the input features matrix has linearly independent columns.
• Coefficients: The parameters that determine the relationship between the variables in the dataset, as found from solving the normal equation.

Gradient Descent

• Finding optimal parameters in a function to minimize it.
• An iterative approach that calculates the gradient of the loss function and moves in the opposite direction to reduce the function's value.
• Different variations include stochastic and mini-batch gradient descent approaches, which provide significant speed improvements over traditional batch gradient descent in large dataset contexts.

Additional Study Materials

• Dataset scaling: Normalizing and standardizing the datasets to improve convergence in gradient-based solutions.
• Polynomial Regression: Extending linear regression to models with higher-degree polynomials, which improves fit where the relationship between variables is not linear.
• Cost Function: Metrics used to evaluate and optimise the model, with examples of Mean Squared Error (MSE).
• Data: Splitting the dataset into training, validation, and test sets to evaluate model ability (generalization) on unseen data.
• Hyperparameters: Values that affect a learning model’s output but aren't part of the process of learning from data (e.g. regularization coefficient).

Cross-Validation

• A technique that uses the same dataset to both evaluate and train a model that prevents overfitting
• Used to select optimal hyperparameter settings when optimizing machine learning models.

Grid Search

• A technique that systematically tries different combinations of hyperparameter values to locate optimal values for best model performance.

Early Stopping

• A method used to stop gradient descent based training when the model optimization stops improving for unseen data to stop overfitting.

Ensemble Learning – XGBoost

• An advanced tree-based model that leverages the power of several decision trees to increase predictive accuracy beyond what can be achieved by single trees alone. This can be accomplished by adjusting hyperparameters.
• Bootstrapping (bagging): This is a method of obtaining several learners by selecting samples from the same original dataset with replacement.
• Decision trees: In a decision tree, data points (e.g. of customers) are sorted using threshold values from a variety of attributes (e.g. age, gender, etc.).
• CART (classification and regression trees): A variation of decision trees that handles both classification/regression tasks.
• Tree boosting: A sequence of trees being trained in a specific order to correct errors from earlier trees and improve accuracy overall

Neural Networks

• Multiple layer perceptrons (MLP)
  • Activation functions: Different functions used in activation of a neuron (e.g. sigmoid, ReLU), affect processing in the network and influence training algorithms.
• Computational graphs: Represent neural networks, aiding in backpropagation, which is essential for computing the gradients needed during optimisation.
• Training and implementation practices
  • Initialization: Random initialization is often necessary, to avoid biases and symmetry issues. Other strategies may be more effective in preventing vanishing or exploding gradients.
  • Regularization: Improves generalization performance by penalizing models that are too complex to improve the accuracy on unseen data.
• Important aspects of MLP construction and application to data:
  • Network structure: Depth (number of layers), width (number of units in the hidden layers) impact the model capabilities.
• More general:
  • Hyperparameter tuning: Adjusting models’ parameters to improve performance on new data. This involves finding the best combination of values.
• Basic ideas for NN optimization:
  • Gradient descent: Numerical computation is used to find minima in a cost function.
  • Back-propagation: A key step in training NN. It computes the gradients needed to adjust weights and biases during optimization

This quiz explores the role of gradient vectors in the field of optimization. You'll learn how these vectors define direction and magnitude for improving function values, which is crucial in various optimization techniques. Test your understanding of gradients and their application in mathematical optimization.