PAC Learning: Theory

Lecture 6: Learning Theory

PAC Learning

• Goal is to create general rules for when algorithms will generalize well.
• Sample set: $S = {(x_i, y_i)}_{i=1}^N \sim D^N$
• A hypothesis h is consistent with S if $h(x_i) = y_i$ for all $(x_i, y_i)$ in S.
• True error is $\epsilon(h) = P_{x \sim D}(h(x) \neq y)$
• Empirical error is $\hat{\epsilon}(h) = \frac{1}{N} \sum_{i=1}^N \mathbb{1}(h(x_i) \neq y_i)$

PAC (Probably Approximately Correct)

• Class H is PAC-learnable if an algorithm A exists, given $\epsilon, \delta > 0$, there exists N such that when A is trained on N examples from distribution D, with probability $1 - \delta$, A outputs hypothesis h where $\epsilon(h) \leq \epsilon$.

Theorem

• For finite H, given $\epsilon, \delta > 0$, a hypothesis h in H that is consistent with sample set S has error capped at $\epsilon$ with a probability of $1 - \delta$, if (N \geq \frac{1}{\epsilon} (ln |H| + ln \frac{1}{\delta})).

Proof

• The event $B_h$ indicates that h is consistent with S but $\epsilon(h) > \epsilon$.
• $P(B_h) = P(h(x_i) = y_i, \forall i | \epsilon(h) > \epsilon) = (1 - \epsilon)^N$
• $P(\bigcup_{h: \epsilon(h) > \epsilon} B_h) \leq \sum_{h: \epsilon(h) > \epsilon} P(B_h) \leq |H|(1 - \epsilon)^N$
• $(1 - \epsilon) \leq e^{-\epsilon}$
• $P(\bigcup_{h: \epsilon(h) > \epsilon} B_h) \leq |H|e^{-\epsilon N} \leq \delta$
• $e^{-\epsilon N} \leq \frac{\delta}{|H|}$
• $-\epsilon N \leq ln(\frac{\delta}{|H|})$
• $\epsilon N \geq ln(\frac{|H|}{\delta})$
• $N \geq \frac{1}{\epsilon} ln(\frac{|H|}{\delta})$

General $H$

Mistake Bound Model (Online Learning)

• $\epsilon = 0$, the model focuses on how many mistakes are made.

Halving Algorithm

• Algorithm tracks all H hypotheses that align with observed data.
• Predictions based on the majority vote from these hypotheses.
• Each mistake diminishes the hypotheses pool by at least half.
• Implies at most $log_2 |H|$ mistakes.

Weighted Majority Algorithm

• Each hypothesis $h_i$ has a weight $w_i$.
• Prediction is based on weighted majority.
• If a hypothesis $h_i$ errs, its weight $w_i$ adjusts: $w_i \leftarrow \beta w_i$, where $\beta \in [0, 1]$

Theorem

• Compared to the best H hypothesis, the mistake count by Weighted Majority is at most $\frac{ln |H|}{ln(1/\beta)} + \frac{ln(1/\delta)}{ln(1/\beta)} $

Proof

• Let $W_t = \sum_i w_i$
• Initially $W_0 = |H|$
• With each mistake, $W_t \leftarrow W_t \beta^{fraction \ of \ weight}$
• After $M$ mistakes, $W_M \leq |H| \beta^M$
• Best hypothesis makes m mistakes $W_M \geq \beta^m$
• $\beta^m \leq W_M \leq |H|\beta^M$
• $\beta^m \leq |H| \beta^M$
• $m \ ln \beta \leq ln|H| + M \ ln \beta$
• $M \ ln \beta \geq m \ ln \beta - ln |H|$
• $M \leq \frac{m \ ln \beta - ln |H|}{ln \beta}$
• $M \leq \frac{ln |H|}{ln(1/\beta)} + m$
• If $\beta = 1 - \epsilon$:
• $ln(\frac{1}{1 - \epsilon}) \approx \epsilon$
• $M \leq \epsilon m + \frac{ln |H|}{\epsilon}$
• With probability $1 - \delta$, $M \leq \epsilon m + \frac{ln |H| + ln(1/\delta)}{\epsilon}$

VC Dimension

Shattering

• H shatters (S = {x_1,..., x_n}) if for every labeling assignment to S, some $h \in H$ produces precisely those labels.

VC Dimension

• VC(H) = size of $S$ set that H can shatter

Examples

• Threshold functions on $\mathbb{R}$ VC(H) = 2
• Intervals on $\mathbb{R}$ VC(H) = 2
• Axis-aligned rectangles on $\mathbb{R}^2$ VC(H) = 4
• Linear classifiers on $\mathbb{R}^d$ VC(H) = d + 1

Theorem

• For any $D$, with probability at least $1 - \delta$, for all h in H:
• $\epsilon(h) \leq \hat{\epsilon}(h) + \sqrt{\frac{VC(H)(ln(\frac{2N}{VC(H)}) + ln(\frac{4}{\delta}))}{N}}$

Implications

• Can’t shatter $N$ with $ |H| < 2^N$ points
• H is PAC learnable if VC(H) is finite

Proof Idea

1. If $\epsilon(h)$ and $\hat{\epsilon}(h)$ are very different, S is “lucky.”
2. Bounding probability of S being lucky.

Growth Function

• $\prod_H(N) = max_{x_1,..., x_N} |{ (h(x_1),..., h(x_N)) | h \in H }|$

Sauer's Lemma

• If VC(H) = d, then $\prod_H(N) \leq \sum_{i=0}^d \binom{N}{i} = O(N^d)$

Structural Risk Minimization

• Choose h to minimize:
• $\hat{\epsilon}(h) + \sqrt{\frac{VC(H)(ln(\frac{2N}{VC(H)}) + ln(\frac{4}{\delta}))}{N}}$

Teorema de Bayes

Overview

• A theory of probability and statistics, Bayes' Theorem defines an event's probability based on prior knowledge of conditions related to the event.
• The formula:

Formula

$$ P(A|B) = \frac{P(B|A)P(A)}{P(B)} $$

• $P(A|B)$: posteriori probability of event A, if B is true.
• $P(B|A)$: Likelihood of observing event B, if A is true.
• $P(A)$: priori probability of A being true.
• $P(B)$: priori probability of B being true.

Example Application

Scenario

• A test designed to detect a rare disease affecting 1 in 10,000 people.
• The precision rate of the test is 99%, in that 99% of the time it reports correctly if positive or negative.

Question

• If tests positive, the probability of actually having it?

Application of Theorem of Bayes

• $P(Doença)$ = 1/10.000 = 0,0001 (prior probability)
• $P(Positivo|Doença)$ = 0,99 (probability of testing positive, given you have it)
• $P(Positivo|Não Doença)$ = 0,01 (probability of testing positive, not having it)
• Calculate $P(Positivo)$ using the law of total probability: $$ P(Positivo) = P(Positivo|Doença)P(Doença) + P(Positivo|Não,Doença)P(Não,Doença) $$
• $P(Positivo) = (0,99 \times 0,0001) + (0,01 \times 0,9999) = 0,010098$
• Calculate the likelihood of having disease after testing positive: $$ P(Doença|Positivo) = \frac{P(Positivo|Doença)P(Doença)}{P(Positivo)} $$
• $P(Doença|Positivo) = \frac{0,99 \times 0,0001}{0,010098} \approx 0,0098$
• Even if testing positive, chance of having the disease is around 0.98% due to its rareness.

Algorithmic Trading & Quantitative Strategies

Topic 1: Introduction to Algorithmic Trading

Algorithmic Trading

• Utilizing computer programs to automate buying and selling decisions.
• Also Automated trading, "black-box", algo-trading, quantitative trading

Motivation

• Enhanced speed of order execution.
• Reduced transaction expenditures.
• Consistent trading, excluding emotional influences.
• Opportunity to quickly find and exploit arbitrage opportunities.
• Automation for backtesting to optimize strategies.

Types of Automated Trade Systems

Trend Following

• Capitalization of trending market direction.
• Utilizing averages to identify when to break out.

Mean Reversion

• Trades based upon prices correcting toward an average baseline.
• Trade based upon correlation pairs, Bollinger Bands

Arbitrage

• Exploiting of variances found across markets
• Latency arbitrage

Market Making

• Offer liquid assets trading options
• High-frequency trading (HFT).

Statistical Arbitrage

• Using models to detect minor errors in trades
• PCA, Kalman filters

Execution Algorithms

• Best practices in order execution
• VWAP, TWAP, Implementation shortfall

Core Steps in Trading

1. Finding a potential trading opportunity.
2. Testing validity of a prospective strategy.
3. Coding the strategy and connecting to a broker.
4. Employ the strategy in market conditions.
5. Track performance.

Algorithmic Challenges

• Overfitting
• Latency
• Market trade impact
• Regulatory compliance
• Infrastructure overhead

Key Performance Indicators (KPI)

Sharpe Ratio

• Measures return vs risk

• Formula: $\qquad Sharpe = \frac{R_p - R_f}{\sigma_p}$

  where (R_p indicates portfolio income, (Rf risk-free and indicates the portfolio's standard deviation.

Drawdown

• Potential peak to trough within given window.

% Win

• % Successful Trades performed

Profit Factor

• ratio of %/loss

Alpha

• Excess income vs benchmark standard

Beta

• Measurement Systematic Risk

Platform toolset:

Languages

• Python, R, C++, Java

Platforms

• MetaTrader, TradingView, Interactive Brokers API

Toolings

• Bloomberg, Reuters, Refinitiv

Libraries

Pandas, NumPy, Scikit-learn, Zipline

Resources:

Books

• "Algorithmic Trading: Winning Strategies and Their Rationale" by Ernest P. Chan
• "Quantitative Trading: How to Build Your Own Algorithmic Trading Business" by Ernest P. Chan

Internet

• Quantopian
• QuantConnect

Journals

• Journal of Financial Markets
• Journal of Trading

Forthcoming Topics:

• Risk Management
• Trading using Machine Learning
• High-Frequency Trading

Algèbre linéaire: Cours et exercices corrigés

Authors

• Claude Deschamps
• Gilles Bertrand

Content

• A textbook on linear algebra, with courses and corrected exercises

Chapter 1: Vector Spaces

• Definition of a vector space
• Vector subspaces
• Sum of subspaces; Supplementary subspaces
• Finite-dimensional vector spaces
• Linear mappings
• Image and kernel of a linear mapping Linear forms; Hyperplanes
• Duality in finite dimension

Chapter 2: Matrices

• General information
• Matrices and linear mappings
• Elementary operations on the rows of a matrix
• Equivalent matrices
• Square matrices
• Invertible matrices
• Transposition
• Trace of a square matrix
• Matrices in blocks

Chapter 3: Determinants

• Alternating n-linear forms
• Determinant of a family of vectors
• Determinant of an endomorphism
• Determinant of a square matrix
• Applications of determinants

Chapter 4: Reduction of Endomorphisms

• Eigenvalues of an endomorphism
• Polynomials of endomorphisms
• Minimal polynomial of an endomorphism
• Diagonalization
• Trigonization
• Nilpotent endomorphisms

Chapter 5: Real Pre-Hilbert Spaces

• Dot product
• Cauchy-Schwarz inequality; Norm associated with a dot product
• Orthogonality
• Orthonormal bases
• Orthogonal projections
• Adjoint of an endomorphism
• Symmetric endomorphisms

Chapter 6: Quadratic Forms

• Bilinear forms
• Quadratic forms
• Gauss reduction
• Orthogonality
• Real pre-Hilbert spaces

Chapter 7: Affine Spaces

• Definitions and examples
• Affine subspaces
• Affine mappings
• Elements of plane affine geometry

Solutions des exercices

• Solutions to the exercises