View source for Data modeling, restructuring, analysis, fuzzy cases, learning

{{math notes}}
{{stub}}


[[Category:Math on data]]


==Overall concepts, Glossary==

===Types of problems===
{{stub}}

The types of tasks/problems are often broadly sorted into some distinct types.
...which says little about how they are solved.

* '''Regression'''
: predicts a continuous variable

* '''Clustering''' 
: yields groups of (mutual) similarity, and dissimilarity from other groups
: clustering may not deal well with future data of the same sort, unless some care has been taken, so isn't necessarily a learner/predicter

* '''Vector quantization'''
: Discretely dividing continuous space into various areas/shapes
: which itself can be used for decision problems, labeling, clustering, etc.

* '''Dimensionality reduction'''
: what: projecting attributes into lower-dimensional data
: with the idea that the resulting data is (hopefully) comparably predictive/correlative (compared to the original)
: The reason is often to eliminate attributes/data that may be irrelevant or too informationally sparse
: see also [[#Ordination.2C_Dimensionality_reduction.2C_Factor_Analysis.2C_Multivariate_analysis]]

* '''Feature extraction''': discovering (a few nice) attributes from (many) old ones, or just from data in general.
: Often has a good amount of overlap with dimensionality reduction

* '''Control optimization''' problem - finding the best action of control in every (known) state of a system



Slightly more specifically:
* '''Reinforcement learning''' has a few different takes. 
: You can see it as any task where actor learns how to do things in an environment
: You can also see it as implementations that do so in more specific reward systems, which is an idea that comes back in a handful of different learning algorithms 


* '''Structured prediction''' refer to prediction problems that predict things more complex than single values
: specifically those that want multiple labels (amount potentially varying with the input), and their prediction relies on intermediate workings of the others
: which actually addresses implementation a little more than most others, in that running independent classifiers will give an answer but not be a structured prediction 


* '''collaborative filtering''' is a relatively new one, from the internet era
: consider e.g. people categorizing music, movies, products
: the contribution from each user is very sparse

<!--
* '''Data fusion''' means merging data from various sources, e.g. various sensors. 
: This often implies some sort of modelling, though this ''can'' be learned
-->


* others...

<!--
https://cs.stackexchange.com/questions/58131/are-neural-networks-a-type-of-reinforcement-learning-or-are-they-different
-->

===Related fields===
<!--

Parts of machine learning are just applied statistics (and a few specific parts of math), other parts are very much their own thing.

You can argue that statistics is more of a game of description and verification,
whereas machine learning is more prediction, which takes more assumptions and more engineering.


'''Data mining''' can apply statistics and learning,
but often has a more specific purpose, like confirming a theory or detecting patterns to explain,
but not the ''prediction'' that ML is often aimed at.

Similarly, there is statistics and ML in optimization theory and control theory,
and while the methods vary wildly, their application is guided by "what do I do right now?".


Even plain detection can involve prediction - say, counting people may track objects over
time and discount them by "that no longer matches how I predict a human can move".


You can argue that a lot of the techniques are just applied in different ways
by different communities, to the point that they don't even know they've reinvented the wheel under different names (see e.g. how many )



These days '''AI''' sometimes gets assumed to be all deep learning NN, 
but even today a lot of "AI" is actually much more classical methods just because they fit the problem more easily, if sometimes updated and mixed.




-->

===Descriptors of learning systems===

====Model-based versus model-free systems====

When you create a '''model''' of what to learn and where from, this can save a lot of computation, but will often not be adaptive to things that don't fit that model well.


'''Model-free''' solutions avoid assumptions and their bias and can learn more, but may be infeasible because of not enough information to stably learn from, or requiring too much time and computation to optimize parameters well enough.
<!--
(See e.g. moderately fancier neural net training easily being GPU-weeks (dozens of kilowatt-hours).
-->

<!--
Intuitively, model-free is

A model's assumptions are often initially fast, and eventually limiting.
Note there are some methods that try to consider this, e.g. 


Model-free often makes for a lot more possibilities 

-->


====Supervised , unsupervised, and more====

Classically we split things into supervised and unsupervised, and perhaps call thoes paradigms.


'''Supervised''' usually refers to the training processes that work (only) using already-annotated training data.
: For example many document classification methods, least-squares fitting, basic neural network back-propagation 
: This often means manually generating training data, which is often a slow process, and not always 


'''Unsupervised''' refers to processes that work without intervention, often meaning they work without annotation.
: For example, clustering documents based on similarity, [[self-organizing maps]]



We've thought up other terms since then to refer to variations.


'''Semi/lightly supervised''' usually means there is an iterative process, which needs only minimal human intervention, e.g. to require manual intervention only for unclear cases.



'''Self-supervised''' learning often refers to cases where you can automatically refine a solution, e.g. by automatically creating labels for further training.

This tends to work better for relatively narrowly defined tasks, say, learning to segment humans, within a piece of video at a time.

Note that self-supervised can variably be seen as
: applying automatic supervision to an unsupervised question
: a flavour of lightly supervised, as it can be used to label a bunch of data more quickly <!--(useful e.g. when it's easier to verify than generate labels)-->



'''Reinforcementt learning''' could be another entry in that list, in that it's a fairly differerent category of expressing problems and solutions.

Problem-wise, RL is those where an actor learns how to do things in an environment.

There generally is no labeled data, but there ''is'' a way of saying what is preferable and what fails to work.
Not in the form of "this was the correct immediate response (input/output pair)", and more that the eventual outcome was good or bad.

Classically, RL it was a bit narrower, often expressed in things like like a [[markov decision process]], 
in part because that was a basic and clear way to express ''what'' to reward and how (often solved via [[dynamic programming]]), and it might give a a more complete description than some other methods, which is something you'ld want around control optimization problems.


It is also used in a wider sense of any sort of reward-based learning, i.e. "have an idea of outcome, punish the bad, reward the good"

Reward itself can be 
: looser way (e.g. genetic algorithm just seeing how far things get)
: more direct (e.g. control optimization calculating reward per unit time within a horizon)

This is related to more finer distinctions with in RL, like
* episodic RL - episodic tasks have recognizable chunks of events to learn from, say each game of chess
* continuous RL - continuous tasks never, meaning you reward on the shorter term


Being so broad, it often lies somewhere between supervised and unsupervised, 
roughly because you're telling it what you want, but not how to get there.


Implementation-wise, that comes back in various methods, in different forms - see e.g.
: e.g. [[Markov Decision Process]] 
: [[Q-learning]]
: evolutionary/genetic algorithms
: arguably a bunch of NN
...but note that there are quantifiable, sometimes huge differences between many of those, e.g. NNs (and problems for which we prefer NN) have a huge state space compared to MDPs.



=====More on RL=====
<!--
You would choose reinforcement learning where complete analysis is too complex

Which e.g includes various control optimiziation problems when a complete analysis (e.g. closed form analysis) is not possible, e.g. because there are a lot of states, or the underlying structure is not simple. 

...because if it ''is'' simple, you can often use dynamic programming to e.g. do an exhaustive(-enough) search.


And RL is one of a few approaches that can give you a reasonable approximation regardless.


You might also use one where a simpler approach is too basic, or not easily defined or easily trained.

Some of those may rule out some RL methods too, like Q-learning when there is no clear way to differentiate states, too many states (and/or too little training to actually update all its cells)


There are many distinct ways you can do that, and there are many methods qualify to some degree, including neural network training.


There are a few footnotes to that
* episodic ''requires'' a finish. Solving mazes would be episodic, but if your agent runs infinite circles in a maze, not so much anymore.

* Some can be seen as both, like balancing, 
: continuous in that it is mostly immediate reaction that will determine whether you fall soon
: episodic in that your collection of choices determined how long you balanced

* it affects how you do rewards. For example, 
: in episodic RL you may e.g. reward all the steps in that game,
: in continuous RL you may reward more often, and reward recently taken choices more

* episodic may be easier to (also) analyse



Often means steering such an agent, and often to learn to imitate something from near-scratch, or perhaps train a ''simulation''.
-->

See also:
* http://en.wikipedia.org/wiki/Reinforcement_learning

* LP Kaelbing, ML Littman, AW Moore.  (1996) "{{search|Reinforcement learning: A survey."}}
* RS Sutton, AG Barto (1998) ''{{search|Reinforcement Learning: An Introduction}}''

====Inductive versus deductive systems====

<!--
This one is actually fuzzier than is seems.

The reference is to relatively formal logic (in philosophy), where
* [[inductive inference]] is going from smaller facts/observations to "probably true in general" statements
* [[deductive inference]] is going from universal truths to more specific statements (and often more applied ones) 


'''Inductive learning''' would then refers to learning that takes data and generalizes from those examples,
to be able to deal with similar unseen cases.


But then, what would '''deductive learning''' mean? (I cannot find a lot of words but roughly zero examples)


A teacher deductively creating example cases from an already-known generalized model, e.g. as a means to do transfer learning? 

Maybe, but then you're just transferring the list of ''specific'' things a teacher knew already.

Because if you're doing more, that would probably still be learning general knowledge - and in the "probably in general", i.e. inductive way, rather than the 'always in specific' that deductive does. 



(Or were we just pointing out that some learners tend to have inductive steps that model from data, and deductive steps that try to predict new data?)



Deductive learning would probably refer to a system trying to find ''descriptive'' truths,
based on general rules, the means to break those into parts, create a space of all possible hypotheses, and see which are true.

Say, it could learn from a whole bunch of weather data that there ''have'' to be clouds for there to be rain. 


Or take existing hypotheses and see if you can make it narrower and stronger but narrower.

Less likely than inductive to [[overfitting]] - but probably often [[underfitting]] instead.


But even in that hypothesis space it would be tempting to generalize, and use probabilities.

---

H Madala (1991), "{{search|Comparison of Inductive Versus Deductive Learning Networks}}"

https://content.wolfram.com/uploads/sites/13/2018/02/05-2-6.pdf


---


Some inductive learning can sometimes be usefully seen, and approached, as a search in a space of possible hypotheses.

The hypothesis space can finitely include all possible hypotheses about the training data, and choose one so that it hypothesizes correctly for every single one. Of course, this is overfitting: It would just be a description of all of the data. 

FIND-S is a simple algorithm to work a little better. It comes down to:
* looking for the most specific hypothesis (or hypotheses; consider that these could ignore parameters) consistent with the trainign data. 
* Based on conjunction of constraints
* If the training data converges, this should find a simple hypothesis to apply to unseen data with the same attributes.
* Problem: It finds only one, and not necessarily the best for anything but the training data 
* Noise will easily disturb into too general hypothesis
* Introduces '''restriction bias''' in that we can have hypothesises with only discrete-valued attributes and can only specify a specific value or "don't care," not a subset of possible values, in a single hypothesis.

This can be generalized into also having disjunction, negation and more, but this ends up in a mess: Only the training data could be unambiguously classified, because it is our training data. Unseen data can be classified with a plethora of hypotheses, each of which are as valid as the other. The only vaguely viable thing would be to take the subset of all valid hypotheses and use that somehow, but this is not a good solution. 


This teaches that we in fact need bias to be able to generalize, usually through something refered to as '''inductive bias''', which is basically the `inate' set of assumptions a learner uses. Algorithms will usually differ in types of bias, so when this bias matches that of the data the algorithm will work better for that data.

It also means that the more accurate prior knowledge you have, the higher the quality of the learning - which makes intuitive sense. On the other hand, embedding too much prior knowledge will dismiss what is seen by it to be unusual data.






In this context you could also put some explanation on 
'''transductive learning''' which instead of generalization uses one specific example to handle another.

and even abductive learning.
-->

====Transfer learning====

Transfer learning is the idea that you could use knowledge from other systems.

<!--
In some cases, particularly model-based systems, this might be straightforward parameters, or otherwise fairly obvious.


In other, e.g. model-free ones, it may be far from obvious how exactly the system does what it does, and the best you can do is e.g. reinforcement learning until the new system answers similarly to the last.


Neural nets tend to not allow much transfer learning unless specifically designed to do so.


: this doesn't really work on classical neural nets
: or RNNs or their variations, basically because what it learned is entangled
: CNNs may allow it a bit more if well designed, e.g. when your change really just implies changing the last one or two layers (e.g. classification) but not the rest (learning of what kind of features are interesting to base that on)
* when transfer learning ''doesn't'' work, you basically need new training data





-->

====State observers====

'''State observers''' / '''state estimation''' will estimate the internal state of a real system,
measuring what they easily can, and estimating what they need to. [[Optimization_theory,_control_theory#State_observers_.2F_state_estimation_.28and_filters_in_this_sense.29]]

This typically a singular state in control theory without much state,
but can also be useful to present data to a learning system.


Related are the (introduced by Kalman)
* [https://en.wikipedia.org/wiki/Observability observability] criterion 
: the idea that the states of a system can be reasonably inferred from knowledge of its outputs. 
: (which seems to include that all states the system can be in are known)
: in practical terms, that a good set of sensors lets you build a model that covers all its important variables.{{verify}}

* [https://en.wikipedia.org/wiki/Controllability controllability] criterion
: the idea that you can actually guide a system through all states.{{verify}}


Both are related to building something that is likely to be stable in a knowable way.

Again, concepts more related to control theory, but more widely applicable.

===Properties and behaviours of learners===


====Underfitting and overfitting (learners)====

'''Underfitting''' is when a model is too simple to be good at describing all the patterns in the data. 

Underfitted models and learners may still generalize very well, and that can be intentional, e.g. to describe just the most major patterns.

It may be hard to quantify how crude is too crude, though.



'''Overfitting''' often means the model is allowed to be so complex that a part of it describes all the patterns there are, meaning the rest ends up describing just noise, or insignificant variance or random errors in the training set.

A little overfitting is not disruptive, but a lot of it often is, distorting or drowning out the parts that ''are'' actually modeling the major relationships.

Put another way, overfitting it is the (mistaken) assumption that convergence in the training data means convergence in all data.



There are a few useful tests to evaluate overfitting and underfitting. 

<!--
via cross validation can be a useful test, as it will reveal predictions that aren't even true in other parts of the training data.
It may also help estimate where a good balance lies.


Notes:
* The [https://en.wikipedia.org/wiki/Bias%E2%80%93variance_tradeoff Bias–variance angle] 
: see e.g. http://datascience.stackexchange.com/questions/361/when-is-a-model-underfitted





For learners
* a pathological case would be to have a model that is an exactly rule-based description of all the training data, with exactly the same complexity as that data


* overfitted learners often means very little generalization

* ...and so has a limited ability to deal with cases that don't look very much like ''specific'' cases in the training set.


Good ways to avoid overfitting depend a little on the type of learner you're using.
If you're halfway involved in the analysis you're doing, and not fully automating analysis,
applied gut feeling tends to avoid most of it already.


See also:
* http://en.wikipedia.org/wiki/Overfitting
-->


====Interpretability====
<!--


'''Explainable AI''' is mostly this applied to NNs, 
as free-form NNs tend to not be interpretable, and designed ones are only somewhat better.



-->

=More concepts, some shared tools=
==On the theory / math side==
====Stochastic processes, deterministic processes, random fields====

A '''deterministic process''' deals with possible determined cases, with no unknowns or random variables.


A '''stochastic process''' (a.k.a. '''random process''') allows indeterminacy, typically by working with probability distributions.

A lot of data is stochastically modeled, often because you only need partial data (and often only ''have'' partial data to start with).


Hybrid models in this context means mixing deterministic and stochastic processes



A '''random field''' is random function over an arbitrary domain. 

When that domain was time, we would probably call it a random process,
but since this is basically a generalization that says it's not necessarily necessarily time, or one-dimensional, or real-valued, we think of it as ''space'' instead, and [https://en.wikipedia.org/wiki/Field_(mathematics) field] becomes the more apt description. {{verify}}



<!--
Relatedly:
: A '''conditional random field''' turns up in 

: A '''markov random field'''
-->

See also:
* http://en.wikipedia.org/wiki/Stochastic_process
* http://en.wikipedia.org/wiki/Deterministic_system
* http://en.wikipedia.org/wiki/Random_field
* http://en.wikipedia.org/wiki/Conditional_random_field

====Markov property====

the '''Markov property''' is essentially that there is no memory, only direct response: that response of a process is determined entirely by its current state, and current input {{comment|(if you don't already define that as part of the state)}}.

More formally, "The environment's response ''(s,r)'' at time ''t+1'' depends only on the Markov state ''s'' and action ''a'' at time ''t''" [http://en.wikipedia.org/wiki/Markov_property]


There are many general concepts that you can make stateless, and thereby Markovian:
* A '''Markov model''' is a [[stochastic model]] with the Markov property

* A '''Markov process''' is a [[stochastic process]] with the Markov property [http://en.wikipedia.org/wiki/Markov_process]

* A '''Markov chain''' refers to a Markov process with finite, countable states [http://en.wikipedia.org/wiki/Markov_chain]

* A '''Markov random field''' [http://en.wikipedia.org/wiki/Markov_random_field] <!--is a random field, i.e. a set of variables, that satisfy the markov property 
:: meaning-->

* A '''Markov logic network'''  [http://en.wikipedia.org/wiki/Markov_logic_network]

* A '''Markov Decision Process (MDP)''' is a decision process that satisfies the Markov property 

* ..etc.

<!--



There are different variants of markov models:
* decision making processes, versus describing system behaviour
* having a complete model of the relevant apsects, or only a partial one.

Basically, describing with a complete model is a markov chain, 
describing with a partial model is a hidden markov model.


The markov chain is the simplest variant.




A state machine is often deterministic 



A markov model is 
sorta-deterministic, 
in that while it says something about state at time t+1 based on state at time t,
it does so with probablistic estimation.

In other words, it aims to make a good guess, does not pretend to be perfect.


Yes, you can make Markov-model implementations of a purely deterministic
state machine, but this mostly proves
* compatibility in that both are discrete-time 
* that the specific cases where the interaction is already known can be modeled by something that
can also be more fuzzy


Similarly, a Markov ''chain'' can be modelled by a finite state machine



Marchov chain is a discrete-time stochastic process



-->

====Markov Decision Process====
<!--
Consists of 
* S: a number of states
* A: a number of actions
* R(s,a): a reward function 
* T: a table of effect of each action in each state
:: it's markovian in that this table assumes the effect depends only on the most recent state


T can be 
* deterministic
: (state,action) leads to a new state

* stochastic
: (state,action) has estimated probabilities for the likeliness of each new state

Implicitly assumes observability, in that the new state must exist already.


https://www.cs.rice.edu/~vardi/dag01/givan1.pdf

'''Partially Observable MDP'''

-->


====Belief network====
<!--
A belief network, a.k.a. Bayesian network



https://artint.info/html/ArtInt_148.html
-->





====Log-Linear and Maximum Entropy====
{{stub}}

<!--

I general, we often want to make independence assumptions to make a problem more tractable.

That will come at the cost of the amount the model will fit.


Log-linear models make no independence assumptions{{verify}}.



Maximum Entropy uses log-linear and tries to maximize the likelihood of the training data.

The idea seems to 
be a model that is most like uniform distribution
''and'' making the least independence assumptions. 

It is, however, still inductive learning, so it easily has problems like [[overfitting]].
-->

====Bayesian learning====
{{stub}}

Bayesian learning is a general probablistic approach, often specifically used as a probablistic classifier. 

Mathematically it is based on any observable attribute you can think of, 
and the math requires Bayesian inversion (see below).

Many basic implementations also use the Naive Bayes assumption (see below), because it saves a ''lot'' of computation time, and seems to work almost as well in most cases.


=====Bayesian classifier=====

======Bayes Optimal Classifier======
<!--
A Bayes Optimal Classifier considers all possible hypotheses in the hypothesis space, and as such its solution is unbeatable on average.

However, it is intractable for all but the simplest problems, so it is not often mentioned outside of theory.

-->
======Naive Bayes Classifier======
<!--
Simple, tractable for pretty complex problems.

'Naive' in that it assumes all attributes are independent.
This saves a lot of computation, and does not remove as much accuracy as you might think.

See [[Naive Bayes]]

-->

=====Bayesian (Belief) Network =====
<!--
Names include
: (Bayesian) belief network
: Bayesian model
: Bayesian network
: Bayes network
: Bayes(ian) model 
: probabilistic directed acyclic graphical model


An acyclic graph where each node conditionally depends only on its direct predecessors, and the existence of the edges define (in)dependence between variables.

Allows selective inclusion of prior knowledge.

Not entirely unlike neural networks, but bayesian networks are more directly about relation of variables, whereas NNs can be structured in a more flexible way.


[https://en.wikipedia.org/wiki/Deep_belief_network Deep belief network]
-->

===Curse of dimensionality===
The '''[http://en.wikipedia.org/wiki/Curse_of_dimensionality curse of dimensionality]''' is the idea that each dimension you add to your model makes life a little harder.


Intuitively, this is largely because a lot of these dimensions may be noninformative, but will still contribute to everything you do.

If each counts equally, that lessens the effect of every ''useful'' dimension.


A common example is distance calculations. As you add dimensions, the contributing value of any single one decays, meaning the bulk of less-expressive are going to overpower the few good ones.

It's very likely to drown any good signal in a lot more noise (unless your method explicitly learns this instead of using a standard metric). 

And any learning build on such a metric is going to have a harder time.
<!--
(unless you did a ''lot'' of work up front, e.g. do to implementation-specific dimensionality reduction so that every one is actually informative)

It's certainly a reason we do dimensionality reduction, but that needs to be done in an informed way to actually help.




For example
* you need proportionally more data for decent training of that model.

* things like distances may becomes less meaningful

* anything that relies on distances (e.g. clustering) will have issues as a result

* a good amount of samples and examples for to train each dimension will be (dimensions) times bigger, so take more storage, and time to process


Since the volume increases so fast, you will probably have sparsity problems.



'''Curse or blessing?'''

There is an argument for the '''blessing of dimensionality'''.

The curse argument assumes 
you have some abstract n-dimensional space where 
you have no idea how they relate, 
that for any one problem there are a few good dimensions and the rest are noise,
and that using them naively and equally means the bulk will overpower the signal.

Aside form there being alleviations to that, if you're adding dimensions based on needing them for the specific problem, you may find that they are ''not'' distinct, and tend to agree with others, in ways that various algorithms will pick up on.

: local minima fall away more than a clear global maximum {{verify}}



-->

===Kernel method===
<!--

The kernel method seems to have meen introduced by SVM, but is a more widely useful idea. 

Others that use it include Linear Discriminant Analysis (LDA), Principal Components Analysis (PCA), ridge regression, spectral clustering - and you could apply it anywhere where you know it's useful for the input data.


The point is to turn any linear model to something that deals with nonlinear data, 
using a mapping (often selected to be suited for the data) into a different space that makes it easier to work with -- often a higher-dimensional one.

In the case of SVM typically for for linear separability.


The linear classifier in the higher-dimensional space is effectively a non-linear classifier in the original space, in a way that depends on how you mapped the data.

Intuitively, any case where you can think of a function that will warp the data so that there is a straight decision boundary.


For example, if you want to detect a 2D circle around the origin, you could create dimensions based on x^2 and y^2, which means what is radius in the original space (and effectively a round thing) is a distance in this new space, which can be split with a line/plane (linear).



That higher-dimensional space is often only ''implied'' by the kernel function, 
but in the case of various implementations, including SVM, the coordinates in that higher-dimensional space are not explicitly calculated, because it turns out to be easier (and often computationally cheaper)
to calculate the distances between data pairs directly, rather than mapping to coordinates and then using a generic metric.

This also makes it somewhat easier to deal with data that is not vectors.



(note that NN doesn't really need this, as multiple layers learn nonlinear in their own way{{verify}}, but it can still help avoid a layer or two and training time)

-->

https://en.wikipedia.org/wiki/Kernel_method

===Statistical modeling===
<!--
Machine Learning leans on statistics (ideally, anyway. Not everyone cares about validation).
-->




====Regression analysis====
<!--


Regression analysis models the relationship between one dependent and one (or more) independent variables, via as-of-yet-unknown parameters.

For each independent variable, it estimates a function (the regression function) mapping it to the dependent variable, with one or more parameters (as deemed sensible).

While there are many variants, people easily relate it to fairly linear and simple models, in part because 


Often estimates the [[conditional expectation]]



Regression glossary:
* '''linear''' regression models a linear predictor function
: typically a least squares estimator

* '''simple''' regression indicates a single independent/explanatory variable


* Ordinary least squares [https://en.wikipedia.org/wiki/Ordinary_least_squares]

* total lease squares [https://en.wikipedia.org/wiki/Total_least_squares]
: generalization of Deming (and orthogonal) regression

* Deming regression [https://en.wikipedia.org/wiki/Deming_regression]
-->

<!--
'''Mean Squared Error''' (metric)

Measures the difference between the estimator/estimation and what is estimated from.

A bunch of data modelling tries to minimize MSE.

https://en.wikipedia.org/wiki/Mean_squared_error
-->


=====Linear regression=====
<!--

Linear regressing finds the best-fitting line between two variables,
under the assumption it's a straight line with an offset.

While it sounds almost too basic, it is a better-than-nothing fit 
and already helps to suggest whether two things may be correlated,
so can help in [[feature selection]]


Linear regression is a small building block with many uses,
but one of them is evaluating individual features


----


Often calculated via least squares - which is basically short for "if we sum the square of the vertical distances to the best-fit line, this line gives the mimimum of all possible lines".


Which implies we can rewrite it into an error function for fitting - said sum of squared errors.

Which does little nothing for the basic case, but can be a useful basis to expand on for more specific cases.

-->


=====Logistic regression=====
<!--

Regresssion model where the dependent variable is [[categorical variable|categorical]] -- often specifically binary, as more-categories are handled by multinomial logistic regression (if unordered) or ordinal logistic regression (if ordered).

https://en.wikipedia.org/wiki/Logistic_regression
-->
<!--

Multinomial logistic regression

https://en.wikipedia.org/wiki/Multinomial_logistic_regression


Ordinal logistic regression

https://en.wikipedia.org/w/index.php?title=Ordinal_logistic_regression
-->


==Feature selection==

https://en.wikipedia.org/wiki/Feature_selection

==Graph based statistical modeling==
TEMPORARILY ELSEWHERE

==Dimensionality reduction==
===As a wide concept===

Dimensionality reduction can be seen in a very wide sense, of creating a simpler variant of the data that focuses on the more interesting and removes the less interesting.


Note that in such a wide sense a lot of learning is useful as dimensionality reduction, just because the output is a useful and smaller thing, be it clustering, neural networks, whatever. 

But in most cases it's also specific output, minimal output for that purpose.


Dimensionality reduction in practice is much more mellow version of that, reducing data to a more manageable form.  It historically often referred to things like factor analysis and multivariate analysis, i.e. separating out what seem to be structural patterns, but not doing much with them yet, often acknowledging that we usually still have entangled surface effects in the observations given, and our direct output is probably still a poor view of the actual dependent variables that created the observations we look at. 
(Whether that's an issue or not depends largely on what it's being used for)


Reducing the amount of dimensions in highly dimensional data is often done to alleviate the '''curse of dimensionality'''.[https://en.wikipedia.org/wiki/Curse_of_dimensionality]

Said curse comes mainly from the fact that for every dimension you add, the implied volume increases quicker and quicker.

So anything that wants to be exhausitve is now in trouble.
Statistics has an exponentially harder job of proving significance (at least without exponential amounts more data),
Machine learning needs as much more data to train well,
optimization needs to consider all combinations of dimensions as variables, etc.


Distance metrics are funnier, in that the influence of any one dimension becomes smaller, so differences in metrics smaller - and more error-prone in things like clustering.
{{verify}}

It's not all bad, but certainly a thing to consider.


<!--

In includes organizing data into a simpler form, classifying and/or partitioning in the process, often to ends like extracting patterns, or reducing the dimensionality of the data, sometimes so much as to draw simple conclusions. Along with those go various methods of to testing the apparent accuracy of the new form, and statistically proving it isn't just one bad solution among many.


Methods or results are rarely provably optimal, but you can usually estimate how much they agree with the input data.
-->
<!--
Like statistics, you reduce data into less data but make implicit decisions along the way, and like statistics, some methods are better for certain types of data and may be structurally weaker than others.


Pattern recognition may work on a settled, well-dimensioned form of data, where specific methods may be applied and known to be good. In certain other cases, the dat is in a much looser form for the question to be answered. Consider, for example, an AGCT sort of string of DNA - it is not immediately clear where sequences (or even codons) start or end.
-->

===Ordination, Factor Analysis, Multivariate analysis===
{{stub}}

(See also [[Statistics#Multivariate_statistics]])


[http://en.wikipedia.org/wiki/Ordination_%28statistics%29 Ordination] widely means (re)ordering objects so that similar objects are near each other, and dissimilar objects are further away.


Ordination methods are often a step in something else, e.g. be good data massage before clustering.

It can become more relevant to higher-dimensional data (lots of variables), in that ordination is something you watch
(so sort of an implicit side effect) in the process of dimensionality reduction methods. 

Of course, different methods have their own goals and focus, different requirements, and their own conventions along the way.

Typical methods include PCA, SVD, and 


<!--
Many methods resemble each other. Some are different in their fundaments, 
some are largely equivalent,
some are actually much the same but have different names in different fields (and a few conditions/assumptions specific to that field),

 (often being defined as a lower-variate expression of much the same information (in terms of a metric, often distance / variance).

For example, in basic eigendecomposition you get same-sized output, but with the most variance explanation in the first variable, the second most in the second, etc, so you can take the first few and get a decent approximation of the largest patterns in the data.

This can also prove useful in efficient-to-execute clustering, some learning algorithms, efficient approximated storage, and such.
-->

<!--
http://ordination.okstate.edu/
-->

<!--

This makes it hard to make a short summary/typology, and easier to do individual comparisons.
For example, take PCA, MDS, and SVD.


In their goal they are largely the same: They compute an orthogonal transform that de-correlates the variables. And make it easy to address/keep the most significant ones. 

Numerically this is often solved by either SVD of the data matrix (after centering), or an eigendecomposition of the covariance matrix.



MDS is itself a type of analysis, a description, or rather a set of related descriptions, where 'classical MDS' is the more general one.
The solution to classical MDS is often an eigenvalue method (frequently PCA). Other MDS variants are more complex.


Classical MDS minimizes dimensions while preserving distance, and e.g. PCA minimizes dimensions while preserving covariance (it works on a covariance matrix), which is equivalent ''if'' the covariance is based on euclidean distance. 

And not if it's another metric. So you could say that PCA solves or ''is'' a specific case of MDS.


In turn, that descirption of PCA is still a description - that of maximizing the explained variance.
If written down more formally, it turns out this is equivalent to the eigenvalue problem,
of finding eigenvalues and eigenvectors of the covariance matrix.  
Which is why PCA is usually explained as being that eigendecomposition of the covariance matrix.

SVD on the data matrix itself (after [[mean centering]]) also 

PCA of matrix X is eigendecomposition of XX<sup>⊤</sup> (note: symmetric, and called a scatter matrix)
SVD 


The results of SVD and PCA are often much the same in expression, though often not numerically.


For pragmatic reasons SVD can be preferable to PCA the covariance-matrix way, in that the latter's calculation loses some precision (because for some matrices).








For example, there are a handful of eigendecomposition-based principal-factor style ordination (e.g. PCA and some variants, some variants of MDS, ): When your input is a (variance-)covariance matrix or correlation matrix, the resulting eigenvectors correspond to principal components, and the eigenvalues to the relative amount of variance explained by that principal component.


The principal components ''may'' show a fairly isolated effect that you ''may'' be able to name. (This depends on the application, and is often only true for the first few).
But keep in mind that they are in the end mathematical constructs and should not be taken too literally.


Often enough, when you think dimensionality reduction would be a good idea for some data it is, and it often turns out that most of the variance is covered by the first dozen PCs.

The amount of eigenvectors/components to extract/use is fairly arbitrary and ad hoc.
As a rule of thumb, when adding further PCs makes little difference (e.g. to the correlation with the original data set), you have enough to work with. If removing one changes the data noticeably, you probably shouldn't have.

See also scree plots, which plot the amount of the overall variation delivered by each PC. It might be nice to also get a cumulative fraction of variance covered by the first that-many PCs (and perhaps the correlation to the original data).

-->
<!--
Some of the more better known names in ordination include:
-->


===Factor Analysis, Principal Component Analysis (PCA), and variants===
<!--
Eigenvector-style analysis with an Euclidean metric.

Closely related to Karhunen-Loeve expansion{{verify}}.


Practically, these (and various of the below) are useful when when you suspect there is redundancy between variables and wish to express much the same data in fewer, artifical variables that express most of the variance (and show much the same correlation between X).
(...and, in various cases, in more axis-aligned ways.)



Say you have data for six different variables,
and you figure there are two main things expressed, so rather redundantly in them.
Assume the first reason is mostly expressed in variables 1 through 3, the second is in 4 through 6.

This means you could express (C is component, X is variabe)
 C1 = 0.4(X1) + 0.4(X2) + 0.4(X3) + 0.0(X4) + 0.0(X5) + 0.0(X6)
 C2 = 0.0(X1) + 0.0(X2) + 0.0(X3) + 0.4(X4) + 0.4(X5) + 0.4(X6)


It would be unusually lucky to find them aligned with the dimensions/axes that way.

Many of these analyses try to find that transform for you,
under varying assumptions.


For example, PCA takes a space of correlated variables and tries to find a (linear) transform into a space of uncorrelated variables. The typical example is an arbitrarily positioned and rotated ellipse-shaped cloud in 2D that 

PCA is named for Principal Components, 
where a principal component is a linear combination of optimally-weighed observed variables.




Functionally, it projects input data into a lower-dimensional orthogonal subspace 
that captures as much of the variation of the data as possible. This is ''usually'' used for dimensionality reduction.


It is originates in the [https://en.wikipedia.org/wiki/Principal_axis_theorem principal axis theorem] 
and was developed by Pearson in 1901, and independently by Hotelling in the 1930s.

There are a set of closely related developments (identical in many but not necessarily all respects), or 
of close variants are known in different fields as:
* the discrete Karhunen–Loève transform / Kosambi-Karhunen–Loève transform (KLT) (signal processing)
* the Hotelling transform (multivariate quality control)
* proper orthogonal decomposition (POD) (mechanical engineering)
* Empirical orthogonal functions (meteorology, geophysics)
* empirical modal analysis (structural dynamics).
* spectral decomposition (noise and vibration)
* Schmidt–Mirsky theorem (psychometrics), 
* empirical orthogonal functions (EOF) (meteorology), 

* Eigenvector decomposition (linear algebra)
* Singular Value Decomposition (SVD) (linear algebra)

* Factor analysis (),
* Eckart–Young theorem 
* empirical eigenfunction decomposition, 
* empirical component analysis
* quasiharmonic modes 


These are not all the same, details will vary.

-->
<!--

The field of eigenvector ''approach'' is wider, and includes similar analyses, such as classic MDS.


PCA is technically part of a wider group of techniques, Factor Analysis[http://en.wikipedia.org/wiki/Factor_Analysis]. 
PCA is the best known and the most used of them.


Methods can be divided into global and local(-and-typically-iterative) solutions.

The global are the most basic approaches:
* eigenvalue decomposition of a data covariance (or correlation) matrix 
: requires the computation of the covariance matrix, effectively making the whole O(n<sup>np<sup>2</sup></sup> (p is data dimensionality, n is amount of samples))
: simply ''does not scale'' to large p, i.e. higher-dimensional data

* singular value decomposition of a data matrix
: similar issue to the above


The local ones:
* iterative: 
: calculates first without the covariance matrix
: iteration: subtract that solution and do again for the second, etc.
: flaws: errors carry over, so only sensible for a smallish amount if 

* NIPALS (Non-linear iterative partial least squares)
: efficient at only calculating the first few principal components
: probably the most standard PCA 

: Wold et al., 1987, "{{search|Principal Component Analysis wold 1987 Chemometrics and Intelligent Laboratory Systems|Principal Component Analysis}}"



sequential methods
: updates state as new examples come in. 




See also:
* https://en.wikipedia.org/wiki/Lanczos_algorithm



http://www.statsoft.com/textbook/stfacan.html


As a commonly used method, it has various variations, including:

=====Principal Coordinate Analysis (PCoA, PCoorA, PCO)=====


=====Kernel PCA=====
Basically the application of kernel methods[http://en.wikipedia.org/wiki/Kernel_methods]
before doing the PCA.




-->

===Correspondence Analysis (CA)===
Conceptually similar to PCA, but uses a Chi-square distance,
to be more appicable to [[nominal data]] (where PCA applies to [[continuous data]]).


See also:
* http://en.wikipedia.org/wiki/Correspondence_Analysis

===Multi-dimensionsional scaling (MDS)===

Refers to a group of similar analyses, with varying properties and methods,
but which all focus on ordination<!--:
They find an embedding in a metric space (and a suitable dimension)
based on dissimilarity(/similarity) of the items it shows.

Eigenvector-based ordination, one of the better known among its relatives.
-->

Commonly mentioned types of MDS include:
* Classical multidimensional scaling, a.k.a. Torgerson Scaling, Torgerson–Gower scaling. <!-- 
** apparently ensures we are working on similarities, then executes PCA?{{verify}}   Minimizes a loss function.-->

* Metric multidimensional scaling

* Non-metric multidimensional scaling


It is regularly used to provide a proximity visualization, so the target dimensions may be two or three simply because this is easier to plot.


Depending on how you count, there are somewhere between three and a dozen different MDS algorithms.

Some MDS methods closely resemble things like PCA, SVD, and others in how they change the data.
Some more generic MDS variants are more on the descriptive side, so can be ''solved'' with PCA, SVD, and such.


A ordination, most try to not change the relative distances, but do change the coordinate system in the process.



=====Input=====

Input to many method is a similarity matrix - a square symmetric matrix often based on a similarity metric.
Note some similar methods may be based on ''dis''similarity instead.


At a very pragmatic level, you may get 
* a ready-made similarity matrix

* items plus a method to compare them

* a table of items versus features (such as coordinates, preferences), with a method to compare them

* perceived similarities between each item (e.g in market research)

There is little difference, except in some assumption like whether the feature values are Euclidean, independent, orthogonal, and whatnot.



=====Result evaluation=====
MDS solutions tend to be fairly optimal, in that ''for the amount of target dimensions'' you will get the solution's distances correlating to the original data's distance's as well as they can.

There are still a number of things that help or hinder accuracy, primarily:
* the choice of input values
* the choice of target dimensions (since too few lead to ill placement choices)
* (to some degree) the type of MDS
* methods that have cluster-like implementations may be sensitive to initial state


You probably want to see how good a solution is. 

The simplest method is probably calculating the [[correlation coefficient]] between input (dis)similarity and resulting data (dis)similarity, to show how much the MDS result fits the variation in the original. By rule of thumb, values below 0.6 mean a bad solution, and values above 0.8 or 0.9 are pretty good solutions (depending on the accuracy you want, but also varying with the of MDS).

Other methods include 
Kruskal's Stress, 
split data tests
data stability tests (i.e., eliminating one item, see if result is similar)
test-retest reliability [http://en.wikipedia.org/wiki/Test-retest]


=====Algorithms=====

Note that in general, correlation can be complete (if k point in k-1 dimensions, or distances between any two items are equal whichever way they are combined, e.g. if distances are those in euclidean space), but usually is not. 
The output's choice of axes is generally not particularly meaningful.


Probably classically the most common example is is '''principal coordinates analysis (PCO, PCoA)''', also known as '''Classical multidimensional scaling''', '''Torgerson Scaling''' and '''Torgerson-Gower scaling''', which is a single calculation step so does not require iteration or convergence testing. 

See also (Torgerson, 1952), (Torgerson, 1958), (Gower, 1966), [http://www.google.com/search?hl=en&q=site%3Ar-project.org%20CMDSCALE CMDSCALE in R]

{{comment|(Note: PCO (Principle Coordinate analysis) should not be confused with PCA (Principle ''Component'' Analysis) as it is not the same method, although apparently equivalent when the PCA kernel function is isotropic, e.g. is working on Euclidean coordinates/distance)}}{{verify}}


The first dimension in the result should capture the most variability (first principal coordinate), the second the second most (second principal coordinate), etc.
The eigenvectors of the input distance matrix yield the principal coordinates, and the eigenvalues give proportion of variance accounted for. As such, eigenvalue decomposition (or the more general singular value decomposition) can be used for this MDS method. 
(The degree to which distances are violated can be estimated by how many small or negative eigenvalues. If there are none (...up to a given amount of dimensions...) then the analysis is probably reasonable), and you can use the eigenvalues to calculate how much of the total variance is accounted for{{verify}} - and you have the option of choosing afterwards how many dimensions you want to use (which you can't do in non-metric).






'''Metric (multidimensional) scaling''': a class of MDS that assumes dissimilarities are distances (and thereby also that they are symmetric). 
May be used to indicate PCO, but is often meant to indicate a class based on something of a generalization, in that the stress function is more adjustable. 
The optimization method used is often [http://en.wikipedia.org/wiki/Stress_Majorization Stress Majorization] (see also SMACOF [http://en.wikipedia.org/wiki/Stress_majorization#The_SMACOF_algorithm] (Scaling by Majorizing A COmplicated Function)).






On iterative MDS methods: 
minimize stress 
no unique solution (so starting position may matter)
* stress-based MDS methods 
* may be little more than non-parametric version of PCO{{verify}}




'''Non-metric multidimensional scaling''' can be a broad name, but generally find a (non-parametric) ''monotonic'' relationship between [the dissimilarities in the item-item matrix and the Euclidean distance between items] and [the location of each item in the low-dimensional space].

The optimization method is usually something like isotonic regression (which is due to monotonicity constraints). Methods regularly have both metric and non-metric parts, and non-metric scaling in the broad sense can describe quite varying methods (see e.g. Sammon's NLM).

Note that the the monotonic detail means that ranking of items ends up as more important than the (dis)similarities. This may be a more appropriate way of dealing with certain data, such as psychometric data, e.g. ratings of different items on an arbitrary scale. 

Non-metric MDS may give somewhat lower-stress solutions than metric MDS in the same amount of dimensions.{{verify}}

Also, certain implementations may deal better with non-normality or varying error distributions (often by not making those assumptions).



Examples:
* Kruskal's non-metric MDS{{verify}}
* Shepard-Kruskal Scaling{{verify}} (and {{verify}} whether that isn't the same thing as the last)

* Sammon non-linear mapping [http://www.google.com/search?hl=en&q=%22R%20Documentation%22%20%20sammon]



Variations of algorithms can be described as:
* '''Replicated MDS''': evaluates multiple matrices simultaneously

* '''Three-way scaling'''

* '''Multidimensional Unfolding'''

* '''Restricted MDS'''






Multidimensional scaling (MDS) [http://www.analytictech.com/networks/mds.htm]
* classical MDS (quite similar to PCA under some conditions, apparently when you use euclidean distance?) 
** (Difference matrix -> n dimensional coordintes (vectors))
* Kruskal's non-metric MDS (R: isoMDS)
* Sammon's non-linear mapping (R: sammon)

=====See also=====
* WS Torgerson (1958) ''Theory and Methods of Scaling''
* JB Kruskal, and M Wish (1978) ''Multidimensional Scaling''
* I Borg and P Groenen (2005) ''Modern Multidimensional Scaling: theory and applications''
* TF Cox and MAA Cox (1994) ''Multidimensional Scaling''


====Generalizized MDS (GMDS)====
A generalization of metric MDS where the target domain is non-Euclidean.

See also:
* http://en.wikipedia.org/wiki/Generalized_multidimensional_scaling_(GMDS)


====Sammon’s (non-linear) mapping====
<!--

-->

===Singular value decomposition (SVD)===

<!--
One of the classical types of ordination.

A matrix factoring/orthogonalizing technique, used in statistics and signal processing/analysis. 

Seen used in classical MDS, Principal Coordinate Analysis (abbreviated PCoA, PCoorA, PCO), one way of doing Principal Component analysis (PCA), latent semantic indexing/analysis, and more.{{verify}}


Can be seen to do a few different ways:
* a transformation of correlated variables to uncorrelated variables
* seeing which variables/dimensions explain the most variation in the data, and ordering them for that {{verify}}
* reducing data, using those last two facts

Since a SVD solution calculates its own basis, it means that effects rotated to play in multiple dimensions are likely to be fairly isolated in a single one in the output.



Takes an m-by-n real-valued matrix A, where m &ge; n.

Generally, this input is individual objects by features for each, which can be seen as more everday than most other sorts of matrices - many summarizing tables take that form. Other examples include time and FFT bands, documents and terms in them, or such.




The idea is to separate a matrix A into a soltuion to to ''A=U*S*V<sup>T</sup>'' {{comment|(also W or D instead of S or &#x3A3;, this seems purely naming convention and to have no difference in meaning)}}{{verify}}.

Accordingly, SVD produces a solution in the form of three such matrices:
* U is an m-by-n (column-orthogonal) matrix, the 'left singular vectors' (an orthogonal basis of K<sup>m</sup>)
* S is a n-by-n diagonal matrix, with only positive elements
* V<sup>T</sup>, and the transpose of an n-by-n orthogonal, contain the 'right singular vectors' (an orthogonal basis of K<sup>n</sup>)

The columns U<sub>i</sub> and V<sub>i</sub> are called the left and right singular vectors, the elements S<sub>i,i</sub> (positive reals) are the singular values.

The left vector is mapped onto the right vector with the value: ''A v<sub>i</sub> = S<sub>ii</sub> U<sub>i</sub>''. 
Rougly speaking, U is the base, S stretches/scales it, and V adjusts/aligns it.


Notes:
* The three matrices are necessary to reconstruct the original data, but note that certain uses of SVD, such as Latent Semantic Analysis, are only interested in the orthogonalization and/or reduction, so may omit some part of the calculation (apparently omitting U yielding only S and V).

* The SVD always exists if A is real or complex (and under other conditions that can be handled inside an implementation). 
The solution is singular under certain conditions (which?{{verify}}).

You can use limited data from these three matrices to approximate A with fair and fairly noise-resilient accuracy. That is, A<sup>l</sup> being the sum (for i=1..l) of ''u<sub>i</sub> s<sub>i</sub> v<sup>T</sup><sub>i</sub>'' minimizes the sum of the squares between the elements of that summed matrix and and A - i.e. that result is the closest l-rank matrix to A.


Other things you can do include:
* dimensionality reduction in a principal component analysis style

* If the input was FFT bands, you can take out the S matrix and treat it as a rough characterization of the frequency bands in A, because the The S<sub>i,i</sub> values reflect how important the (in the original case of the FFT) frequency band is in reconstructing the data -- assuming the least-squares metric is a good measure. For intensity data like light and sound you may want to apply a log for some more accuracy.

* When the m{{verify}} dimension is continuous sampling, the plot of V<sup>t</sup> may reveal interesting patterns (related to that continuity)

* The effective rank (using a halfway smart threshold value on the s<sub>i</sub> values) probably roughly reflects the complexity of the music. If taking the SVD in a windowed way, the variance (in an entropy way) should reflect change over time.

* (column-orthogonal means that U*U<sup>t</sup>, U<sup>t</sup>*U, V*V<sup>t</sup>, and V<sup>t</sup>*V all evaluate to identity matrices)
-->


See also:
* http://www.kwon3d.com/theory/jkinem/svd.html
* http://en.wikipedia.org/wiki/Singular_value_decomposition
* http://www.netlib.org/lapack/lug/node53.html
* http://public.lanl.gov/mewall/kluwer2002.html

===Nonlinear dimensionality reduction / Manifold learning===

<!--
An approach to non-linear dimensionality reduction.

Can be thought of an extension of PCA-style techniques that is sensitive to non-linear structure in data.


Applies to cases where the dimensionality is high more artificially due to how it's being measured,


t-SNE/TSNE 
https://en.wikipedia.org/wiki/T-distributed_stochastic_neighbor_embedding
https://scikit-learn.org/stable/modules/generated/sklearn.manifold.TSNE.html


https://scikit-learn.org/stable/modules/manifold.html
-->

===Expectation Maximisation (EM)===
{{stub}}

A broadly applicable idea/method that iteratively uses the Maximum Likelihood (ML) idea and its estimation (MLE).

<!--
TODO: See also [http://www.montefiore.ulg.ac.be/~piater/Cours/INFO0013/Notes/16/toc.xhtml], [http://www.informit.com/articles/article.asp?p=363730&rl=1], [http://www.cs.wisc.edu/~mschultz/cs540/em.html], [http://sifaka.cs.uiuc.edu/course/397cxz03f/em-note.pdf], [http://grb.mnsu.edu/grbts/doc/manual/Expectation_Maximization_EM.html], [http://research.microsoft.com/research/pubs/view.aspx?tr_id=192]

Related: RANSAC.


=====EM for missing-data problems=====
{{stub}}

When you have an imperfect model and an incomplete set of observations, and wish to augment the model based on observations (based on a means of estimation), the methods iterates:
* '''E''': Estimate fictitious data based on current model and observations
* '''M''': Adjust the model to maximize the likelihood of estimating the current data (including estimated data points)

Output can be that model and/or the data estimated with it.

It is comparable to machine learning like Bayesian methods in its prediction-by-observation.

Note: EM easily converges to local maxima; some random initialisation to see whether this varies or not can be called for.


=====EM in clustering=====
{{stub}}

When used for clustering, EM can be seen as a soft version of k-means. 
(See also [[Mixture Models]])


* amount of clusters fixed beforehand
* sensitive to initialisation. See variation [http://www.eece.unm.edu/~chsmith/Papers/SLA-NP-EM.pdf].


===Unsorted===
http://ordination.okstate.edu/eigen.htm

-->

=Decisions, fuzzy coding=
{{stub}}

<!--
Perhaps the most basic machine learning is concerned with approximating data into rules, usually as simple as possible and as automatic as workable. 
The point is usually to handle unseen data as correctly as can be expected, according to the given task. 


More formally, it is interested in:
* Maximizing or improving measurable performance
* At a specific task
* Given some sort of experience


Statistics-based versus model-based.



-->

<!--
...which is to say, those are headers under which it is easy enough to elaborate.
For example, the assumption is generally that experience can be interpolated and/or extrapolated, that the task has to be defined enough to give the sorts of answers you want, that the given experience (and the bits that are considered important) will converge on something interesting, and that that and experience will control what will be actually learned. The way performance is measured will too when it has effect on a next learning run.

This is a rough model of human learning. This doesn't mean that 'performance' and 'knowledge aquisition' as you might attribute them to humans will mean the same thing or be modeled even roughly the same - both are a lot more liquid for humans, and draw on a lot more seemingly casual knowledge.


While no artificial intelligence, machine learning is often more than just a few statistics or probabilities, in that machine learning locates and focuses on structure in data, at least ideally.
This to one of various ends, for example reproducing behaviour, categorizing data, creating an AI-like agent, though time is not usually a part of ML algorithms.




There is, naturally, overlap with and application in data mining, natural language processing, character or other sorts of image recognition, artificial intelligence and other areas that have to deal with changing or inexact environments.



'''Learning versus adaptation'''

You may notice that learners are similar to agents (and their design) in artificial intelligence. This is not unintentional, but may suggest more autonomy than will often be achieved. AI often focuses on learners that are robust to (can maintain performance under) change in the environment, and even to changes the controlled system (and possibly even to the learning process itself). 

Such systems are more complex. One of the issues is that there is a feedback loop which can have issues of its own, for example oscillating feedback loops (note that feedback can both have useful converging effects and annoying ones such as oscillation -- depending on what?{{verify}}). 

Adaptive controllers are necessary given the complexity of systems that interact. For example, the more sensors and actuators, the more prone to error design by parameter estimation is, and the more that adaptive learning can simplify this for the initial, but also unseen tasks.

-->


===On bias===
<!--
Bias: Experience, Defining a Hypothesis Space, and the Target Function


One thing to realize is that many different decisions can bias your results in that it can cut off types of answers, skew away from things not commonly experienced (in a training set), and other things. Sometimes this is the point - and that's one of the reasons this is an issue. Consider that simplification of a document into a class can be the entire use of a system, but often enough there are decisions that will limit your system's expressiveness, which you should realize when you use it.


=====Experience=====
Central questions to ask are what experience actually consists of, how it should be represented, what parts of it are useful features, what should be learned, and even whether the data will conform to the restrictions on the algorithm(s) you'll use - in classification, for example, you need to know whether something only fits intside a single class, and how noise-robust the algorithm is and how noisy the data is.

Models will usually allow you to embed or seed with prior knowledge as well as learn from experience data. Sometimes that distintion isn't even that large.


<small>Lightly sidestepping into AI for a second, you could define a task of playing checkers:
* T: Playing chekers
* P: Games won (this is a fairly general, long-term and loose goal, yes)
* E: Games played against itself

An interesting point to be made here is that training by example games wouldn't necessarily be so interesting option because that would likely focus learning on roughly copying legal moves, which is unlikely to be exhaustive or even tactical in the term of a few or even a single move - depending, of course, on how much prior data and domain theory you introduce.</small>


=====Target function=====
Mathematically, you can see many algorithms-for-problems as a combination of:
* Input data (the unseen data)
* A target function (trained with experience)
* A desired output mapped to by that target function

In slightly more general terms, you canbe said to be looking for a a useful hypothesis (function) among many possible ones. Sometimes the hypothesis space (the possible ones) is finite and even computationally tractable, in which case you can calculate the best one. Often, however, you can't, and you will have to approximate the ideal target function.

The type of value that the target function produces is representative of what sort of algorithm you are dealing with. Discrete values will often be used to classify (and boolean often to classify into relevant or not, in eg. concept learning), whereas real values usually point to correlation and regression tasks.

You definition of the target function introduces '''Preference bias''' in that specifically your output will have limited range, and therefore be limited to specific values. More exactly, you will (have to) internally choose a specific representation for data. 

Think of ways you would choose a target function for playing a move in chess. There are various ways to define this target function and what you would actually value when choosing a best. Consider for example that you can map a board position to a best move, or to that of the possible board positions that we like best. They sound the same, but will probably lead to different focus, and different direct evaluation.
In fact, direct evaluation this in an integral part of he function: What do you actually prefer? Would you just value having more pieces? That and threatened pieces? That and the amount you threaten? All of that for all the types of your pieces? Doing just that will focus your tactics entirely on those aspects and nothing else -- basically because that will be the universe in terms of evaluation.

To come back to learning: choosing a nonoptimal representation isn't actually fatal. For example, in the chess playing setup just suggested, what you would probably actually decide to learn is how important each of those aspects are. In the long term your algorithm would probably learn that pawns can be quite useful, queens perhaps not so much as the prior knowledge you may put in there may suggest, and it may even discover that evaluation aspects you introduced are almost entirely irrelevant.

====Experience====
To learn with experience without supervision, things like iterative methods are used, which are seen to have at least the elements of experience and that of measuring performance.

That's a couple of new terms. The amount of supervision (supervised, unsupervised, semi-supervised) refers to how much human interaction is needed to make the system work at all, though of course interactive supervision will often lead to tweaking as well.

Iterative learning, or in more AI-like terms, reinforcement learning, is simply a step towards the unsupervised. It learns particularly what interactions are effective. Note that most basic ML isn't directly that advanced.





===Fuzzy logic===
Fuzzy logic is itself fuzzily defined.

It is mostly a formalization of working with degrees of applicability, or rather, degree of membership to a group, according to fuzzy set theory[http://en.wikipedia.org/wiki/Fuzzy_set]. 

Superficially, partial membership is the same as probability, but there are differences you can care about.


Fuzzy logic is often contrasted with boolean logic, which in itself can be a misleading way to introduce it.

Fuzzy logic based decisions / control can often just as easily be described a conditional logic based with a few degrees (seemingly particularly so for the more basic, linear fuzzy set membership functions) and thresholds that are in themselves nothing special particularly in programming, which is where most fuzzy logic is applied, though they can be used to keep such a system simple, or keep it more numeric, abstract and/or apart from main code.



http://en.wikipedia.org/wiki/Fuzzy_logic
http://en.wikipedia.org/wiki/Fuzzy_set
-->




===Methods / algorithms / searchers===
<!--
There are a lot of algorithms, which can usually be said to model in specific ways. Usually these model specific types of structures well and others not so well.


-->

===Decision trees===
<!--
Decision trees are used to classify: to decide.


They are, in some ways, no more than a codification of already-known rules. 
In themselves they are memorization, not learning.

You can create such decision trees, but this requires fairly clean data.




Decision trees are essentially acyclic graphs where each edge/transition is the answer to the node it originates in.
For example, the root note could ask "Weather", from which "Overcast" leads to "Sad", and "Sunny" leads to "Happy."

Of course, such decision nodes can follow each other, which also puts them in the context of the information given by the decisions of the previous nodes. As such, a set of given attributes is a walk in the tree. 

To be exact:
* Node: attribute
* Branch (edge): attribute value (discrete)
* leaf: classification


Such a tree can contain all training data in a dense tree, but that isn't very useful. Interestingly, on no-noise data it can do so fairly compactly. The value of this is the structure and the possible transformations on it. Pruning  branches and making a decision is analogous to making a generalisation: for example, when all leafs after 'Sunny' lead to 'Happy', you can replace that subtree with a single leaf 'Happy' and have exactly the same data encoded.

Similarly, when you notice that ''most'' of them do, you can '''prune''' the tree and do the same simplification at the cost of only a little accuracy on unseen data - or such is the assumption when you assume training data is representative.


It is also interesting to make the most important/clearest decisions first. Among other things, it ensures pruning lower nodes will have minimal effect.

The usefulness of a decision can be measured by information gain, basically a measure of usefulness to the decision tree based on the amount of entropy an attribute causes.

-->
=====ID3=====
<!--
In fact, the ID3 algorithm does just what is described above. It constructs a decision tree from scratch by locally using the node that adds the most value / information gain to the decision tree.

More exactly, it measures the entropy of each attribute value and weighs it by the fraction of cases it represents {{verify}}. The gain of information is the current node's entropy minus all such values. It comes down to that more distinctive decisions will be chosen first, less ones later, meaning that the important decisions come first.

It also means this effect is purely local optimality and ignores depthwise considerations, meaning it is not guaranteed to be optimal, only a fair guess. 


ID3 searches (and encodes) the entire hypothesis space. It is also statistically based, so can handle training data that is a little noisy: The information gain will be lower, but not necessarily disturn the process or choice.


Now note that instead of restruction bias (limiting the range of outcomes or attributes) we have preference bias: we decided we prefer 'useful' decisions based on some measure. 

However, it is convenient. It is in the spirit of Occam's razor in that it tries to explain everything it sees with the shortest hypothesis. If such a short one exists, it is more likely to be structure in the data than coincidence.


=====Overfitting=====
In the context of a decision tree, overfitting means that adding too many levels of deep tree detail will be too specific for the training data and be invalid for unseen data and probably the entire general universe of possible data (not that that one's measurable).

-->
=====Pruning (ID3, others)=====
<!--
Given a decision tree that contains all hypotheses is quite likely to be overfitting, so you probably want to generalize by pruning. 

You could in theory do this during, e.g. figure that if your best dicision isn't statistically very strong you do not want to add a brancj.

More generally, you could post-prune trees. When you have less informative information about the construction of the tree, you can prune do so by a sort of trial and error based on a training set of data, for example by seeing which tree minimizes (treesize + misclassifications).

Pruning will often mean an accuracy increase because it will work for more general cases, but only a little because it will exclude other cases in the process.


=====Tree effects/extensions=====
You can limitedly use continuous values by using a threshold to map them into a boolean or a set of discrete values.

Attributes with many values will tend to be chosen for infogain when it isn't really.

There are alternatives to simple infogain

You can deal with missing values in various ways.

-->

=====Rule Post-pruning; C4.5=====
<!--
{{stub}}

One thing you can do with a tree is turn it into equivalent rules - each path, after all, is a conjunction of conditions, so can be made into an if-then structure. You can then prune arguments in each rule's expression, based one something such as information gain, and sort the rules for application.

Apparently this is the C4.5 method. I'll have to look up the details.

http://en.wikipedia.org/wiki/C4.5_algorithm

https://octaviansima.wordpress.com/2011/03/25/decision-trees-c4-5/

-->

===Instance-based learning===
<!--
"Just Store all data in memory" and find likely answer by analogy: 
* Define distance measure between two 
* Use distance measure for unseen-any training data member.
* Calcualte answer from most likely entry's target value

The nearest neighbour(s) based on euclidian distance in n-dimensional space -- when instances canbe mapped to such a space, and only when sensibly (as dimensions also interact).

Lazy method (decision on the spot), vs. eager (generalize/learn before using).

====k-Nearest Neighbor (k-NN)====
Use the k nearest neighbours, or just one.

Weighed variant: Weigh closer neighbours more, or possibly even all.

-->


===Semi-sorted===
====Markov Models, Hidden Markov Models====
{{stub}}

Something like (the simplest possible) [[Bayesian Belief Networks]], but geared to streams of data.
Can be seen as a state machine noting the likeliness of each next step based on a number of preceding steps. 

The hidden variant only shows its output (and hides the model that produces it), the non-hidden one shows all of its state.

Simple ones are first-order 

<!--
Expectation-maximization (EM) is regularly used.
(EM: Iterative process based on maximum likelihood of untrustable (hidden) values)
-->

=Classification=


===Naive Bayes===
====Some background====
A certain Reverend [http://en.wikipedia.org/wiki/Thomas_Bayes Thomas Bayes] said a number of things about probability,
used mostly in [[Bayesian inference]] in statistics, and in Naive Bayes classification.


'''[[Classification]]''', in general, is usually based on a trained model {{comment|(or sometimes hardcoded assumptions)}}:
* deciding on a set of distinct target classes (say, exclusives as 'spam' vs. 'not spam', or rough article subjects {{comment|(preferably exclusive, or classification itself does not make that much sense, although the value-for-class assignments still may)}} 
* deciding some features to look at, that classification will be based on
* learning the importance of features to each class (often using good examples for each class)

Given something unseen to classify, you extract its features the same way you did for the training set, and see which class compares best. Classification is regularly many fuzzy measures of fit followed by a hard choice of which seems best.



'''Naive Bayes''' refers to one of the simpler algorithms that does classification this way. 

Its definition has a few notational conventions:
* Each training class is referred to as '''<tt>c</tt>''' in the set of classes '''<tt>C</tt>''' {{comment|(<tt>c<sub>1</sub></tt>...<tt>c<sub>i</sub></tt>)}}
* We eventually want to judge an unseen document '''<tt>D</tt>'''
* and what we want for '''<tt>D</tt>''' is is the class for which the probability the document fits that class is highest


You can express such Bayesian classification as:
 the c for which <tt>P(c|D)</tt> is highest 

or, a bit more formally yet,
 c = maxarg( P(c<sub>i</sub>|D) )

====Bayes's rule====

The <tt>P(c|D)</tt> above is not obvious to calculate, because it immediately asks us for a best choice for a document, and a thorough answer of that will probably depend on multiple pieces of information: document's features, all classes, and all documents.


So we need to break the problem down before we can give an estimation of the probability <tt>P(c|D)</tt>,
and the first step is to apply '''Bayes's rule''' {{comment|(which pops up in various other types of probability calculations and estimations)}}.
              P(D|c) * P(c)
 P(c|D)  =  -----------------
                  P(D)
...for each class <tt>c</tt> in <tt>C</tt>.


Looking at the parts:      

'''P(c)'''  is the base probability of each class, that is, the probability that a document is in class ''c'' given ''no'' other information. 
: This is sometimes assumed to be equal for all classes {{comment|(in which case it falls away)}},
: sometimes it is estimated, for example using the assumption that the ''amount'' of training examples in each class is a direct indication of how commonly an item falls into that class.

'''P(D)''' is the chance of finding the document, in general. 
: This is usually assumed to be independent of the classification problem. 
: because of that, and because it is hard to realistically estimate for an unseen document, it is often assumed to be equal for all documents (so falls away).

...so '''P(D|c)''' is the interesting one. It asks for the probability that a particular document in a particular class.
: This is still abstract, and not yet a directly calculable answer, but it is a smaller problem than we had a few paragraphs earlier: Unlike the earlier form {{comment|('''P(c&#x7c;D)''')}} which deals with an immediate choice between alternatives, we now deal mainly/only with an calculation/estimation of fit, of '' 'how well does a specific '''D'''ocument fit in every specific '''c'''lass?' ''.

: This degree of fit for a document in a class can be done with any method that judges similarity, as long as '''it is (fairly) stable/consistent''' between documents, and it '''can be calculated (roughly) equally well for seen and unseen documents'''.



Long story somewhat shorter, applying Bayes' rule reduces the classification problem from
: "Choose best class immediately"
to
: "find the class for which our estimation of fit is highest" {{comment|(by making an estimator that can judge individual documents, and can do so stably / comparably well for all documents)}}


Put another way, from:
 maxarg( P(c<sub>i</sub>|D) )
to:
 maxarg( P(c<sub>i</sub>) * P(D|c<sub>i</sub>) )
or, assuming equal base-class probabilities, to:
 maxarg( P(D|c<sub>i</sub>) )

====Features, Words, and Naivety====
So let's talk about an implementation.

If we want to calculate a class's fit based on features, we need
to choose those features, and a method to calculate an arbitrary document's fit to those features.

It's nice if each feature is 
''fairly robust'' in that it does not react in an unnecessarily noisy way,
and ''productive'' for the classification task at hand. 



In Naive Bayes introductions, the choice of features is often words {{comment|(some introductions talk mainly of words, some talk more broadly about features)}}, and the probabilities are based on the relative occurrence of each chosen word. 

Words are a specific implementation choice, but are a nice introduction, in part because it speaks to the imagination in cases such as spam {{comment|(even though it's limited for this, given that spammers know and try to defeat this model)}}.


If you're programming such a toy example, then the amount of words is often reduced to maybe a thousand.
The actual selection is interesting, in that they ought to be distinguishing within the training set ("the" may be common but not useful), but not be so unusual that they are rare within unseen documents.

There are cleverer ways of choosing words, and you probably want to consider the [http://en.wikipedia.org/wiki/Zipf_distribution Zipf distribution] of words, but to keep the example simple, let's say we take the most common 1000 in the training set, minus some obvious stopwords.

<!--
In fact, spam filters may be bayesian but will have more specific features, such as 'apparently sent to self', 'sent to dozens of people', 'uses many non-dictionary words', some estimation of 'uses misspellings likely to be read over but avoid exact matchers', presence of common spam-phrases (e.g. based on regexp matches), trust or distrust of certain mail networks, etc.
-->


Naive Bayes is often explained by saying we want a probability based on <tt>n</tt> features in feature set F: <tt>P(c|f<sub>1</sub>..f<sub>n</sub>)</tt>, which Bayes-inverses and denominator-eliminates to:
 P(c) * P(f<sub>1</sub>..f<sub>n</sub>|c)
...which roughly means "how do features in this new document compare to the one for the class?"


Technically, <tt>P(f<sub>1</sub>..f<sub>n</sub>|c)</tt> should expand to a very long formula, as each feature depends on others. That's where the naivety of Naive Bayes comes in: the '''Naive Bayes assumption''' is simply that all features are independent of all others. This is rarely true, but is much simpler to work with, is evaluated much faster, and works better than you might expect. (this also effectively makes it a [[bag-of-words]] model)

It means calculation of the probability of the class based of the features simplifies to a simple multiplication of individual feature values / probabilities. Given there are n features:
 P(c) * <span style="font-size:210%">&#928;</span><sub>i=1 to n</sub> P(f<sub>i</sub>|c)


Note that the words-as-features setup is a [[#Bag_of_words.2Ffeatures_.28assumption.29]] assumption: it plus the naivety means that word order is ignored.  This means that potentially indicative phrases, collocations, and such are represented only weakly at best, by their words' independent probabilities being slightly higher.  Word n-grams are one possible fix, but will likely run you into a sparseness problem since n-grams are implicitly rarer than single words. 
Even just bi-grams may be problematic - if you take all possible ones from a large set of documents, you'll find that most documents have a tiny fraction of the overall real use.

====Bayesian classification as a procedure...====
Naive Bayes training comes down to:
* Deciding which set of features (F) you will use. 
* '''Train''', which calculates characteristics for each class, namely:
** P(c) for each class (see above), and more importantly,
** all P(f|c): the probability of each feature f in each class c


Later, when classifying an unseen document, you calculate <tt>P(c) * P(f<sub>1</sub>..f<sub>n</sub>|c)</tt> for it:
* for each c in C:
** take P(c), times 
** the calculated probability of each feature in class c, i.e. each P(f|c) based on the document.
* Choose the one with the highest probability, and you've got a classifier.


====Choosing your features, and further discussion====
Naive Bayes with simple word features works fairly well on various types of text, since it essentially notices differences in vocabulary use, the theory being that that is indicative of the document class. Common words can be useful when they aren't uniformly common between all classes, uncommon ones since they tend to up the probability of just a few classes. 


You could simply use all words in all documents and end up with tens of thousands of features, although it would help speed to prune that a little. Which ones to leave is a choice you can be halfway smart about - although note that too much tweaking just means it will work better on the training data, with no guarantees for ''unseen'' data.

Also note that when you pre-process the training data, you need to process the unseen documents the same way. When choosing the features, you should consider what this may do to unseen documents.


A feature probability of zero is evil to calculations as it randomly destroys comparability in the both training and classification steps. It can happen fairly easily, such as when a word in the vocabulary doesn't occur in a document. A common solution is to cheat and pretend you did actually see it a little. There are a few different ways; some disturb the relative probabilities less than others.



You can add other features. The main property they should have is that their probabilities compare well, are in the same sort of scale. You could for example add important words a few times, a hackish way of weighing them more. You could for example add select word bigrams or add character n-grams. 

You can alter the model further, observing that what you actually do is per-class strengthening or weakening of a probability that it will win. 
It doesn't even have to be a simple probability, even; you could for example include sentence length, which is not a direct probability, so you would have to e.g. remember the average sentence length in each class, calculate the average for the unseen document and define some metric of similarity. This isn't Naive Bayes anymore, but as a probability-based classifier it may work a little better if you choose your alterations well.


====Pseudocode====
This example pseudocode uses only word features, and some basic add-one{{verify}} smoothing to avoid the zero problem.

'''Training''' (word features)
 U = feature universe
 D = document set (text,class pairs)
 C = set of classes in D
 foreach c in C:
   BaseProb(c) = |D with class c| / |D|
   Text = concatenation of documents in current class
   N    = |tokens in Text|
   foreach token t in U:
     <tt>P(t|c) = ( '''numoccurence'''(t in Text) + 1 ) / ('''numtokens'''(Text)+|U| )</tt>


'''Classifying''' (word features)
 foreach c in C:
   p=P(c)
   foreach token in Document
     p = p*P(token|c)
...then collect each of these probabilities and choose the class with the highest probability. 


In reality, the probabilities quickly become very small and you run into the problem that standard 32-bit or 64-bit floating point numbers cannot accurately contain them. 
A common workaround for this is to add the logs of the probabilities (yielding negative numbers) instead of multiplying the probabilities.  These values are much less likely to scale out of control, and they are as just as monotonous as the probabilities.



===Semi-sorted===
* [[#Bayesian classifier]]

* Parzen classifier

* Backpropagation classifier

<!--

Applications of more general techniques:
* PCA
* SVM
* Any clustering in a feature space, e.g. kNN
-->


====Evaluating classifiers====
<!--
Precision/recall, accuracy, variant/hybrid methods (, valuing precision over recall.)


Classification can be tested. Usually, there is a set of annotated data. When it is large enough, it can be split into a training set and an evaluation set. The idea is that you cannot evaluate based on the training set iself, as that should give (nearly) perfect results, and would not at all be a test of how it would work on unseen data.

When you have enough data, you could split into training, evaluation and a completely separate evaluation set that you use for nothing else and see as your unseen data. Usually this will contain some bias, that of the fact it comes from the same data collection, but it is a pretty good test of how a system tweaked to training data works with data it hasn't seen before, and should reveal if it is unflexible.

When data is scarce, you can do an n-fold crossvalidation. This means you split your data into n (nearly-)equal-sized buckets, and use n-1 for training and the last one for testing, in all possible combinations, and averaging the accuracy. It is essentially pretending that you have more training data. On the upside, it will use all your data for testing and thus make it less likely that your test won't accidentally be skewed by a few odd cases.



-->

====Combining classifiers====
<!--
Combining classifiers can be useful when you think some may have imperfections that sometimes leads to strange answers for certain data. 

Averaging can sometimes make sense. There is also focus on:
* Voting: let each model predict, and look for consensus: use the most common answer.

* Bagging: Voting, but use same learner on different training data, to the end of hoping to lessen [[overfitting]].

* Boosting: Focus on misclassified data by weighing it more the next iteration


Also: 
* Use classification to self-teach or 
* co-teach by generating corpora yourself. May easily delude itself.
* Add a human for difficult cases only (like co-training)
-->

====Ensemble learning====
<!--


https://en.wikipedia.org/wiki/Ensemble_learning
-->

====Support Vector Machines====

<!--
Supervised, trained from samples in one of two categories.
(Sometimes trained from unlabeled data via clustering)


By themselves, they do binary, linear classification.

SVM is generally introduced as linear SVM, the moving on to uses of the kernel method.
(basically something that maps a complex thing into something more linearly separable for SVM to deal with).



One of the ideas behind SVM is that you can try to minimize overfitting by trying to pick a set of most useful points out of the training data. You can see it as ignoring outliers, or generalizing as part of the learning process.


The idea is that each datapoint is one of:
* Important (a.k.a. a 'Support Vector')
* Wrong    
* Ignorable (correct, but not strong)

The best results usually come from widening the margin, maximizing the distance from the SV's to the hyperplane.

This makes it a constraint problem, which is you can always deal well with using the Lagrangian equation. So they say:)


Given n attributes to use, SVM takes place in n-dimensional space, constructing a hyperplane to categorize the data into two groups, or because of the margin, more accurately a hypertube. (...closest human-likable concept given the margin is also n-dimensional)





-->

=====Support-vector regression=====

====Using the kernel method====
<!--
See also [[Kernel method]]

-->

=Clustering=

===Intro===

Clustering groups a few related sub-problems, including
: '''cluster formation''' - organizing into clusters
: '''cluster segmentation''' - dealing with boundaries (often using cluster centers)
: '''labeling''' - assigning meaningful names
:: for the (relatively few) cases where this makes sense to estimate
: '''deciding how many groups''' to have in the result
: '''evaluation''' of a solution (possibly feeding back into the previous point)


<!--

Clustering methods vary in in intermediate definitions, e.g. 
* method of calculating the similarity/distance (the metric)
* intermediate definitions, such as agglomerate distances in hierarchical clustering
* thresholding or other means of inclusion/exclusion decision per cluster, possibly a target amount of clusters.


It is generally not hard to find a reasonable solution for nice data, as each strong-enough cluster in the data attracts a cluster center into it / makes for clear division / makes for clear local density.


For some algorithms there are visual interpretations.
For example, assuming 2D data, simpler nearest-cluster-by-distance methods resemble [[Voronoi]]-like division.



-->

'''Formally''', the simplest clustering ca be described as:
* you have a set of n data objects, call it  D = { d<sub>1</sub>, ..., d<sub>n</sub> }
* in its simplest shape, a clustering result is a disjoint partitioning of D
* which makes clustering itself a function, mapping each datapoint to a cluster number/label that indicate membership of said cluster



The input data is often either 
* a set of a points in a many-dimensional space, usually a [[vector space]], plus a metric to calculate distance between them, OR

* a set of already-chosen distances
:: preferably complete, but depending on how it's made it might be sparse, and it may be easier to do some fuzzy statistical estimation than to ask people to complete it


The latter may well be in the form of a [[distance matrix]] / [[similarity matrix]].

A bunch of methods given datapoints-plus-metric convert to that internally, but starting data-plus-metric is often a little more flexible up front - both for data massaging, and sometimes for implementation reasons.


That said, the choice of metric takes care, 
because there are many ways to accidentally put some bias into the metric.


Many methods look at element-to-element similarities/dissimilarities, while a few choose to be more involved with the data that comes from {{comment|(e.g. some Maximum-likelihood-based methods common in bioinformatics)}}



====Variations====
=====Hard, soft, and fuzzy clustering=====
'''Hard clustering''' means each item should be assigned to a single group. 
This is essentially a partitioning.


'''Soft clustering''' means something can belong to more than one group.

Regularly used for data known to be too complex to be reduced cleanly with hard clustering, such as when there are closeby, overlapping, or ambiguous groups. 

Soft clustering is generally understood as boolean soft clustering: something can belong to one or more clusters, but there are no degrees.


'''Fuzzy clustering''' is soft clustering plus degrees of membership.

This means intermediate results are effectively still moderately high-dimensional data,
you often still have to make a decision about exclusion,
thresholds or such (preferably within the algorithm, to have all information available).

If you don't make such a decision, the result more resembles dimensionality reduction.
<!--
This starts to resemble other things, such as probability-based classifiers, and some other methods mentioned here.
-->

=====Agglomerative versus divisive=====

'''Agglomerative''' clustering usually starts with each item in its own cluster and merges them where it seems a good idea.


'''Divisive''' clustering usually starts with every item in a single cluster and iteratively splits them as it sees fit, stopping either when some goal is satisfied, or sometimes until everything is split.


Differences include:

* what side they err on in unclear cases.{{verify}}

* divisive by nature makes its decision on more data, so ''can'' be more accurate
: e.g. early combination decisions in agglomerative may be less sensible but cannot be undone without making the method more complex

* divisive is often more efficient to calculate

* divisive is a little more supervised, in that you may need to explecitly give it a way to split that makes sense of the data


In general, divisive clusters seems better at finding large clusters, 
agglomerative clustering is good at finding small clusters.{{verify}}

=====Hierarchical clustering=====
'''Hierarchical clustering''' creates a tree of relations, often by an process where we keep tracks of how things join, rather than just assimilate things into a larger blob.


Hierarchical clusterers can be flexible, in that their results can partition into an arbitrary number of groups (by choosing the depth at which there are that amount of groups).

Depending on the data these results contain may also be useful as an approximation for fuzzy clustering. 
They may also be a little more helpful in cluster stability tests.


Some algorithms record and retain he distances of (/stress at) each such joint.
These can be interesting to visualize (think dendrograms and such),
and to effectively allow the amount-of-cluster choice to be made later (think threshold in a dendrogram).


http://gepas.bioinfo.cipf.es/cgi-bin/docs/clusterhelp

<!--
=====Graph clustering=====

If you have a graph (in the mathematical network sense) you could cluster it
 
Markov Cluster Algorithm
[http://www.micans.org/mcl/]
-->

====Notes on....====
=====Group number choice=====
Some algorithms try to decide on a suitable number of target groups,
but many require you to choose an exact number before they get started.

This number is difficult to decide since there is usually is no well-defined, implicit, calculable best choice.


This is a problem particularly in hard clustering, because any decision of group membership is very final.
The membership of bordercases may not be stable under even the slightest amount of (sample) noise.


Things you can do include:
* use evaluation to measure the fitness of a solution (or sub-solutions while still clustering), based 

Note that such a metric in itself is only a relative value in a distribution you don't know - you'll often have to calculate the fitness for many solutions to get a still-vague idea of fitness.
<!--
You could even create a dendrogram from a (separate) hierarchical clustering and decide based on that, which is computationally more expensive than a single run, but often cheaper than running the clustering for all possible number of groups.
-->

* In the case of hard clustering, you can intentionally add some noise and see how much the membership of each item varies - and, say, report that as the confidence we have in a choice.

* use some type of cross-validation


<!--
* Clusters into a fixed number of groups that is either manually set, or sometimes based on the data. 
* input: n coordinates in many-dimensional space, and where applicable a target number of groups
* potential problems: sensitive to outliers, sensitive to unrepresentative choices of k (whether given or automatic)
* complexity: Generally, each iteration is O(n*k). For most data sets there will be less than n iterations, though there are pathological cases
-->

=====Inter-cluster and intra-cluster comparisons; susceptibilities=====

<!--
Each element can be and often is represented by multidimensional data. The distance measures simplify this to a (usually symmetric) difference matrix to work on - though various methods needs to also define the distance between clusters.
-->


Depending on the algorithm, you often want to be able to compare 
* items to clusters (agglomerative and divisive decisions)
* clusters to clusters (e.g. in hierarchical decisions)
* items to items (e.g. for centroid/medoid decisions)


'''Cluster-to-cluster distances''' are most interesting to hierarchical clustering, and can be calculated in a number of ways (usually hardwired into the algorithm), including:

* '''Single-link''', a.k.a. '''minimum linkage''' or '''nearest linkage'''
: the most similar combination (lowest distance) of possible comparisons
: more susceptible to over-chaining than most other methods

* '''Complete-link''' , a.k.a. '''max/farthest linkage'''
: uses the least similar (largest distance) combination of possible comparisons
: often gives a non-chained, more equally divided clusters than single-link
: outliers may have disproportional influence

* '''Average-link''' {{comment|(a.k.a. group-average, a.k.a. Group-average (agglomerative) clustering (GAAC))}} - average of distances between ''all'' inter-cluster pairs
: less sensitive to outliers than complete-link, less sensitive to inversion than centroid approaches.

* '''Centroid''' approaches use a calculated average for comparison to a cluster
: quite susceptible to inversions {{verify}}

* '''Medoid''' approaches try to use a representative item for comparison to a cluster
: somewhat susceptible to inversions {{verify}}

* Density-based methods care more about local density of items and less directly about the exact distances involved

* Ward's method
: based on Ward criterion, a.k.a. the [http://en.wikipedia.org/wiki/Ward's_method#The_minimum_variance_criterion Ward minimum variance criterion]





Potential problems:
* '''outliers'''
** including a single outlier may drastically change comparisons to that group. 
** The timing of their inclustion can have significant effects on the result.

* the '''chaining effect''' refers to algorithms doing a chain/string of assignments of to a group. The concept is clearest in <!-- hierarchical cases that make for a very deep tree with one leaf at each depth. In flattened form {{comment|(and some non-hierarchical cases)}} it means one very large group and a few tiny ones, rather than a more balanced clustering. Sometimes contrasted with a symmetry effect{{verify}}-->

* '''Inversions''' {{comment|(sometimes 'reversal' or 'non-monotonicity')}} - describes when similarity values do not decrease monotonously in a series of iterations
** easily happens when a process makes decisions based on centers that move in the process of clustering (such as in many centroid-style processes) particularly when combined with cases where there is no clear clustering solution.<!--
** They lead to items which show a larger distance in the result
** They are not necessarily a problem - small inversions can indicate areas where there is no clear clustering solution. However, there are also situations where 

* '''Non-uniqueness'''
** In agglomerative hierarchical clustering regularly wants to join two clusters, and may find that where distances between different clusters are equal, so equally valid at that level. An algorithm will often choose an arbitrary one. Those different solutions may be different at more detailed levels.

-->

<!--
Non-uniqueness and inversions are sometimes underestimated.
-->


See also:
* http://en.wikipedia.org/wiki/Hierarchical_clustering

TODO: read
* http://people.revoledu.com/kardi/tutorial/Similarity/index.html
* http://www.google.com/search?hl=en&q=Mahalanobis+distance

=====on convergence=====
{{stub}}

Convergence is a nontrivial check in many algorithms.

You ''could'' check whether the group assignments have not changed, but this is sensitive to oscillations, resulting in a premature report of convergence and/or a failure to converge (depending somewhat on logic and data size).

A simple threshold is arbitrary since the error values often depend on the scale of the data values (which is not very trivial to correct for{{verify}}).


This is occasionally solved by error minimization criteria, for example minimization-of-the-sum-of-squares.

There are some details to this. For example, reallocating a point between clusters, various methods consider only the error decrease in the target cluster - while the solution's ''total'' error may increase. 
It usually still converges, but the total error decreases with a little more oscillation, which "no significant improvement in the last step" terminating criterion may be sensitive to (though arguably it's always more robust to check whether the error decrease is roughly asymptotic with the minimum you presume it'll get to).

The idea resembles [[Expectation Maximization]] (EM) methods in that it tries to maximize the probability of the clusters being the correct by minimizing the energy/error.



Purely random initial positioning may cause the local minimum problem.
Smartly seeding the initial centroids helps and need not be too computationally expensive - and in fact helps convergence; see e.g. k-means++. 

Alternatively, you could run many versions of the analysis, each with random initial placement, and see see whether (and/or to which degree) the results are stable, but this can be computationally expensive.

=====Robustness in hard clustering=====
Particularly hard clusterers are often not robust against even minor variations in the data. That is, separate data sets that are highly correlative may lead to significantly different results; areas in which membership is borderline flip-flip under the tiniest (sample) noise.


You can evaluating a solution for stress (or correlate distances it implies to the original data e.g. in hierarhical data), though in itself this is only a general thing. It is meaningful the same measre from other clusterings of the same data, meaning that you *can* roughly compare different solutions for expression of the original data, but only in a roughly converging way.


One trick is to cause the problem and test how varied results will be over mild variations over the data. You can for example repeat the clustering some amount of times with some noise, and record how often things change membership. 

You can repeat the clustering omitting random pieces of data to lessen the effect of outliers - pieces of data that do not agree with the rest. 

You can even aggregate the results from these runs and combine them into a sort of fuzzy cluster result that can show you instabilities, and/or converge on a clusters amount choice.

=====Evaluation=====

<!--
Evaluating the accuracy of clustering (and dimensionality reduction) is by nature an imperfect thing. 
You always reduce information - the question is how useful that is to you, which is subjective.


In the case of hierarchical clustering, the cophenetic correlation coefficient (CPCC or CCC) is common, and makes the cluster-based metric taxa-based.

You could test how stable a result is: add noise to your data, see how often and how much the clusterings disagree.

There are also some metrics of clusterings. For example, the silhouette value can measure of how similar an object is to its own cluster (cohesion) compared to other clusters (separation).

For dimensionality reduction, the most basic method is probably to have some metric, and and see how well these distances correlate before and after.

Note that it matters whether a clustering is complete or not. The ability to ignore points as outliers


In evalauation, there are various concept that com eup:
* '''cohesion''' of/within a cluster
* '''separation''' between clusters is relevant.

* '''entropy'''
* '''purity'''

-->

======Silhouette coefficients======
<!--
Uses cohesion and separation, and can be evaluation for points, clusters, and the whole clustering.


https://cs.fit.edu/~pkc/classes/ml-internet/silhouette.pdf
http://scikit-learn.org/stable/modules/generated/sklearn.metrics.silhouette_score.html

-->

======Davies-Bouldin index======

======Gap statistic======
<!--

https://web.stanford.edu/~hastie/Papers/gap.pdf

https://en.wikipedia.org/wiki/Silhouette_%28clustering%29

http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html


http://stats.stackexchange.com/questions/10540/how-to-interpret-mean-of-silhouette-plot
-->


====Related====
=====Clustering as neighbour search=====

<!--

Clustering, usually used to find a simpler classification based on more complex data, 
will also represent a nearness of items.

As such, certain algorithms can be adapted to do both classification ''and'' 
be create an index supporting things like recommendation, feature matching, and information retrieval.

The latter because it is one way of both reducing the amount of items to compare to (which may run in the millions), and to simplify the complexity of comparison (which may be high dimensional vectors).


Similar to optimized search trees, like kd-trees, however those are not always efficient as we hoped.


There are also some thing you can be faster by only needing to guarantee ''approximate''[https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximation_methods] rather than precise nearest neighbour.



For example, k-nearest neighbors (kNN) is classifier first. 
It's a fairly basic way to classify new data: given existing classified data, take the n closest datapoints at have them vote based on their class membership.

(The best k is not always obvious. A small k is more sensitive around outliers, high k means that larger/denser clusters may outvote small ones.)



S Arya (1993), "{{search|An optimal algorithm for approximate nearest neighbor searching}}"

J Bentley (1975), "{{search|Multidimensional binary search trees used for associative search}}"


H Jegou (2013) "{{search|Product quantization for nearest neighbor search}}"



https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

https://arxiv.org/pdf/1807.02962.pdf

https://opendistro.github.io/for-elasticsearch-docs/docs/knn/

https://scikit-learn.org/stable/modules/neighbors.html
-->


=====Hamming embedding=====

<!--
https://www.quora.com/What-is-hamming-embedding-How-does-it-improve-the-BoF-model


H Jegou et al. (2008) "{{search|Hamming embedding and weak geometric consistency for large scale image search}}"

M Jain et al. (2012) "{{search|Hamming Embedding Similarity-based Image Classification}}"

-->

=====Unsorted=====

<!--
SSE ?


http://www.cs.kent.edu/~jin/DM08/ClusterValidation.pdf


https://cgi.csc.liv.ac.uk/~katie/adma10.pdf

-->

===Implementation notes===

=====k-means=====
The '''k-means''' problem is finding a cluster labelling for a given amount of clusters (k) with minimal error,
where the error function is based on the the within-group sum of squares.

{{comment|(For completeness, that means for all elements in a group, calculate the square of the euclidean distance to the centroid, and sum up all these squares, which gives per-cluster error values. Various convergence checks will want to know the sum of these errors)}}


Most implementations are iterative and look something like:
* Position ''k'' cluster centroids (at random, or sometimes slightly more cleverly)

* For each element, assign to the nearest centroid
* Recalculate (affected) centroid means (and often the error/energy at the same time)

* Check whether the moved centroids change the element assignments.
: If so, iterate
: If no change, we have converged and can stop


Of iterative clustering methods, k-means is the simplest and many others can be said to be based on it.


K-means gives better better results if the value for k is a good choice, representative for the data.
(it's not unusual to try various k and test them)

The common 'nearest cluster' criterion will avoid attraction of multiple clusters, and the whole will converge to a decent solution for k groups. 


Limitations: 
* results are sensitive to initial placement, and it is easy to get stuck in a local minimum.
: It is not unusual to run the clustering various times with different starting clusters and see how stable the clustering is.

* If k is not representative of the structure in the data the solution may not be satisfying at all. This is partly caused by, and partly independent of, the fact that there may be various possible stable clusterings.

* the simple distance metric means we say the shape for inclusion is always a circle


Average-case runtime is decent because it's a fairly simple algorithm.
Worst-case runtime, for fairly pathological datasets, is fairly quite high. There are faster approximations of k-means that you may wish to consider.

You can tweak k-means in various ways.
For example, you can assign weights (based of frequency, importance, etc) to elements to affect the centroid mean recalculation.


See also:
* [http://en.wikipedia.org/wiki/K-means_algorithm Wikipedia: K-means algorithm] 
* Arthur & Vassilvitskii, [http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf ''k-means++ The Advantages of Careful Seeding'']
* JA Lloyd (1957),  ''Least Squares Quantization in PCM''
* EW Forgy (1965), ''Cluster analysis of multivariate data: efficiency vs interpretability of classifications''
* MacQueen (1967), ''Some methods for classification and analysis of multivariate observations.''
* Hartigan and Wong (1979), ''A K-means clustering algorithm''
* Kanungo, Mount, Netanyahu, Piatko, Silverman, and Wu, [http://www.kanungo.us/pubs/tpami02-kmeans.pdf ''An efficient k-means clustering algorithm: Analysis and implementation'']
* Bottou, Bengio, [http://citeseer.ist.psu.edu/bottou95convergence.html ''Convergence Properties of the K-Means Algorithms'']



Variations:
* '''ISODATA''' (Iterative Self-Organising Data Analysis Technique Algorithm) builds on k-means and tries to be smart in initial positions and in variations of k{{verify}}.

* '''H-means''' is a variation on k-means that recalculates the centroid only after a complete iteration over all the items, not after each reassignment. 
: Seen one way, it checks for error decrease less often, which makes it a smidge more sensitive to local minima and perhaps doesn't converge as nicely.
: Although the difference in practice tends to be slight, k-means tends to be the slightly safer (and much more common) choice, even if the order it handles elements in is a different kind of bias that h-means avoids.

=====Canopy clustering=====
<!--
In part the idea that you can deal with more data if you first do rough and fast clustering within windows, then merge that, and continue with more accurate clustering (e.g. hierarchical or k-means).

...where those windows can be quickly calculated. The windows are intended to overlap, so a bunch of data plays in more than one such pre-clustering.
-->
https://en.wikipedia.org/wiki/Canopy_clustering_algorithm

=====Bisecting k-means=====
{{stub}}


=====hard c-means=====
{{stub}}


=====UPGMA, WPGMA=====
{{stub}}

UPGMA = Unweighed Pair Group Method using Arithmetic averaging

WPGMA = Weighed Pair Group Method using Arithmetic averaging

(These specific names/abbreviations come from Sneath and Sokal 1973)


UPGMA assigns equal weight to all distances:
 D((u,v),w) = (n<sub>u</sub>*D(u,w) + n<sub>v</sub>*D(v,w)) / (n<sub>u</sub>+n<sub>u</sub>)

WPGMA uses:
 D((u,v),w) = (n<sub>u</sub>*D(u,w) + n<sub>v</sub>*D(v,w)) / 2


In the unweighed variant, the two ''things'' being combined weigh equally, 
in the weighed variant, all leaves that are part of a cluster weigh in as much as the other part. 


Bottom-up combiners working from a difference matrix, combining whatever leaf/cluster distance is minmal, then recalculating the difference matrix. 


It's not too hard too argue this terminology is a little arbitrary

=====UPGMC, WPGMC=====
{{stub}}

Unweighed Pair Group Method using Centroids, and 
Weighed Pair Group Method using Centroids

(the specific names/abbreviations come from Sneath and Sokal 1973)

=====Fuzzy c-means (FCM)=====
{{stub}}

* Type: '''fuzzy''' clustering (not really partitioning anymore)

Method: Like k-means, but weighs centroid recentering calculations by fuzzy distance to all data points

http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/cmeans.html

http://www.scholarpedia.org/article/Fuzzy_C-Means_Cluster_Analysis

=====Fuzzy k-means=====
{{stub}}

http://www.know-center.tugraz.at/forschung/wissenserschliessung/downloads_demos/fuzzy_k_means_and_k_means_clustering_demo

=====Shell clustering=====
{{stub}}

Basic fuzzy c-means would include by a radius - a sphere.

There are various other options, including:
* fuzzy c-quadric shells algorithm (FCQS) detects ellipsoids
* fuzzy c-varieties algorithm (FCV) detects infinite lines (linear manifolds) in 2D
* adaptive fuzzy c-varieties algorithm (AFC): detects line segments in 2D data
* fuzzy c-shells algorithm (FCS) detects circles
* fuzzy c-spherical shells algorithm (FCSS) detects circles
* fuzzy c-rings algorithm (FCR) detects circles
* fuzzy c-rectangular shells algorithm (FCRS) detects rectangles

* Gath-Geva algorithm (GG) detects ellipsoids

* Gustafson-Kessel algorithm (GK) detects ellipsoids of roughly the same size

=====PAM=====
Partitional, medoid-based

=====CLARA=====
Partitional, medoid-based


=====AGNES=====
Hierarchical

AGglomerative NESting

=====DIANA=====
Hierarchical, divisive

DIvisive ANAlysis - the idea is that at every step, the most homogenous cluster is split in two

=====Buckshot=====
Hybrid

=====Birch=====
Hybrid

BIRCH (balanced iterative reducing and clustering using hierarchies)

https://en.wikipedia.org/wiki/BIRCH

=====Cure=====
Hybrid

Clustering Using REpresentatives

https://en.wikipedia.org/wiki/CURE_algorithm

=====Rock=====
Hybrid


[http://theory.stanford.edu/~sudipto/mypapers/categorical.pdf "Rock: A robust clustering algorithm for categorical attributes"]

=====Chameleon=====
Hybrid, Hierarchical


[https://www-users.cs.umn.edu/~hanxx023/dmclass/chameleon.pdf "CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling"]

=====DBSCAN=====

Density-based.

The assumption that real objects will always be a dense cloud of points more easily rejects random points as noise/outliers (even if relatively close). 

It can also deal decently with closeby nonlinear clusters, if separated cleanly.



http://en.wikipedia.org/wiki/DBSCAN

=====OPTICS=====
Similar to DBSCAN

https://en.wikipedia.org/wiki/OPTICS_algorithm

=====FLAME=====
Fuzzy, density-based

http://en.wikipedia.org/wiki/FLAME_Clustering



=====Clustering by Committee (CBC)=====
Hybrid


Based on responsive elements (a comittee) voting on specific outcomes.


See also:
* http://www.aclweb.org/aclwiki/index.php?title=CBC
* PA Pantel (2003) ''Clustering by Committee'' [http://scholar.google.com/scholar?q=pantel+%22Clustering+by+Committee%22]


=====Principal Direction Divisive Partitioning (PDDP)=====


=====Information Bottleneck=====


See also:
* https://en.wikipedia.org/wiki/Information_bottleneck_method
* N Slonim, "{{search|The Information Bottleneck: Theory and Applications}}"


=====Agglomerative Information Bottleneck=====

See also:
* N Slonim, N Tishby (1999) "{{search|Slonim Tishby Agglomerative Information Bottleneck|Agglomerative Information Bottleneck}}"

=====Expectation Maximization Clustering=====

===Related fields===

<!--


Particularly bio-informatics and AI have seen specific research into finding relations in data, taxonomic overviews, and change over time - phylogenic relations. This may overlap somewhat with computational linguistics.

Bio-informatics is also one of the driving forces between concepts like:
* '''Phenetics''' are a group of techniques that mostly concerns itself with relations and separation in taxonomies, and attempts to classify by direct and overall similarity and differences, specifically the observable ones, rather than dealing with evolutionary (phylogenetic) relations. Its main developers are probably Sokal and Sneath.

* '''Cladistics''' are a set of (computationally hungier) techniques that focuses more on phylogenetic relations.  It places a few stricter requirements on the data.  Its focus on clades is somewhat specific to evolutionary biology, so phenetics is also still used.  

* Dendrograms, phylograms (from phylogenetics) and cladograms (from cladistics) are fairly closely related -- arguably the largest difference is that the name suggests what type of data they were based on{{verify}}, and how they can be visualised.

-->
===See also===
* http://www.statsoft.com/textbook/stcluan.html
* http://www.cs.joensuu.fi/pages/franti/vq/algorithms.htm

=State observers / state estimation (and filters in this sense)=

'''State observers''' / '''state estimation''' will estimate the internal state of a real system,
measuring what they easily can, and estimating what they need to, 

Good knowledge of a system is useful to various control problems.


===Bayes estimator, Bayes filter===
<!--

A Bayes estimator could refer to anything that computes narrowing belief about state.

(The name seems to indicate the bayesian approach, as in contrasting with frequentist?{{verify}})

Generally assuming everything has (linear {{verify}} and) gaussian-distribution behaviour.

See also:
* https://en.wikipedia.org/wiki/Bayes_estimator


A '''Bayes filter''', a.k.a. '''recursive Bayesian estimation''',



See also:
* https://en.wikipedia.org/wiki/Recursive_Bayesian_estimation



https://johnwlambert.github.io/bayes-filter/
-->


====alpha-beta filter====
An alpha beta filter (a.k.a. f-g filter, g-h filter)

====Kalman filter====
<!--

A Kalman filter is a estimator.
('Filter' is somewhat misleading, and seems to refer mostly to it being pretty noise-robust)

Related are
: Linear Quadratic Estimator (LQE), which is basically synonymous with Kalman filter
: Linear Quadratic Regulator (LQR)
: Linear Quadratic Gaussian (LQG) control, which is basically LQE+LQR


Is optimal for linear systems, in the sense that its state minimizes the [[mean squared error]] -- '''if''' the noise on the signal is gaussian. {{verify}}

It is iterative (steps in states, used to recalculate), and for most applications you can construct a model computationally simple enough to be carried out in real-time.


It combines prediction of next state with correction from measurements, calculating a new state based on
: sensor data, assumed to be noisy
: current state, assumed to be an estimate
: a model of the system's dynamics (e.g. constraints from basic physics)

And in the case of control,
: control commands, assumed to be somewhat uncertain



Kalman is attractive for applications that update their model as they go - such as in tracking, control, 
certain kinds of prediction, 
and it lends itself to sensor fusion.

It is used in satellite receivers, smartphones, games, and such.




Kalman can be introduced/derived via vector algebra, but it helps to have some intuition for what it's doing.



Also cases where you cannot easily measure directly but you do have a decent idea of what the influences are,

Which is itself a little feedback control system: you're minimizing the error of what you can measure,
because {{comment|(under a few assumptions, e.g. [[observability]] and [[controllability]])}} once your model seems to be a good predictor of the thing you ''can'' match, it's also probably a good estimator of the thing you can't.




Many explanations focus on the Kalman gain part, which is 
: E<sub>mea</sub> - error in measurement, e.g. the precision of a sensor, and usually fixed
: E<sub>est</sub> - error in estimation, something we estimate over time (but may start around E<sub>mea</sub>)

Then we define
: KG = E<sub>est</sub> / (E<sub>est</sub> + E<sub>mea</sub>)


It helps to see / do a numerical example (e.g. [https://www.youtube.com/watch?v=PZrFFg5_Sd0] and [https://www.youtube.com/watch?v=SIQJaqYVtuE]) of how KG and Eest change in a few steps.

Note that on such a one-dimensional variable and without much model, it amounts to a complex implementation of a basic lowpass (like [[EWMA]]), and you might prefer that unless/until you have interest in Kalman's estimate of error, or models that try to reduce it.



----



: Higher gain places more weight on measurements, giving faster response, but erratic if the model is imprecise
: lower gain places more weight on the model, giving smoother but slower response



Similarly, you can estimate the location of a car to show on a navigation system.

GPS is a great start to give you absolute positioning, but it gives you relatively slow updates,
and regularly error up to a few meters, and be a little behind.

Adding an accelerometer would be great at detecting cornering, but would drift over time, though this would only matter in tunnels. You could add whatever other information you have, like current speed, angle of your steering wheel, even information ABS has, and model it somehow to narrow down what your car is likely doing in the next few seconds to better decent accuracy. 


As an estimator (instead of a controller) this will never be asThis one's never perfect because the controller isn't it but you, but for navigation display it's better than any of these sensors alone.



Note that such examples often stay vague about the contents of the model.
While absolutely important to real-world implication, 
in a broader view of Kalman models it's more important to understand how and when errors converge.








We assume that state at time t depends only on the one directly before (t-1), and on the effect of our own control, and on process noise.

Each update is two basic parts.
* time update - prediction
* measurement update - correction



More formally, we assume that state at discrete time t evolved from t-1 like:
x<sub>t</sub> = F<sub>t</sub> x<sub>t-1</sub> + B<sub>t</sub> u<sub>t</sub> + w<sub>t</sub>
where {{comment|(note that not all of these need to vary with time)}}
: x<sub>t</sub> is the state vector - the system parameters we chose, at time t

: F<sub>t</sub> is the state transition matrix - basically the amount of effect of the previous state on this one
:: usually keeps most things very similar (so resembles an identity matrix){{verify}}
:: can get more complex when your state contains related variables, such as position and speed{{verify}}

: B<sub>t</sub> is a matrix containing the amount of effect the control vector is expected to have (on each part of state)
: u<sub>t</sub> is the control vector, the value of specific controls

: w<sub>t</sub> is the process noise for each system parameter
:: assumed to come from a zero-mean (accordingly multivariate) gaussian distribution with [[covariance]]
described by Q<sub>t</sub>




You typically also want to update the system with measurements.

 z<sub>t</sub> = H<sub>t</sub> x<sub>t</sub> + v<sub>t</sub>
where:
: z<sub>t</sub> is
: H<sub>t</sub> maps the state vector into the measurement domain
: x<sub>t</sub>, as above, is the state vector
: v<sub>t</sub> is the measurement noise for each measurement
:: assumed to come from a zero-mean gaussian distribution with [[covariance]] described by R<sub>t</sub>

https://en.wikipedia.org/wiki/Kalman_filter


One example you see is estimation of voltage, from noisy measurements - a 1D case to make the math and state simple. It is also a case that focuses more on measurement than predication. This also means it mostly just acts like a moving average {{comment|(similar to a [[EWMA]] style lowpass)}}.

Real-world tend to have at least a handful of variables.

A somewhat more interesting example is modelling a falling object. 
In this case, modeling the dynamics of the situation can really help the prediction step work well / not insist on skewing the result. Consider for example on how air drag means a terminal velocity.




====Extended kalman filter (EKF)====

Nonlinear version of the Kalman filter, which works by linearizing (think Taylor series) the transition around the place we want.

The state transition can be an arbitrary (differentiable) function, rather than a linear function / matrix.

While more flexible, it does not have the optimality guarantee, if state or process transition is inaccurate it is easily less stable.




-->

===Multi hypothesis tracking===


===Particle filter===
<!--
(Discrete, unlike most others here{{verify}})

https://en.wikipedia.org/wiki/Particle_filter
-->
===Data fusion===

<!--
Data fusion is, roughly, the idea that sometimes distinct (synchronized or otherwise cohereht) measurements on the same thing together hold better information than either measurement alone.

Intuitions often come from the subfield of sensor fusion. 
Say you want to count people in a place. 
A single camera on a scene might give decent information, but occlusion is a problem. 
Adding a side view is already a lot better.



https://en.wikipedia.org/wiki/Data_fusion

-->


====Sensor fusion====


=Optimization theory, control theory=
<!--
'''Optimization theory''' is basically applied mathematics (see also [ttps://en.wikipedia.org/wiki/Mathematical_optimization#Major_subfields mathematical optimization]) that finds the best choice in given data. 


Which is still very abstract, yes, and often sits along the more applied '''control theory''', which is concerned with the best course of action in, and feedback from, the real world.


Optimization theory tends to also describe cases where relatively complete analysis is possible or at least partially so, for better bounds on stability of control, knowledge of how complete learning can be, etc.

See e.g. terms like closed form analyis, solid state analyis.

-->

===Glossary===
<!--

'''Controller-related'''
* Controller - something that monitors and affects the operational conditions of given dynamic system

* Control system - [http://en.wikipedia.org/wiki/Control_system]

* Control loop - a (feedback) system that attempts to regulate a variable, in terms of something else

* Feedback - systems where output/control affects the thing being measured - that past influence will influence current/future state [http://en.wikipedia.org/wiki/Feedback]
** Positive feedback - refers to cases feedback reinforces itself. Without stabilizing forces this will lead to oscillation, to divergence, and small changes to result in very large. A technical example: a microphone too much near its amplified output, a sociological one: a stampede, a bank run. [http://en.wikipedia.org/wiki/Positive_feedback]
** Negative feedback - systems that try to avoid positive feedback (control opposing input and thereby itself), which means the system will tend to be more stable. [http://en.wikipedia.org/wiki/Negative_feedback]

* Proportional feedback 


* closed loop control
** system where there is feedback to check the output of the control (into the actuating system, or the control system), and correct any immediate problems.
** makes sense when short-term accuracy, waste, danger is relevant (e.g. in CNC devices, chemical processes, and such)
** If you measure system state fairly directly, you can (re)formulate things into a closed loop strategy by taking measured state as current state.

* open loop control (a.k.a. feed-forward?)
** systems where the control is ''assumed'' to arrive, and runs in a predetermined way. If it does not (e.g. a motor is blocked), there is no way to know.
** If you don't directly measure and can only really estimate, it's typically modelled as open loop.


* horizon: for systems that plan ahead...
** '''control horizon''' - refers to the finite future for which there is a control plan. If not the same as the prediction horizon, it will be shorter.
** '''predicton horizon''' - the finite future for which you have predicted the results of the planned control. If different than the control horizon, it is typically longer.
** 'what would you have to do to have to do no control after this time window?'
** finite-dimensional reduction (while QP, LP are infinite-dimensional, at least in the theory stage)

* Stability
** Is there a sensible/preditable domain on the output given a reasonable bound of the input?
** For closed-loop systems there are relatively simple analyses (e.g. Routh–Hurwitz)
** degree of stability, relative stability - 

* Setpoint - the target value that a controller aims to reach (when control is non-instant, which is usually)



'''Kalman's observability criterion''' and '''Kalman's controllability criterion''' are 


Controllability: In order to be able to do whatever we want with the given
dynamic system under control input, the system must be controllable.

Observability: In order to see what is going on inside the system under observation, the system must be observable.




'''Model/strategy/system terms and properties'''

{{comment|(Often useful properties to describe and express systems in terms familiar in DSP, in terms of feedback, to apply transforms like convolution, describe in terms things like a system's impulse response.)}}

* '''Linear system''' - one in which the output is homogenous and additive in terms of the input
** Linearity makes control simpler. (Linear estimates are occasionally used for simplicity's sake)
** Things like robots and such won't make for particularly linear systems

* Homogeneity - 

* Additivity - 

* Superposition - homegenous and additive

* Shift-invariance
** describes whether responses at different points in time are identical. For example, a sound amplifier is a shift-invariant linear system
** In modelling it is often useful to know whether a linear system is also shift-invariant

* linear filter - often synonymous with 'shift-invariant linear system'. 

* Linear feedback system - 

* Nonlinear system -

* Nonlinear feedback system - 

* Linear control systems - (control system with linear feedback) use linear negative feedback to produce a control signal mathematically based on other variables, with a view to maintaining the controlled process within an acceptable operating range.
** simple soltutions for linear systems (and systems that you can control under the assumption they are linear enough in the short term)

* saturation strategy - 

* windup - when the response to a setpoint change can mean significant accumulation of error, often meaning an overshoot. In particular in PID systems.
** Can have various causes, one of which controller's physical limitations (e.g. slower change), which PID can't really model, and which can cause the I part to go crazy.
** http://en.wikipedia.org/wiki/Integral_windup

* anti-windup strategy - some way of avoiding windup, such as ramping towards the setpoint, disabing I until we get closeish to the setpoint, modelling the actuator, or whatnot


* SISO, SIMO, MISO, MIMO - single/multiple input, single/multiple output. Has implication on the model's complexity, and computational compexity.

-->

===System analysis===
<!--

Note: timespan and type of dynamics are important - and interact

* For example, a chemical plant may easily have nonlinear dynamics, that work on the order of minutes or even hours

* Whereas computer process or network scheduling has to happen in less than milliseconds, and you can assume fairly linear dynamics



Limits on control:
* practical actuation constraints
** amplitide (e.g. actuator extents), slew rate (e.g. actuator speed limit, a servo may take up to a second to move to the target position)

* practical state constraints, 
** hard maximums such as a full water tank

* discrepancy on wished and and delivered control



All real-world problems are constrained in some way. Sometimes in minor ways you can ignore, while in other cases cannot, particularly where the state and/or set point are near a point where control would be constrained, which makes this a fundamental part of the problem statement.

Such constraints implicitly make control suboptimal, partly because it often makes the effective response time larger, and partly because some models cannot (and some just do not) consider such constraints.

Depending on goals and costs, it can be useful to actuate a little more than you otherwise would to reach a setpoint faster, but at the cost of possible instability, and in particular overshoot.

'''Windup''' refers to this pattern of overshoot. Also known as '''integral windup''' because it is the integral controller that causes this{{verify}}.
There is some theory on how to avoid and model it to predictably.

Linear system, symmetric control:
* 

Linear system, asymmetric control:



Example problems:
* Boat rudder control
** course keeping, but also using small adjustments to stabilize rolling motion (one actuator, two goals)
** limited in amplitude, slew rate

* Cruise control

* HVAC system

* Airplane aileron control
-->
====Problem theory====
<!--
Example description of linear system:
 x(t+1) = Ax(t) + Bu(t)
Where
* t is integer (discrete steps)

* x(t) is system state
* x(0) = z  (given start state)

* x has to be in a given set

* u is the control/action
* input/controls u are in a given set / constraints (e.g. throttle opening, aileron stops)

* Aim to minimize some cost function (may be sum over time)




Real-world problems are almost always due to various sorts of constraints, like actuator constraints (speed, delay, slew), and some fundamental details (reservoir size, etc.)

-->


====Types of problems====
<!--

LP, QP, and other approaches make it easy to model various entangled properties while keeping the way we manage a lot of interaction fairly easy to express and handle (mathematically speaking)

=====Second-order cone program (SOCP)=====
Relation to  Quadratically constrained quadratic program (QCQP) [http://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program] ?

======Linear Programming (LP)======
Special case of SOCP problems, 

* objective is linear function of the decision variables
* constraints are linear functions of the decision variables

For example:
* maximize/minimize: 
 c<sub>1</sub>x<sub>1</sub> + c<sub>2</sub>x<sub>2</sub> +...+ c<sub>n</sub>x<sub>n</sub>
* subject to 
 a<sub>11</sub>x<sub>1</sub> + a<sub>12</sub>x<sub>2</sub> +...+ a<sub>1n</sub>x<sub>n</sub> ~ b<sub>1</sub>    
 a<sub>21</sub>x<sub>1</sub> + a<sub>22</sub>x<sub>2</sub> +...+ a<sub>2n</sub>x<sub>n</sub> ~ b<sub>2</sub>    
   ...  
 a<sub>m1</sub>x<sub>1</sub> + a<sub>m2</sub>x<sub>2</sub> +...+ a<sub>mn</sub>x<sub>n</sub> ~ b<sub>m</sub>   
* with bounds:
 l<sub>1</sub> &le; x<sub>1</sub> &le; u<sub>1</sub>
 ...  
 l<sub>n</sub> &le; x<sub>n</sub> &le; u<sub>n</sub>    

Where 
* ~ can be &le;, = &ge;
* lower bound (l) and upper bound (u)  can be -inf, inf, real numbers

You would enter:
* objective function coefficients (c1, c2, ..., cn)
* constraint coefficients (a, right hand sides b)
* upper and lower bounds

The solution will be coefficients for x1.. xn



* typically solved via the simplex method [http://en.wikipedia.org/wiki/Simplex_method]
* Since all linear functions are convex, they are intrinsically easier and faster to solve than various types of non-linear programming problems.

* can determine:
(i) has no feasible solution
(ii) has an unbounded objective
(iii) has a globally optimal solution (single point or multiple equivalent points).


Mixed Integer Programming (MIP)
* LP with integer constraints [http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns]
* harder to solve?


'''Quadratic Programming (QP)'''
* special case of SOCP problems 
* objective is quadratic function of the decision variables
* constraints are linear functions of the decision variables


Constraint Programming (CSP)



When QPs were new, calculating them was heavy and complex. By now it's cheap (which is one reason MPC is fast ''enough'').
Note that it can be a lot faster when a specific problem is worked our and optimized for hardware, than the same model may be while part of a generic solver, such as prototyping in matlab.





Quadratic Program(ming) (QP): An optimization problem   with a quadratic objective function,  and linar constraints. In general:
 f(x) = cx + 1/2 x<sup>T</sup>Q x
subject to:
 Ax &lt; b 
 x &ge; 0




* Convex function - one that, within a given interval, lies below all possible line segments from two points on that interval. Visually: a dip.
** Useful property because this makes optimization tractible, partly because because local optimality is global optimality
** http://en.wikipedia.org/wiki/Convex_function

* Convex optimization: minimizing/maximizing convex functions 
** http://en.wikipedia.org/wiki/Convex_optimization
** Complex optimizations include:
*** Least squares [http://en.wikipedia.org/wiki/Least_squares]
*** Linear programming (LP) [http://en.wikipedia.org/wiki/Linear_programming]
*** Quadratic programming (QP) [http://en.wikipedia.org/wiki/Quadratic_programming]
*** Conic optimization [http://en.wikipedia.org/wiki/Conic_optimization]
*** Second order cone programming (SOCP) [http://en.wikipedia.org/wiki/Second-order_cone_programming]
*** Geometric programming [http://en.wikipedia.org/wiki/Geometric_programming]
*** Semidefinite programming [http://en.wikipedia.org/wiki/Semidefinite_programming]
*** Quadratically constrained quadratic programming [http://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_programming]
*** Entropy maximization [http://en.wikipedia.org/wiki/Entropy_maximization]

=====Closed form analysis=====


=====Steady state analysis=====


=====Unsorted=====

Linear-quadratic regulator [http://en.wikipedia.org/wiki/Linear-quadratic_regulator]

http://en.wikipedia.org/wiki/Category:Optimal_control


====Software====

'''C''':
* CSDP: C Library for Semidefinite Programming [https://projects.coin-or.org/Csdp]
* CVXGEN: Code Generation for Convex Optimization [http://cvxgen.com/]
** generates fast, library-free C code (useful for embedded use)

* http://www.stanford.edu/~boyd/papers/fast_mpc.html

'''Python''':
* http://jleny.wordpress.com/2009/12/31/python-control-libraries/
* CVXMOD: Convex optimization software in Python [http://cvxmod.net/]
* CVXOPT: Python Software for Convex Optimization [http://abel.ee.ucla.edu/cvxopt/]


'''Matlab''':
* CVX: Disciplined Convex Programming [http://cvxr.com/cvx/]
* SDPT3: semidefinite-quadratic-linear programming [http://www.math.nus.edu.sg/~mattohkc/sdpt3.html]
* SeDuMi: [http://sedumi.ie.lehigh.edu/]
* YALMIP [http://users.isy.liu.se/johanl/yalmip/]


-->

===Some controllers===

In terms of the (near) future:
* greedy control doesn't really look ahead.

* PID can be tuned for some basic tendencies

* MPC tries to minimize mistakes in predicted future



* For example, take a HVAC system that actively heats but passively cools. This effectively means you should be very careful of overshooting. You would make the system sluggish -- which also reduces performance because it lengthens the time of effects and settling



Non-linear:
* HVAC 



====Greedy controllers====

Doesn't look ahead, just minimizes for the current step.


Tends not to be stable.   Can be stable ''enough'' for certain cases, in particular very slow systems where slow control is fine, and accuracy not so important.

For example, water boilers have such large water volume, which has high heat capacity, that even a [https://en.wikipedia.org/wiki/Bang%E2%80%93bang_control bang-bang controller] (turn a few-hundred-watt heating element fully on or off according to temperature threshold) will keep the water within a few degrees of that threshold, simply because the water's heat capacity is large in relation to the heating element you'ld probably use (see also [https://en.wikipedia.org/wiki/Volumetric_heat_capacity#Thermal_inertia thermal inertia]).


If on the other hand the boiler's volume is small or the heater too powerful, it will spike much too warm, and average will be ''noticeably'' above the setpoint.

A proportional controller (e.g. for the boiler case, even slow PWM of that heating element) would probably be good enough.


....but more generally, greedy control tends to not be stable when you want control to be fast.
You easily run into the issue that actuation may be too fast for the measurement,
easily causing feedback and oscillations as well.

====Hysteresis (behaviour)====

<!--
Hysteresis refers to a system state depending on some amount of history,
and intuitively to sluggishness of response.

There is often some hysteresis in the measurement or control to avoid rapid switching - though such fast control isn't ''always'' a problem.
-->

====Hysteresis control (type)====

<!--
'''Hysteresis ''control'' '''

-->

====Map-based controller (type)====

<!--
Based on a lookup table, so determinisic.

Somewhat like greedy, but can have more interesting responses, 
because it lets you code nontrivial transfer function into a very simple IC (or even discrete solution).

It also theoretically lets you update parts


https://en.wikipedia.org/wiki/Map-based_controller
-->

====PID controller====
{{stub}}

PID is a fairly simple and generic control-loop system, still widely used in industrial control systems.

It is useful in systems that have to deal with some delay between and/or in actuation and sensing,
where they can typically be tuned to work better than greedy proportional-only controllers (and also be tuned to work worse - which you want to avoid).

Compared to some other cleverer methods, PID is computationally very cheap (a few adds and multiplies per step).


Yet:
* there is no easily quantified way to describe or guarantee optimality stability
:: you have to tune them, 
:: and ''learn'' how to tune them

* tuning is complex in that it depends on
:: how fast the actuation works
:: how fast you sample
:: how fast the system change in reaction / settles

* doesn't deal well with long time delays

* derivative component is sensitive to noise, so filtering may be a good idea

* has trouble controlling complex systems
: more complex systems should probably look to MPC or similar.

* linear at heart (assumes measurement and actuation are relatively linear)
:: so doesn't perform so well in non-linear systems 

* symmetric at heart, so not necessarily well-suited to non-symmetric actuation
:: consider e.g. a HVAC system -- which would oscillate around its target by alternately heating and cooling. 
:: It is much more power efficient to do one passively, e.g. active heating and passive cooling (if it's cold outside), or active cooling and passive heating (if it's warmer outside)
::: means it's easier to overshoot, and more likely to stick off-setpoint on the passive side, so on average be on one side
::: You could make the system sluggish -- in this case it reduces the speed at which it reaches the setpoint, but that is probably acceptable to you.
::: in other words: sluggish system and/or a bias to one side


=====Some definition=====
{{stub}}

The idea is to adjust the control based on some function of the error, and a Proportional–Integral–Derivative (PID) controller combines the three components it names, each tweaked with their own weight (gain).

The very short version is that 
* P adjusts according to the ''proportional'' error  
* I adjusts according to the ''integrated'' error
* D adjusts according to the ''derivative'' error


It can be summarized as:
: [[File:PID formula.png|300px]]
where 
* e(t) is the error
* P, I, and D are scalar weights controlling how much effect each component has


<!--
Roughly speaking, 
P looks at how far you currently are, 
I looks at where you've been over time,
D considers where you're probably going,


In practice, it turns out there are many cases where it makes sense to disable parts. 

* PI controllers (D turned off, or maybe just very low) may be more common than full PID
: because adding I does a little better than just P in many systems

: you see some full PID

: PD has relatively few specific applications

: just P can work well enough in situations with low mass/delay

: (I and D by themselves make little sense {{verify}})




-->

=====Some intuition=====
{{stub}}
<!--
Example time.

Say you're trying to match speeds with the car in front of you, and you have distance sensor. 

The easiest way is to have a target distance, and keep that constant.


You would probably make your error function (the thing that should go down to zero)
 measured_distance - intended_distance
and your actuation be the gas and brake pedals.


A '''P controller''' (and some people) would be using ''only'' at that distance, 
meaning you accelerate when it's too far away, and brake when you are too close.

A P controller would also base the magnitude of the response (how hard to hit the gas or brake pedal) on the magnitude of the error.

The gain of the P response would be a factor of how strong to press in response to the same amount of error.



That works, and the P factor will typically be the largest contributor in a PID system.

But there's a few practical details.

In any real world case there is some delay in the sensor, the decision, a the actuation - and in this case also some sluggish response because cars have mass.
Whatever you do, it happens late.

This means you're likely to overshoot a little, then to slow down to correct, accelerate again, brake, accelerate, etc.
If sensing and actuation was almost immediate, that oscillation would be smaller, but still there.

Not enough to cause accidents, but probably enough to make ''some'' passengers carsick, depending a little on how aggressive the adjustment.
: A very small P factor would be smoother ride, but react too slowly to changes and spend little of the time with distance or speed matched.
: A very large P factor makes any amount of oscillation stronger. In fact, if it starts far enough off-target (or gets far enough off-target) it may try to actuate so strongly it would never stabilize again. In the example, if you get far behind, you may race to get back, and never even consider braking before you cross your intended distance -- which with a large speed difference may be far too late. (this system doesn't actually model things like braking distance at all, which is why you wouldn't use it for this example in the real world)


Also, when the actuator
: has a lot of momentum, it'll oscillate harder
: is very immediate, it'll oscillate faster


Also, with P alone there is not necessarily much reason for the amount of oscillation (so reaction) to lower and disappear. It's almost like a conservation of energy thing.




One reason to consider D is that it reacts to changes in distance over time.

In this case it would reacts to changes in speed, and D by itself may even match speed, but at a distance you can't control. In most applications that's not useful and you would combine it with P.

As such, D is often added with a low factor, considered as a useful dampening for P and I efforts.
This also helps dampen oscillation over time.

Generally, D should be kept low, more so around noise, e.g. measurement noise

You can get better response with some lowpass on D (some suggest median instead), though too strong a lowpass cancels out the derivative control. It's not necessarily useful to have ''another'' thing to tune.

There is an argument that well tuned PI is better than moderately tuned PID.





One reason to consider I is that P and D basically still using one step for error calculation,
and at some small amount of error P would no longer respond (and and D won't react at all when error is constant), so PD may settle ''near'' but not ''on'' the setpoint.

That offset is stronger if there are system-inherent delays, or effects that push more in one direction than another - e.g. gravity in robot control, environment temperature when heating things, etc.


I effectively collects error over time, (its influence is proportional to magnitude ''and duration'' of error).

But for the same reason, this is most useful when already near the setpoint - the further away, the more it has a tendency of wanting to ''accelerate'' towards the setpoint, and just be another reason for overshoot and oscillations. 
As such, it's generally used with a rather small small factor, to help nudge it (P or PD) over to the real setpoint.

-->

<!--

Further properties
* differentiation is a shift-invariant linear operation, which makes it an interesting tool in systems with such properties.

See also:
* http://en.wikipedia.org/wiki/PID_controller
* http://www.google.com/search?q=PID%20without%20phd


https://controls.engin.umich.edu/wiki/index.php/PIDIntro

TODO: read:
* http://www.codeproject.com/Articles/36459/PID-process-control-a-Cruise-Control-example
* http://www.diydrones.com/profiles/blogs/announcing-arducopter-the?id=705844:BlogPost:163519&page=119#comments
* http://www.mstarlabs.com/docs/tn031.html
* http://www.expertune.com/tutor.aspx
* http://www.mstarlabs.com/docs/tn031.html





Examples / discussion


: '''Heating a large pot of water'''

...for example a boiler providing you with hot water trying to stay at a temperature.

The heat capacity of water is so large that given a few liters, even shoving a kilowatt in there will still only mean a bunch-of-degrees-per-minute change.

You don't even need P, as on and off (bang-bang control) is fine, 
particular if you don't care about overshooting a degree or two.   

A bit of hysteresis is fine, but mostly for the electronics involved relay.
The oscillation's asymmetry isn't a big issue either.



An example for when D is useful:

Say you are heating a wax, and its smoke point is not much higher than its melting point, meaning that while you want to get it to melt soon, you don't want to overshoot and burn it. {{comment|(note that in this example, you only get to actuate one way, adding heat, so we only need to discuss one side)}}

Assuming your heater is good enough to increase the temperature quickly, PI alone would probably still overshoot, because it's not considering that heat added should be zero near the setpoint{{verify}}



-->

=====So how do you tune it?=====
<!--

There's always the "set enough P for reasonable actuation speed, add a much smaller amount of I and D, and decide if you're happy" method.


More specific advice depends on specifics.

Disturbance rejection and overshoot/oscillation are at odds in various cases. Decide what you want.


But also, there will generally be effects from 
* sampling rate
: mostly in relation to...

* actuation speed
: and how actuation relates to sampling -- they should probably be on the same order, or sample faster.

* time in which you want the system to settle
: and how actuation relates to sampling -- should probably sample faster than the time in which you want the system to settle

* speed at which you want to react

* overshoot

* noise





To be a little more exact, look at"
* [https://en.wikipedia.org/wiki/Ziegler%E2%80%93Nichols_method Ziegler-Nichols tuning]


-->

====MPC (Model Predictive Control)====
<!--
{{stub}}

For a basic intuition: Model predictive control (MPC) makes decisions based on how a basic numeric solution (e.g. quadratic programming) thinks the system would react to the planned control.

It makes a complete plan up to a given prediction horizon (some steps ahead), but only actually uses the first step for control.

The rest are basically there to avoid making predictable mistakes within the plan's timespan (which means that even if calculations are bad, it's often still better than greedy reaction based on the same). 

It will then measure and do the same thing again.

It typically tries to solve control to be finished at the end of the control horizon {{comment|(if that is infeasibile, that often means the horizon is too short)}}



As an idea it is fast enough to be realtime, in that what MPC wraps around what you already have is fairly basic math, so widely applicable, though currently mostly seen in industrial, particularly petrochemical control.

Many real-world applications are not fast, sometimes far from it, because designers often err on the side of thorough calculation, i.e. complex models, whenever control doesn't need to be that fast.

It also doesn't help that people don't think to use MPC for for smaller problems.
Also, some MPC toolboxes are set up for prototyping and generic problem solving, and are more flexible than they are fast.



Practical for multivariate systems, and applicable to non-linear systems. 

The mathematical properties (constraints, model) vary a little with the field's details, because different people came up with the same basic idea in different fields, and implemented it in different ways.

MPC is, arguably, the modern name that attempts to pull together a lot of closely-related theory (and names) - see e.g. '''finite lookahead control''', '''moving horizon control''', '''receding horizon control''', '''generalized predictive control''', '''dynamical matrix control''' and others.


Because the math of generic MPC is quadratic cost, it begs some comparison to Linear–Quadratic Regulators (LQR), and introductions tend to mention the differences.




Properties:
* Allows choice of model, including complex ones.

* Finite horizon of prediction
: that amount of future steps is calculated each step (hence some of the names)

* tends to work decently even when your basic model is flawed - because its plan tends to be stabilizing in the given timespan 
** ...assuming fairly complete state information
** partly because it avoids violating the given constaints within the timespan as well as it can, avoiding overreactions and some feedback
* MPC has advantages when things aren't so deterministic (when a model can't be perfect, when disturbances are likely). Depending a little on implementation, MPC still does fairly well when the future doesn't match the plan very much

* lets you models state contstraints more easily than some other systems, 
* ...so behaves in an anti-[https://en.wikipedia.org/wiki/Integral_windup windup] sort of way, within certain demands


Variations include:
* Linear MPC - called that when using a linear model  (even if the controlled system's dynamics aren't linear)
* nonlinear MPC - any computable model
* hybrid MPC - 
* state-based MPC - 
* stochastic MPC - 
* control using first few steps plan, only recalculate after that (cheaper calculation, also has further implications)
* explicit MPC (automatically generated), limited but still useful applications


See also:
* http://en.wikipedia.org/wiki/Model_predictive_control



http://www.mathworks.nl/products/mpc/index.html

-->

====FLC (Fuzzy Logic Control)====

<!--

See also:
* http://en.wikipedia.org/wiki/Fuzzy_control_system

-->

====LQR====
<!--

-->


===Q-learning===
{{stub}}

Q-learning is a specific type of [[#reinforcement learning]].

Q-learning models discretized (state,action) mapping, 
and learns the values for each mapping and implicitly the optimal action in each state,
by trial and error.

You can see it as a state-by-action table where each cell stores a value that is increased on success, decreased on failure (often with an EWMA{{verify}} to control learning rate?).

Like reward-based learning in general, Q-learning can be supported by something as simple or complex as you wish. 


The discretized approach mainly makes when there is a relatively small set of possible states and actions,
but the larger that space is, the longer it takes takes very long to actually learn enough for each pair.



''Deep'' Q-learning is a variant that outputs the value for all actions from a network instead, 
which is often a more compact way to store what can works out as a very large state space, and may be m

and can be more robust{{verify}}

<!--
The network seems a fairly generic MLP{{verify}}, but the method around it is still fairly specific.
-->

https://en.wikipedia.org/wiki/Q-learning

<!--
https://web.mst.edu/~gosavia/neural_networks_RL.pdf

https://www.analyticsvidhya.com/blog/2019/04/introduction-deep-q-learning-python/

https://pythonprogramming.net/deep-q-learning-dqn-reinforcement-learning-python-tutorial/

https://visualstudiomagazine.com/articles/2014/08/01/batch-training.aspx
-->

===See also===

* http://en.wikibooks.org/wiki/Control_Systems





[[Category:Math on data]]
[[Category:Algorithms]]

=Semi-sorted=

===Structured prediction===
<!--
: yes, you could approached these questions as a series of independent classifications, but there is often reason that considering them together gives better answers
: we use the name when this consideration is part of our problem, e.g. when our scoring function considers this
: For example
:: taking written letters and detecting words will probably consider whether the series forms a word
:: assigning lexical categories to words in a sentence, which will often include sentence structure (e.g. via dependency-tree analysis)
:: figuring out what objects an image contains may consider which objects make sense together
: the output doesn't need to be highly structured itself

https://www.youtube.com/watch?v=e5sPNlgbZAE

https://pystruct.github.io/intro.html

https://en.wikipedia.org/wiki/Structured_prediction
-->

===Mistake Bound learning===
<!--

Basically any where the algoritm predicts a classification of an unlabeled example,
and is later told the correct answer.

With just that, it sounds like supervised learning you could do in any way,
but the name points at an approach that learns the logical conjunction of features,
so learning whether each presumed features has positive, negative, or no contribution.



http://pages.cs.wisc.edu/~yliang/cs760_fall17/slides/lecture16-learning-theory-2.pdf


-->

===PAC theory===
<!--

Whenever you're learning from examples, Probably Approximately Correct (PAC) theory is an analysis that (among some other things) helps you think about the lower bounds of generalization error of a generatization function.


Learning from examples often means training a generalizing function, so you will run into questions like
* how many examples are needed to learn the concept decently?
* what is success, when some examples may conflict?
* how well can I expect this to work on unseen examples? 

PAC e.g. e.g. lets us estimate the likelines off achieving a particular accuracy



https://www.cs.utexas.edu/~klivans/f06lec2.pdf

-->


[[Category:Algorithms]]
[[Category:Math on data]]
[[Category:Machine Learning]]

===Evolutionary/genetic computation===
{{stub}}

For context:

Part of a wider category of evolutionary computation, which is is inspired by the observation that biological evolution tends to adapt well for a specific task.

Evolutionary computation is a wider field including concepts like optimizations imitating ant colonies or particle swarms, to gene expression, to self-organization, to agent-based modeling, to genetic programming. 


Applications include include classification, curve fitting and other statistical/data modelling, feature selection. 

Perhaps the largest applications lie around gaming, research, as people don't seem to like the opaqueness of the method for 'real' applications. But now that we're okay with equally opaque neural networks, perhaps that has ended? (and yes, things like [[NEAT]] apply for both and works decently).


Technically, '''genetic algorithms''' focus more on the evolutionary concepts and is more a method that barely gets into possible implementations, while '''genetic programming''' on its application specifically to generating machine programs, but border between the two is sometimes vague and used interchangably.


'''Genetic programming''' is specifically concerned with generating a program fit for a specific task by trial and error, with the largest components being a fitness function and introducing some randomness in a group (population) of candidate programs.

The representation that is altered can be anything productive, from trees of operators to machine code to neural nets.


Practically, you have to deal with aspects like
* generating an initial population
* evaluate fitness of individuals
* deciding how much and how to 
** reproduce (copy as-is)
** cross over (combine into offspring)
** and mutate (applying a genetic variation) 
* deciding when to stop

=Unsorted=
<!--



Domain adaptation 


Zero-Shot Learning (ZSL) is when a learner is expected to learn a new class 
without having explicitly been shown examples. It is an extreme form of form of domain adaptation.

One-shot learning 

Few-show learning

...where classically we have large dataset of human-labeled 


Zero-shot learning still typically counts on auxiliary information, and knowledge transfer.
Consider how as a human, you might be able to visually identify a platypus, never having seen one,
but only descriptions.






(k-)Nearest Neighbour, a.k.a. kNN

Not the same as k-means. TODO: See [http://www.ir.iit.edu/~dagr/DataMiningCourse/Spring2001/Notes/Clustering.pdf] for distinction.

TODO: See [http://www.google.com/search?q=%22k-nearest%22%20neighbor%20%22k-means%22], [http://people.revoledu.com/kardi/tutorial/KNN/index.html], [http://www.autonlab.org/autonweb/software/10408.html], [http://www.dbs.informatik.uni-muenchen.de/~boehm/publications/dexa03-final.pdf]





* various at http://crd.lbl.gov/~cding/, http://ecology.msu.montana.edu/labdsv/R/, http://www.statsoft.com/textbook/stcluan.html

* [http://video.google.com/videoplay?docid=2546753955666121345 Google Video: Clustering aggregation (Aristides Gionis)]

* VQ / LVQ ((Learning) Vector Quantization)
** (apparently like kNN and SOM)

* Curvilinear Component Analysis (CCA)

* [http://en.wikipedia.org/wiki/Expectation-maximization_algorithm Expectation Maximization] 

* Quality Threshold (QT)
** Doesn't cluster elements deemed low quality


* Fuzzy ([[http://public.fh-wolfenbuettel.de/~hoeppnef/clustering.html]], [http://documents.wolfram.com/applications/fuzzylogic/Manual/12.html], [http://fuzzy.iau.dtu.dk/tutor/ddfm_files/v3_document.htm])


* Spectral Clustering http://crd.lbl.gov/~cding/Spectral/notes.html


* BSAS, see maybe [http://www-staff.it.uts.edu.au/~paulk/DMBio.cgi/pubs/paul-clustering.pdf]

* Artificial neural network (ANN)
* Self-organizing map (SOM) (sometimes Kohonen Map, or Self Organizing Feature Map) [http://www.sims.berkeley.edu/~hearst/irbook/10/node5.html]
** Usually used for reducing dimensionality 

* Shi-Malik
* Meila-Shi


* Discriminant Function Analysis (DFA, DA)


Trained Structure
Classifier


Adaptive Resonance Theory


Linear programming [http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html#Q1] [http://www.google.com/search?q=Integer%20Linear%20Programming]


*RIPPER



Tile coding: simple formalism to have learning affect similar states {{verify}}








* Jain, ''Murty, Data Clustering: A Review,'' (1999), [http://citeseer.csail.mit.edu/jain99data.html]
* [http://en.wikipedia.org/wiki/Data_clustering Wikipedia: Data clustering]
* http://www.kddresearch.org/Courses/Fall-2001/CIS732/Lectures/

* http://www.autonlab.org/tutorials/index.html


Software:
* [http://bips.u-strasbg.fr/fr/Documentation/ClustalX/ ClustalX]
* [http://evolution.genetics.washington.edu/phylip.html Phylip]


Unsorted:
http://citeseer.csail.mit.edu/722717.html

http://citeseer.csail.mit.edu/718017.html

http://citeseer.csail.mit.edu/guha98cure.html

http://citeseer.csail.mit.edu/chu02incremental.html

http://citeseer.csail.mit.edu/steinbach00comparison.html

http://citeseer.csail.mit.edu/karypis99chameleon.html

http://citeseer.csail.mit.edu/fred03robust.html

http://citeseer.csail.mit.edu/712324.html

http://citeseer.csail.mit.edu/topchy03combining.html

http://citeseer.csail.mit.edu/711453.html

http://citeseer.csail.mit.edu/706677.html

http://citeseer.csail.mit.edu/jain01structure.html

http://citeseer.csail.mit.edu/719978.html

http://citeseer.csail.mit.edu/714801.html

http://citeseer.csail.mit.edu/guha00rock.html

http://citeseer.csail.mit.edu/na01performance.html

http://citeseer.csail.mit.edu/260668.html

http://citeseer.csail.mit.edu/ng94efficient.html

http://citeseer.csail.mit.edu/cutting92scattergather.html

http://citeseer.csail.mit.edu/steinbach00comparison.html

http://citeseer.csail.mit.edu/fred02data.html

http://citeseer.csail.mit.edu/law04simultaneous.html

http://fuzzy.iau.dtu.dk/tutor/ddfm_files/v3_document.htm

http://citeseer.csail.mit.edu/masulli02soft.html


-->