For directed acyclic graphs, a topological sort of a directed graph is such that if there’s an edge \(A \to B\), then \(A\) comes before \(B\) in the sort (i.e. there’s not an edge from \(B\) to \(A\)). Under direct acyclic graphs, a topological sort always exist.

solving topological sort with depth first search

In a DAG, you can always go from larger finish times to smaller finish times in depth first search to be able to get a topological sort.

Let’s consider greedy Decision Tree learning.

greedy procedure

1. initial tree—no split: always predict the majority class \(\hat{y} = \text{maj}\qty(y), \forall x\)
2. for each feature \(h\qty(x)\)
   1. split data according to feature
   2. compute classification error of the split
3. choose \(h^{*}\qty(x)\) with the lowest error after splitting
4. loop until stop

stopping criteria

1. each node agrees on \(y\) (the tree fits data exactly)
2. exhausted on all features (nothing to split on)

additional information

threshold splitting

We are going to perform what’s called a “threshold split.” Choose thresholds between two points as the “split values” to check. Now, how do we deal with splitting twice? We can until we get bored or we over fit.

Exponential Family is a family of distributions following exponentials.

constituents

• \(y\) the data
• \(\eta\) the natural parameter — vector or scalar
• \(T\qty(y)\) the “sufficient statistic” (this is usually just \(y\)) — vector or scalar
• \(b\qty(y)\) the base parameter — scalar
• \(a\qty(\eta)\) the log-partition function — scalar

requirements

A class of distributions is in the Exponential Family if it can be written as:

\begin{align} P\qty(y \mid \eta) &= b\qty(y) \exp \qty(\eta^{\top}T\qty(y)-a\qty(\eta)) \\ &= \frac{b\qty(y) \exp \qty(\eta^{\top} T\qty(y))}{e^{a\qty(\eta)}} \end{align}

Using Linear Regression to perform a classification task \(y \in \qty {0,1}\) sounds kind of silly. We assume that \(y\) follows a kind of Bernoulli distribution.

requirements

\begin{align} h_{\theta}\qty(x) &= g\qty(\theta^{T} x) \\ &= \frac{1}{1+e^{-\theta^{T}x}} \end{align}

That is, we apply a sigmoid function to our linear regression output to perform classification. Such a sigmoid function has the following properties:

\begin{equation} p\qty(y=1|x;\theta) = h_{\theta}\qty(x) \end{equation}

\begin{equation} p\qty(y=0|x;\theta) = 1-h_{\theta}\qty(x) \end{equation}

\begin{equation} y \in \qty {0,1} \end{equation}

regularization penalize large weights to reduce overfitting

1. create data interpolation that countains intentional error (by throwing away/hiding parameters), missing some/all of the data points
2. this makes the resulting function more “predictable”/“smooth”

there is, therefore, a trade-off between sacrificing quality and on the ORIGINAL data and better accuracy on new points. If you regularize too much, you will underfit.

Motivation

Recall that, for linear regression, we want to optimize:

\begin{equation} \min_{\theta} \frac{1}{2} \sum_{i=1}^{n} \norm{ y^{(i)} - \theta^{\top}x^{(i)} }^{2} \end{equation}