Multi-track Turing machine

2013-11-11T22:54:33Z

46.244.238.12: /* Proof of equivalency to standard Turing machine */

In [[data mining]], '''cluster-weighted modeling (CWM)''' is an algorithm-based approach to non-linear prediction of outputs ([[Dependent and independent variables|dependent variables]]) from inputs ([[Dependent and independent variables|independent variables]]) based on [[density estimation]] using a set of models (clusters) that are each notionally appropriate in a sub-region of the input space. The overall approach works in jointly input-output space and an initial version was proposed by [[Neil Gershenfeld]].<ref>Gershenfeld, N. (1997) "Nonlinear Inference and Cluster-Weighted Modeling", ''Annals of the New York Academy of Sciences'', 808, 18–24. {{DOI|10.1111/j.1749-6632.1997.tb51651.x}}</ref><ref name=nature>Gershenfeld, N., Schoner, B.* & Metois, E. (1999) [http://www.nature.com/nature/journal/v397/n6717/pdf/397329a0.pdf Cluster-weighted modelling for time-series analysis], Nature, 397 (28 Jan. 1999), 329–332 </ref>

==Basic form of model==
The procedure for cluster-weighted modeling of an input-output problem can be outlined as follows.<ref name=nature/> In order to construct predicted values for an output variable ''y'' from an input variable ''x'', the modeling and calibration procedure arrives at a [[joint probability distribution|joint probability density function]], ''p''(''y'',''x''). Here the "variables" might be uni-variate, multivariate or time-series. For convenience, any model parameters are not indicated in the notation here and several different treatments of these are possible, including setting them to fixed values as a step in the calibration or treating them using a [[Bayesian analysis]]. The required predicted values are obtained by constructing the [[conditional probability distribution|conditional probability density]] ''p''(''y''|''x'') from which the prediction using the [[conditional expected value]] can be obtained, with the [[conditional variance]] providing an indication of uncertainty.

The important step of the modeling is that ''p''(''y''|''x'') is assumed to take the following form, as a [[mixture model]]:
:<math>p(y,x)=\sum_1^n w_jp_j(y,x), </math>
where ''n'' is the number of clusters and {''wj''} are weights that sum to one. The functions ''pj''(''y'',''x'') are joint probability density functions that relate to each of the ''n'' clusters. These functions are modeled using a decomposition into a conditional and a [[marginal distribution|marginal density]]:
:<math>p_j(y,x)=p_j(y|x)p_j(x), </math>
where:
:*''pj''(''y''|''x'') is a model for predicting ''y'' given ''x'', and given that the input-output pair should be associated with cluster ''j'' on the basis of the value of ''x''. This model might be a [[regression analysis|regression model]] in the simplest cases.

:*''pj''(''x'') is formally a density for values of ''x'', given that the input-output pair should be associated with cluster ''j''. The relative sizes of these functions between the clusters determines whether a particular value of ''x'' is associated with any given cluster-center. This density might be a [[Gaussian function]] centered at a parameter representing the cluster-center.

In the same way as for [[regression analysis]], it will be important to consider preliminary [[data transformation]]s as part of the overall modeling strategy if the core components of the model are to be simple regression models for the cluster-wise condition densities, and [[normal distribution]]s for the cluster-weighting densities ''pj''(''x'').

==General versions==
The basic CWM algorithm gives a single output cluster for each input cluster. However, CWM can be extended to multiple clusters which are still associated with the same input cluster.<ref name="feldkamp">{{cite journal|last=Feldkamp|first=L.A.|coauthors=Prokhorov, D.V.; Feldkamp, T.M.|date=2001|title=Cluster-weighted modeling with multiclusters|journal=International Joint Conference on Neural Networks|volume=3|issue=1|pages=1710–1714|url=http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/7474/20319/00938419.pdf?temp=x}}</ref> Each cluster in CWM is localized to a Gaussian input region, and this contains its own trainable local model.<ref name="mit">{{cite journal|last=Boyden|first=Edward S.|title=Tree-based Cluster Weighted Modeling: Towards A Massively Parallel Real-Time Digital Stradivarius|publisher=MIT Media Lab|location=Cambridge, MA|url=http://edboyden.org/violin.pdf}}</ref> It is recognized as a versatile inference algorithm which provides simplicity, generality, and flexibility; even when a feedforward layered network might be preferred, it is sometimes used as a "second opinion" on the nature of the training problem.<ref name="dearborn"/>

The original form proposed by Gershenfeld describes two innovations:
* Enabling CWM to work with continuous streams of data
* Addressing the problem of local minima encountered by the CWM parameter adjustment process<ref name="dearborn">{{cite journal|last=Prokhorov|first=A New Approach to Cluster-Weighted Modeling Danil V.|coauthors=Lee A. Feldkamp, and Timothy M. Feldkamp|title=A New Approach to Cluster-Weighted Modeling|publisher=Ford Research Laboratory|location=Dearborn, MI|url=http://home.comcast.net/~dvp/cwm.pdf}}</ref>

CWM can be used to classify media in printer applications, using at least two parameters to generate an output that has a joint dependency on the input parameters.<ref name="media">{{cite journal|last=Gao|first=Jun|coauthors=Ross R. Allen|date=2003-07-24|title=CLUSTER-WEIGHTED MODELING FOR MEDIA CLASSIFICATION|publisher=World Intellectual Property Organization|location=Palo Alto, CA |url=http://www.wipo.int/pctdb/en/wo.jsp?wo=2003059630}}</ref>

==References==
{{Reflist}}

[[Category:Multivariate statistics]]
[[Category:Data clustering algorithms]]
[[Category:Estimation of densities]]

formulasearchengine - User contributions [en]

Multi-track Turing machine