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

{{math notes}}
{{stub}}


[[Category:Math on data]]


==Concepts & glossary==

The '''[http://en.wikipedia.org/wiki/Curse_of_dimensionality curse of dimensionality]''' is, roughly, the idea that when you add a dimension to your model you need proportionally more data for decent training of that model. Similarly, since the volume increases so fast, you probably have a sparsity problem. 
It's a fairly exponential problem, so 





===Stochastic processes, deterministic processes, random fields===


A '''deterministic process''' deals with possible determined cases, 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, because you only need partial data and can generally only get partial data.


(Models mixing deterministic and stochastic processes are often called hybrid models)


A '''random field''' basically describes the generalization that happens when the parameter (dependent variable) is not necessarily time, or one-dimensional, or real-valued.


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

-->

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



===Types of problems===

Tasks are often one of:

* '''Clustering''' points out regions or 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 may not be the best choice of a learning/predicting system

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

* '''Dimensionality reduction''': projecting attributes into lower-dimensional data
: where 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

* others...

===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 {{comment|(and input, 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]

* 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



-->

===Observability and controllability===

<!--
Also related are the concepts of [https://en.wikipedia.org/wiki/Observability observability] criterion and [https://en.wikipedia.org/wiki/Controllability controllability] criterion, introduced by Kalman.

Observability is the idea that the states of a system can be reasonably inferred from knowledge of its outputs.
Roughly, that a good set of sensors lets you build a model that covers the variables.{{verify}}

Controllability is roughly 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.

-->

===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
-->

===supervised versus unsupervised systems (learners)===

'''Supervised''' usually means the training process is suggested or somehow (dis)approved. Usually it refers to having annotated trainign data, sometimes to altering it. Example: Classification of documents, basic neural network back-propagation, least-squares fitting, operator cloning

'''Unsupervised''' refers to processes that work without intervention. For example, self-organizing maps, or clustering documents based on similarity needs no annotation.

'''Semi/lightly supervised''' usually means there is an iterative process which needs only minimal human intervention, be it to deal with a few unclear cases, for information that may be useful, or such.


===Inductive versus deductive systems (learners)===
'''Inductive''' refers to training purely from data.

'''Deductive''' refers to also having a theory about the domain domain.


Inductive learning can be approached as a search in a hypothesis space. <!--
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.

-->

===Model-based versus model-free systems (learners)===
<!--
When you base learning on models, this can save a lot of computation, but will often not be adaptive to things that don't fit that model well. 

Model-free often makes for a lot more possibilities and a lot more optimizaiton work.
-->

==Statistical modeling==
Data fusion means merging data from various sources, e.g. various sensors. 
This often implies some sort of modelling.


===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]
-->
====Linear regression====
<!--

-->
====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
-->

===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
-->

===Bayes estimator===
<!--
Basically something that computes belief about state, assuming everything has (linear {{verify}} and) gaussian behaviour.

A ''bayes filter'' is more specific, and also named '''recursive Bayesian estimation'''

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



====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.




-->

===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====

==Classifiers==


===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)
-->

=Semi-sorted=

 




[[Category:Algorithms]]
[[Category:Math on data]]
[[Category:Machine Learning]]

=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


-->