Mathematics Dictionary

Automatic differentiation (autograd) is a computational technique that automatically calculates derivatives of functions defined by computer programs. Unlike symbolic differentiation (which manipulates mathematical expressions) or numerical differentiation (which approximates derivatives using finite differences), autograd computes exact derivatives efficiently by applying the chain rule systematically during program execution.

In machine learning, autograd is fundamental to training neural networks through gradient-based optimization. It enables frameworks like PyTorch, TensorFlow, and JAX to automatically compute gradients of loss functions with respect to model parameters, eliminating the need for manual derivative calculations. This automation is crucial for deep learning, where models may have millions or billions of parameters.

Autograd works by tracking operations performed on tensors and building a computational graph that records how outputs depend on inputs. During the backward pass, it traverses this graph in reverse order, applying the chain rule to compute gradients efficiently. This process, combined with backpropagation, enables the training of complex neural architectures that would be impractical to differentiate manually.

Modern autograd systems support both forward-mode and reverse-mode automatic differentiation, with reverse-mode (used in backpropagation) being particularly efficient for functions with many inputs and few outputs, which is typical in machine learning scenarios.

Simple Examples:

1. Strong Positive Correlation (r ≈ 0.9): Height and weight in a population. As height increases, weight tends to increase proportionally.

2. Moderate Positive Correlation (r ≈ 0.4): Study hours and test scores. More study time generally leads to better scores, but other factors also influence performance.

3. No Correlation (r ≈ 0): Shoe size and intelligence. These variables have no meaningful linear relationship.

4. Moderate Negative Correlation (r ≈ -0.4): Age of a car and its resale value. Older cars typically have lower resale values, though condition and other factors matter.

5. Strong Negative Correlation (r ≈ -0.8): Outdoor temperature and home heating usage. As temperature drops, heating usage increases substantially.

Also known as CANDECOMP/PARAFAC decomposition, CP breaks down a tensor into a sum of rank-one tensors (outer products of vectors). This decomposition provides a highly interpretable representation where each component represents a distinct pattern or factor in the data.

CP decomposition serves as a powerful unsupervised learning tool for discovering latent factors in multi-way data, with applications in chemometrics (analyzing chemical measurements), neuroscience (identifying functional networks), and recommendation systems (capturing user-item-context interactions).

A fundamental rule in calculus for finding the derivative of composite functions. The chain rule states that if you have a composite function f(g(x)), then its derivative is the derivative of the outer function evaluated at the inner function, multiplied by the derivative of the inner function.

Mathematically expressed as:
$$\frac{d}{dx}[f(g(x))] = f'(g(x)) \cdot g'(x)$$

Or in Leibniz notation:
$$\frac{dy}{dx} = \frac{dy}{du} \cdot \frac{du}{dx}$$

The chain rule is essential for differentiating complex functions and is widely used in calculus, physics, engineering, and machine learning (particularly in backpropagation algorithms for neural networks). Common applications include finding derivatives of exponential functions, trigonometric functions with inner functions, and nested polynomial expressions.

A fundamental result in number theory that provides a solution to systems of simultaneous linear congruences with coprime moduli. The theorem states that if one has several congruence equations, a unique solution exists modulo the product of the moduli, provided that the moduli are pairwise coprime.

Formally, if n₁, n₂, ..., nₖ are pairwise coprime positive integers and a₁, a₂, ..., aₖ are any integers, then the system of congruences x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ aₖ (mod nₖ) has a unique solution modulo N = n₁ × n₂ × ... × nₖ.

The theorem has applications in various fields including cryptography (RSA algorithm), coding theory, and computer science (particularly in distributed computing and for creating efficient algorithms). It also has historical significance, originating in ancient Chinese mathematics as early as the 3rd century CE in the mathematical text "Sunzi Suanjing."

Video explanation:
Chinese Remainder Theorem - A comprehensive explanation of the Chinese Remainder Theorem, its proof, and applications.

A loss function commonly used in classification problems, particularly for multi-class classification and neural networks. Cross entropy loss measures the difference between the predicted probability distribution and the true distribution (one-hot encoded labels). It penalizes confident wrong predictions more heavily than uncertain predictions.

Mathematically, for a single sample with true class y and predicted probabilities p, the cross entropy loss is:

$$L = -\sum_{i=1}^{C} y_i \log(p_i)$$

where C is the number of classes. For binary classification, this simplifies to:

$$L = -[y \log(p) + (1-y) \log(1-p)]$$

Cross entropy loss is particularly effective because it provides strong gradients when predictions are wrong and approaches zero as predictions become more accurate. It's widely used in deep learning for training neural networks on classification tasks, often combined with softmax activation in the output layer.

A cryptographic protocol that allows two parties to establish a shared secret key over an insecure communication channel without requiring a prior shared secret. It relies on the mathematical principles of modular exponentiation and the computational difficulty of the discrete logarithm problem.

The protocol works by having both parties generate private keys, derive public keys using modular exponentiation, exchange these public keys, and then independently compute the same shared secret. This method is fundamental to many secure communications systems and was the first practical implementation of public key cryptography. It's widely used in secure protocols like HTTPS, SSH, IPsec, and TLS to establish encrypted communication channels.

Video explanations:
Diffie-Hellman Key Exchange - A visual explanation of how the Diffie-Hellman protocol works and why it's secure.

The Genius Math of Modern Encryption | Diffie-Hellman Key Exchange - A visual explanation of how the Diffie-Hellman protocol works and why it's secure.

A hybrid regression technique that combines the penalties of both Lasso and Ridge Regression, incorporating both L1 and L2 regularization terms. This balanced approach overcomes limitations of each method alone: it can select variables like Lasso while handling groups of correlated features better, similar to Ridge. The mixing parameter allows data scientists to tune the model between pure Lasso and pure Ridge behavior.

Elastic Net is particularly valuable for complex datasets with many correlated features, such as in genomics (where groups of genes may work together), neuroimaging (where brain regions have correlated activities), and recommendation systems (where user preferences show complex patterns).

A fundamental mathematical constant approximately equal to 2.71828, denoted by the letter 'e' in honor of the Swiss mathematician Leonhard Euler. It is defined as the limit of (1 + 1/n)ⁿ as n approaches infinity, or equivalently as the sum of the infinite series:

$$e = \sum_{n=0}^{\infty} \frac{1}{n!} = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots$$

Euler's number is the base of the natural logarithm and appears naturally in many areas of mathematics, particularly in calculus where it serves as the unique number such that the derivative of eˣ equals eˣ itself. This property makes it invaluable for solving differential equations and modeling exponential growth and decay processes.

Key Applications:
- Compound Interest: Continuous compounding formula A = Pe^(rt)
- Population Growth: Exponential growth models in biology and demographics
- Radioactive Decay: Half-life calculations in physics and chemistry
- Probability Theory: Normal distribution and Poisson processes
- Signal Processing: Fourier transforms and complex analysis
- **Machine Learning**: Activation functions (sigmoid, softmax) and optimization algorithms
- Economics: Present value calculations and economic modeling

The constant e is irrational and transcendental, meaning it cannot be expressed as a simple fraction or as the root of any polynomial equation with rational coefficients. Its ubiquity in natural phenomena has earned it the designation as one of the most important mathematical constants alongside π.

A set of fundamental algebraic rules that govern operations with exponential expressions. These rules are essential for simplifying expressions, solving equations, and working with logarithms and exponential functions.

Basic Exponent Rules:
- Product Rule: $a^m \cdot a^n = a^{m+n}$
- **Quotient Rule**: $\frac{a^m}{a^n} = a^{m-n}$ (where $a \neq 0$)
- Power Rule: $(a^m)^n = a^{mn}$
- Power of a Product: $(ab)^n = a^n b^n$
- Power of a Quotient: $\left(\frac{a}{b}\right)^n = \frac{a^n}{b^n}$ (where $b \neq 0$)
- Zero Exponent: $a^0 = 1$ (where $a \neq 0$)
- Negative Exponent: $a^{-n} = \frac{1}{a^n}$ (where $a \neq 0$)
- Fractional Exponent: $a^{\frac{m}{n}} = \sqrt[n]{a^m} = (\sqrt[n]{a})^m$

These rules form the foundation for working with exponential and logarithmic functions, compound interest calculations, scientific notation, and are extensively used in algebra, calculus, physics, chemistry, and computer science algorithms.

A float, or floating-point number, is a data type used in computer programming to represent real numbers that can have a fractional part. Unlike integers, which represent whole numbers, floats can represent a wide range of values, including very small and very large numbers, as well as numbers with decimal points. Floating-point numbers are typically stored in a format defined by the IEEE 754 standard, which specifies how to represent the number using a sign bit, an exponent, and a significand (or mantissa). Common floating-point types include single-precision (usually 32-bit) and double-precision (usually 64-bit), offering different ranges and levels of precision. While versatile, floating-point arithmetic can introduce small inaccuracies due to the finite way real numbers are approximated, leading to potential rounding errors or loss of precision in calculations.

Reference: How floating point works - jan Misali

Floating-point precision refers to the number of significant digits that can be accurately represented by a floating-point data type. It determines how close the stored floating-point number can be to the true mathematical value. Precision is limited because computers store numbers in a finite number of bits. The IEEE 754 standard defines common formats like single-precision (float) and double-precision (double). Single-precision typically offers about 7 decimal digits of precision, while double-precision offers about 15-17 decimal digits.

What this means in practice is that calculations involving floating-point numbers may not always be exact. For example, representing 0.1 in binary floating-point is not perfectly accurate, similar to how 1/3 cannot be perfectly represented as a finite decimal. This can lead to:
- Rounding Errors: Small discrepancies that occur when a number is rounded to fit the available precision.
- Loss of Significance: When subtracting two nearly equal numbers, significant digits can be lost, leading to a result with much lower relative accuracy.
- Comparison Issues: Directly comparing two floating-point numbers for equality (e.g., `a == b`) can be unreliable due to these small precision differences. It's often better to check if their absolute difference is within a small tolerance (epsilon).

Understanding floating-point precision is crucial in scientific computing, financial calculations, and any domain where numerical accuracy is important, as ignoring these limitations can lead to incorrect results or unexpected behavior in programs.

Reference: How floating point works - jan Misali

An extension of the standard CP decomposition that incorporates different loss functions and constraints to handle various data types (binary, count, continuous) and missing values. GCP provides more flexibility for modeling complex real-world data with non-Gaussian characteristics.

In unsupervised learning, GCP enables robust pattern discovery in heterogeneous multi-way data, supporting applications like topic modeling across document collections, community detection in dynamic networks, and analyzing sparse, noisy biological measurements across multiple experimental conditions.

A fundamental optimization algorithm used to train machine learning models by iteratively adjusting parameters to minimize a loss function. The algorithm computes the gradient (partial derivatives) of the loss function with respect to each parameter and updates parameters in the direction opposite to the gradient, effectively moving downhill toward a minimum.

Mathematically, the update rule is:
$$\theta_{t+1} = \theta_t - \alpha \nabla J(\theta_t)$$

where θ represents parameters, α is the learning rate, and ∇J(θ) is the gradient of the loss function.

Main Variants:

Batch Gradient Descent: Uses the entire dataset to compute gradients at each step. Provides stable convergence but can be computationally expensive for large datasets.

**Stochastic Gradient Descent (SGD)**: Uses a single random sample to compute gradients at each step. Much faster per iteration and can escape local minima due to noise, but convergence is more erratic.

Mini-batch Gradient Descent: Uses small batches of samples (typically 32-256) to compute gradients. Balances the stability of batch gradient descent with the efficiency of SGD, making it the most commonly used variant in practice.

Gradient descent is the foundation of most machine learning optimization and is essential for training neural networks, linear regression, logistic regression, and many other models.

A linear regression technique that performs both variable selection and regularization to enhance prediction accuracy and interpretability. Lasso (Least Absolute Shrinkage and Selection Operator) adds an L1 penalty term to the cost function, which can shrink some coefficients exactly to zero, effectively removing less important features from the model. This feature selection capability makes Lasso particularly valuable for high-dimensional datasets where many features may be irrelevant or redundant.

Lasso Regression is widely used in fields like genomics (selecting relevant genetic markers), finance (identifying key economic indicators), and image processing (extracting important features while discarding noise).

A mathematical function that measures how far a model's predictions are from the actual target values, providing a quantifiable way to assess model performance during training. The loss function calculates the "cost" or "error" of the model's current state, with lower values indicating better performance. Different types of problems require different loss functions: mean squared error for regression tasks, cross-entropy for classification, and specialized losses for tasks like object detection or generative modeling.

The choice of loss function is crucial as it directly influences how the model learns through gradient descent optimization. During training, the algorithm adjusts model parameters to minimize the loss function, effectively teaching the model to make better predictions. Common examples include mean absolute error (L1 loss), mean squared error (L2 loss), binary cross-entropy, categorical cross-entropy, and Huber loss. Modern deep learning often employs custom loss functions tailored to specific tasks, such as focal loss for handling class imbalance or perceptual loss for image generation tasks.

Statistical techniques that don't rely on assumptions about the underlying population distribution. These methods are distribution-free and typically based on ranks or orders rather than the actual values. Examples include the Mann-Whitney U test, Kruskal-Wallis test, and Spearman's rank correlation.

Non-parametric methods are more robust and flexible, making them suitable when data doesn't meet parametric assumptions or when working with ordinal data, but they may have less statistical power when parametric assumptions are valid.

NP is the complexity class of decision problems for which a solution can be verified in polynomial time, even if finding that solution might take longer. More formally, these are problems solvable by a nondeterministic Turing machine in polynomial time. Every problem in P is also in NP (since if you can solve a problem quickly, you can certainly verify a solution quickly), but the famous open question in computer science is whether P = NP, which asks if every problem whose solution can be quickly verified can also be quickly solved. Examples of NP problems include the Boolean satisfiability problem, the traveling salesman decision problem, and the subset sum problem.

NP-Complete problems are the hardest problems in the NP class, in the sense that if an efficient (polynomial time) algorithm exists for any NP-Complete problem, then efficient algorithms would exist for all problems in NP. A problem is NP-Complete if it is in NP and every other problem in NP can be reduced to it in polynomial time. The first problem proven to be NP-Complete was the Boolean satisfiability problem (SAT), through Cook's theorem. Other examples include the traveling salesman decision problem, the graph coloring problem, and the subset sum problem. The P vs NP question essentially asks whether NP-Complete problems can be solved efficiently.

NP-Hard problems are at least as hard as the hardest problems in NP, but they might not be in NP themselves. A problem is NP-Hard if every problem in NP can be reduced to it in polynomial time, but the problem itself might not be verifiable in polynomial time. NP-Hard problems can be decision problems, search problems, or optimization problems. All NP-Complete problems are NP-Hard, but not all NP-Hard problems are NP-Complete. Examples of NP-Hard problems include the traveling salesman optimization problem (finding the shortest route), the graph isomorphism problem, and the halting problem. Many important optimization problems in various fields like operations research, bioinformatics, and artificial intelligence are NP-Hard, which is why approximation algorithms and heuristics are often used to find good-enough solutions in practice.

An algorithm used to adjust the parameters of machine learning models during training to minimize the loss function. Optimizers determine how the model's weights and biases are updated based on the computed gradients, directly affecting the speed and quality of learning.

Common optimizers include:

**Gradient Descent (SGD)**: The fundamental optimizer that updates parameters in the direction opposite to the gradient.

Adam (Adaptive Moment Estimation): Combines momentum and adaptive learning rates, widely used for its robustness and efficiency.

RMSprop: Adapts learning rates based on recent gradient magnitudes, effective for non-stationary objectives.

AdaGrad: Adapts learning rates based on historical gradients, useful for sparse data.

Momentum: Accelerates SGD by adding a fraction of the previous update to the current one.

AdamW: A variant of Adam with decoupled weight decay for better regularization.

The choice of optimizer significantly impacts training convergence, stability, and final model performance. Modern deep learning frameworks typically default to Adam or its variants due to their adaptive nature and robust performance across various tasks.

P is the complexity class of decision problems that can be solved by a deterministic Turing machine in polynomial time. In simpler terms, these are problems for which efficient algorithms exist that can find a solution in a reasonable amount of time, even as the input size grows. The time required to solve these problems grows as a polynomial function of the input size. Examples include sorting algorithms, searching in ordered lists, and determining if a number is prime using modern primality tests. P represents the class of problems that are considered computationally tractable.

Statistical methods that assume data comes from a population following a probability distribution based on a fixed set of parameters. These methods make specific assumptions about the data's distribution (often assuming normal distribution) and draw inferences about the parameters of the assumed distribution. Examples include t-tests, ANOVA, and linear regression.

Parametric methods are generally more powerful when their assumptions are met but may produce misleading results when these assumptions are violated.

The Pearson Correlation Coefficient (PCC) is a statistical measure that quantifies the linear relationship between two continuous variables. It produces a value ranging from -1 to +1, where +1 indicates a perfect positive linear relationship, -1 indicates a perfect negative linear relationship, and 0 indicates no linear relationship between the variables.

Mathematically, it is calculated as the ratio between the covariance of two variables and the product of their standard deviations, making it a normalized measurement of covariance. The formula is often expressed as:

$$
r = \frac{\sum_{i=1}^{n} (x_i - \bar{x})(y_i - \bar{y})}{\sqrt{\sum_{i=1}^{n} (x_i - \bar{x})^2 \sum_{i=1}^{n} (y_i - \bar{y})^2}}
$$

In machine learning, the Pearson correlation coefficient serves several critical functions:

1. Feature Selection: It helps identify which features have strong relationships with the target variable, allowing data scientists to select the most relevant features for model training.

2. Multicollinearity Detection: It identifies highly correlated input features that might cause instability in models like linear regression.

3. Dimensionality Reduction: Understanding correlation patterns helps in techniques like Principal Component Analysis (PCA) to reduce the number of features while preserving information.

4. Data Exploration: It provides insights into relationships within the data, guiding further analysis and model selection.

The interpretation of correlation strength varies by field, but generally:
- Values between ±0.1 and ±0.3 indicate weak correlation
- Values between ±0.3 and ±0.5 indicate moderate correlation
- Values between ±0.5 and ±1.0 indicate strong correlation

It's important to note that Pearson correlation only captures linear relationships and is sensitive to outliers. For non-linear relationships or when dealing with ordinal data, alternative measures like Spearman's rank correlation coefficient may be more appropriate.

In practical machine learning applications, Pearson correlation is used in genomics to identify relationships between genes, in financial modeling to analyze market dependencies, and in recommendation systems to measure similarities between user preferences or items.

Simple Examples:

1. Strong Positive Correlation (r ≈ 0.9): Height and weight in a population. As height increases, weight tends to increase proportionally.

2. Moderate Positive Correlation (r ≈ 0.4): Study hours and test scores. More study time generally leads to better scores, but other factors also influence performance.

3. No Correlation (r ≈ 0): Shoe size and intelligence. These variables have no meaningful linear relationship.

4. Moderate Negative Correlation (r ≈ -0.4): Age of a car and its resale value. Older cars typically have lower resale values, though condition and other factors matter.

5. Strong Negative Correlation (r ≈ -0.8): Outdoor temperature and home heating usage. As temperature drops, heating usage increases substantially.

An algorithm for computing discrete logarithms in a cyclic group, particularly useful when the order of the group has only small prime factors. Developed by Stephen Pohlig and Martin Hellman in 1978, it significantly reduces the computational complexity of the discrete logarithm problem in certain groups.

The algorithm works by decomposing the discrete logarithm problem in a group of composite order into smaller subproblems in groups of prime order using the Chinese remainder theorem. It then solves these smaller problems using techniques like the baby-step giant-step algorithm. While highly efficient for groups whose order factors into small primes, it's ineffective against groups specifically chosen for cryptographic purposes (those with at least one large prime factor). Understanding this algorithm is crucial for cryptographers to select appropriate parameters for discrete logarithm-based cryptosystems like Diffie-Hellman and ElGamal.

Video explanation:
How can I compute discrete logs faster? — Pohlig–Hellman — The Ross Program - A mathematical explanation of how the Diffie-Hellman protocol works and why it's secure.

A differentiation rule used to find the derivative of a function that is the quotient (division) of two other functions. If you have a function h(x) = f(x)/g(x), where both f(x) and g(x) are differentiable and g(x) ≠ 0, then the quotient rule provides the formula for h'(x).

The quotient rule formula is:
$$\frac{d}{dx}\left[\frac{f(x)}{g(x)}\right] = \frac{f'(x) \cdot g(x) - f(x) \cdot g'(x)}{[g(x)]^2}$$

Often remembered by the mnemonic "low d-high minus high d-low, over low squared" where "high" refers to the numerator function and "low" refers to the denominator function. This rule is particularly useful in calculus for differentiating rational functions, rates of change problems, and optimization problems involving ratios.

A widely-used activation function in neural networks that outputs the input directly if it's positive, otherwise it outputs zero. Mathematically defined as f(x) = max(0, x), ReLU is simple yet effective at introducing non-linearity into neural networks while being computationally efficient. It helps solve the vanishing gradient problem that plagued earlier activation functions like sigmoid and tanh, allowing for faster training of deep networks. ReLU has become the default activation function for hidden layers in most modern neural network architectures, though variants like Leaky ReLU and ELU address some of its limitations, such as the "dying ReLU" problem where neurons can become permanently inactive.

A regularization technique that addresses multicollinearity in linear regression by adding an L2 penalty term to the cost function. Unlike Lasso, Ridge Regression shrinks coefficients toward zero but rarely sets them exactly to zero, keeping all features in the model while reducing their impact. This approach is particularly effective when dealing with highly correlated predictors, preventing the model from assigning excessive importance to any single variable.

Ridge Regression excels in scenarios where all features contribute to the outcome but need to be constrained to prevent overfitting, such as in economic forecasting, climate modeling, and biomedical research.

A cryptographic weakness that can occur in implementations of protocols using discrete logarithm-based cryptography, particularly Diffie-Hellman key exchange. These vulnerabilities arise when an attacker forces computations into a small subgroup of the larger cryptographic group, making it feasible to determine the private key through brute force methods.

Small subgroup attacks exploit improper parameter validation, specifically when implementations fail to verify that received public keys are members of the correct cryptographic group of appropriate order. By sending carefully crafted invalid public values, attackers can extract information about the victim's private key through multiple protocol interactions. Proper implementation requires validation of all public keys and the use of safe primes or prime order subgroups to mitigate these vulnerabilities.

A mathematical function that converts a vector of real numbers into a probability distribution, where each output value is between 0 and 1 and all outputs sum to 1. Softmax is commonly used as the final activation function in multi-class classification problems, transforming raw model outputs (logits) into interpretable probabilities for each class.

Mathematically defined as: $$\text{softmax}(x_i) = \frac{e^{x_i}}{\sum_{j} e^{x_j}}$$ for all j, where x is the input vector. The exponential function ensures all outputs are positive, while the normalization by the sum creates a valid probability distribution. Softmax amplifies the differences between values - larger inputs receive disproportionately higher probabilities, making it useful for confident predictions.

Softmax is essential in neural networks for tasks like image classification (determining which of several objects appears in an image), natural language processing (predicting the next word from a vocabulary), and any scenario requiring probabilistic outputs across multiple mutually exclusive categories. It's often paired with cross-entropy loss during training to optimize classification performance.

In simple terms, "stochastic" refers to processes or systems that are random or inherently unpredictable, but they follow some statistical patterns or probabilities. Stochastic systems don't have a single, fixed outcome; instead, their behavior or outcomes are governed by chance and probability distributions.

The term is widely used in fields like mathematics, biology, finance, and physics, where randomness and uncertainty are present.

A higher-order extension of principal component analysis (PCA) that decomposes a tensor into a core tensor multiplied by a matrix along each mode. Tucker decomposition provides a more flexible representation than other tensor methods, allowing different ranks for different dimensions.

In unsupervised learning, Tucker decomposition excels at subspace learning and dimensionality reduction for multi-way data, enabling applications like multi-aspect data mining, anomaly detection in network traffic, and feature extraction from multi-modal signals.