6
$\begingroup$

There are two main probabilistic approaches to novelty detection: parametric and non-parametric. The non-parametric approach assumes that the distribution or density function is derived from the training data, like kernel density estimation (e.g., Parzen window), while parametric approach assumes that the data comes from a known distribution.

I am not familiar with the parametric approach. Could anyone show me some well known algorithms? By the way, can MLE be considered as a kind of parametric approach (the density curve is known, and then we seek to find the parameter corresponding to the maximum value)?

$\endgroup$
7
$\begingroup$

Usually, maximum likelihood is used in a parametric context. But the same principle can be used nonparametrically. For example, if you have data consisting in observation from a continuous random variable $X$, say observations $x_1, x_2, \dots, x_n$, and the model is unrestricted, that is, just saying the data comes from a distribution with cumulative distribution function $F$, then the empirical distribution function $$ \hat{F}_n(x) = \frac{\text{number of observations $x_i$ with $x_i \le x$}}{n} $$ the non-parametric maximum likelihood estimator.

This is related to bootstrapping. In bootstrapping, we are repeatedly sampling with replacement from the original sample $X_1,X_2, \dots,X_n$. That is exactly the same as taking an iid sample from $\hat{F}_n$ defined above. In that way, bootstrapping can be seen as nonparametric maximum likelihood.

EDIT   (answer to question in comments by @Martijn Weterings)

If the model is $X_1, X_2, \dotsc, X_n$ IID from some distribution with cdf $F$, without any restrictions on $F$, then one can show that $\hat{F}_n(x)$ is the mle (maximum likelihood estimator) of $F(x)$. That is done in What inferential method produces the empirical CDF? so I will not repeat it here. Now, if $\theta$ is a real parameter describing some aspect of $F$, it can be written as a function $\theta(F)$. This is called a functional parameter. Some examples is $$ \DeclareMathOperator{\E}{\mathbb{E}} \E_F X=\int x \; dF(x)\quad (\text{The Stieltjes Integral}) \\ \text{median}_F X = F^{-1}(0.5) $$ and many others. By the invariance property (Invariance property of maximum likelihood estimator?) we then find mle's by $$ \widehat{\E_F X} = \int x \; d\hat{F}_n(x) \\ \widehat{\text{median}_F X}= \hat{F}_n^{-1}(0.5). $$ It should be clearer now. We don't (as you ask about) use the empirical distribution function to define the likelihood, the likelihood function is completely nonparametric, and the $\hat{F}_n$ is the mle. The bootstrap is then used to describe the variability/uncertainty in mle's of $\theta(F)$'s of interest by resampling (which is simple random sampling from the $\hat{F}_n$.)

$\endgroup$
  • 4
    $\begingroup$ Why is bootstrapping related to parametric MLE? And why is empirical CDF the MLE? $\endgroup$ – Albert Chen Jun 22 '17 at 19:06
  • $\begingroup$ What kind of problem uses bootstrapping to finding some optimal parameter? Say, does it work to find MLE of the mean of a population for which we have a sample $x_1=1, ..., x_n=n$? It seems a bit cyclic. I compute the probability to obtain the data based on the empirical distribution from that same data (or is this done in some cross validation way?). Would that really lead to a MLE? How do you compute the probability/likelihood with bootstrapping? $\endgroup$ – Sextus Empiricus Mar 31 '19 at 0:27
  • $\begingroup$ Bootstrapping is nonparametric MLE in the sense that $\hat{F}_n$ is the MLE of $F$, when there is no restrictions. It then gives the MLE of any parameter defined by $\theta=\theta(F)$ as a function of $F$, given by $\hat{\theta}=\theta(\hat{F}_n)$. That is the connection, that the bootstrap s then a way of approximation the distribution of this estimator. $\endgroup$ – kjetil b halvorsen Apr 1 '19 at 14:40
  • $\begingroup$ @kjetilbhalvorsen I do not see so clearly how that works. The function $\hat{F}_n$ is the empirical distribution function. How do I compute the likelihood function (and associated MLE) from this? If I can turn it into some empirical likelihood function (which depends on $\theta$) then I agree that you can use this to maximize it and you have something like a MLE. But how does this relate to bootstrapping, and how do you go from the function $\hat{F}_n$ to a likelihood function? What does $\theta(F)$ mean, how is it defined? $\endgroup$ – Sextus Empiricus Apr 4 '19 at 8:29
  • $\begingroup$ MLE is used to compute estimates for one or more parameters. But how this function $\hat{F_n}$ relates to those parameters is unclear. There must be a particular expression that makes this connection. For instance, we need to be able to make a choice to either compute the MLE of the variance, or the MLE of the mean, and this should somehow be found in the expression of $F_n$ and whatever method of bootstrapping is used to find some pseudo likelihood-function and maximize it for the mean or the variance (or whatever other parameter one wishes to estimate). $\endgroup$ – Sextus Empiricus Apr 4 '19 at 8:38
6
$\begingroup$

It is applied to both, parametric and nonparametric models.

Parametric example. Let $x_1,\dots,x_n$ be an independent sample from an $Exp(\lambda)$. We can find the MLE of the parameter $\lambda$ by maximising the corresponding likelihood function.

Nonparametric example. Maximum likelihood density estimation. In this recent paper you can find an example of a maximum likelihood estimator of a multivariate density. This can be considered as a nonparametric problem, which incidentally represents an interesting alternative to the KDE mentioned in your question.

$\endgroup$
2
$\begingroup$

Not necessarily. You can use maximum likelihood to fit nonparametric models such as infinite mixture model. (Definition of "nonparametric model" is not always clear-cut though.)

$\endgroup$
  • $\begingroup$ This question has a bit of a loose end. Could you provide more information about how this fitting of non-parametric functions is done? Or maybe at least a reference that explains it. $\endgroup$ – Sextus Empiricus Apr 4 '19 at 8:44
1
$\begingroup$

Nonparametric maximum likelihood estimates exist only if you impose special constraints on the class of allowed densities. Suppose that you have a random sample $x_1,\dots,x_n$ from some density $f$ with respect to Lebesgue measure. In the nonparametric setting, the likelihood is a functional which for each density $f$ outputs a real number $$ L_x[f] = \prod_{i=1}^n f(x_i) \, . $$ If you are allowed to choose any density $f$, then for $\epsilon>0$ you can pick $$ f_\epsilon(t) = \frac{1}{n}\sum_{i=1}^n \frac{e^{-(t-x_i)^2/2\epsilon^2}}{\sqrt{2\pi}\epsilon} \,. $$ But then, because $$ L_x[f_\epsilon] \geq \frac{1}{\left(n\sqrt{2\pi}\epsilon\right)^n} \, , $$ making $\epsilon$ small you can make $L_x[f_\epsilon]$ grow unboundedly. Hence, there is no density $f$ which is the maximum likelihood estimate. Grenander proposed the method of sieves, in which we make the class of allowed densities grow with the sample size, as a remedy to this aspect of nonparametric maximum likelihood. Exagerating a little bit, we may say that this property of nonparametric maximum likelihood is "the mother of all overfitting" in Machine Learning, but I digress.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.