Fast Recap:

Estimated Probability

Recap:

Probability $P$ that a generic pattern $\underline{x}$ , drawn from pdf $p (\cdot)$ , belongs to an arbitrary region $R$ of the feature space:

P = \int_{R} p (\underline{x}) d \underline{x}

If $k$ out of $n$ data are in $R$ , we can estimate $P$ via the relative frequency:

P ≃ \frac{k}{n}

Practical Problem: Consider that if the region isn’t really big enough and the pdf $p (\cdot)$ is constant the probability $P$ will tend to $0$ .

As $n$ (our number of data) increases, so does our region: $R_{1}, R_{2}, \dots, R_{n}$ , where the subscript means the number of data in the region, such that $\underline{x_{0}}$ belong to each of them, $\underline{x_{0}} \in R_{i} \forall i$ , where $\underline{x_{0}}$ is our pattern of interest (~Ex.: we are searching for the pdf of males in a specific university, we use the region $R_{n}$ to estimate $p (\underline{x_{0}})$ from $n$ data.

$V_{n}$ be the volume of $R_{n}$ .
$k_{n}$ be the number of data (out of $n$ ) in $R_{n}$ .
$p_{n} (\underline{x_{0}})$ be the $n$ -th estimate of $p (\underline{x_{0}})$ , ~Ex.: $p_{n} (\underline{x_{0}}) = \frac{k _{n}}{n V _{n}}$ .

Asymptotic Necessary and Sufficient Conditions: we want to ensure $p_{n} (\underline{x_{0}}) \to p (\underline{x_{0}})$ :

$lim_{n \to \infty} V_{n} = 0$
$lim_{n \to \infty} k_{n} = \infty$
$lim_{n \to \infty} \frac{k _{n}}{n} = 0$ (to guarantee convergence)

⇒ To satisfy these conditions, we can do one of two things:

Fix a proper volume, say $V_{n} = \frac{1}{n}$ and determine $\frac{k _{n}}{n}$ consequently. (Parzen Window).
Fix $k_{n}$ (~Ex.: $k_{n} = n$ ), and determine $V_{n}$ consequently, in such a way that exactly $k_{n}$ patterns fall in $R_{n}$ ( $k_{n}$ -nearest neighbor).

🪴 Quartz 4.0

Explorer

AI - Lecture 8

Fast Recap:

Recap:

Original Files:

Graph View

Backlinks