08-模式识别-上下文分类详解.ppt

CONTEXT DEPENDENT CLASSIFICATION Remember: Bayes rule Here: The class to which a feature vector belongs depends on: Its own value(它自己的数值) The values of the other features(其它特征向量的值) An existing relation among the various classes(各类之间的关系) 这种相互关系要求分类必须同时对所有可能的特征向量进行。 Thus, we will assume that the training vectors occur in sequence, one after the other and we will refer to them as observations The Context(上下文) Dependent Bayesian Classifier Let Let Let be a sequence of classes, that is There are MN of those Thus, the Bayesian rule can equivalently be stated as It is equavelent to Markov Chain Models (for class dependence) Assume: statistically mutually independent The pdf in one class independent of the others, then From the above, the Bayes rule is readily(容易地) seen to be equivalent to: that is, it rests on To find the above maximum in brute-force(强力) task we need Ο(NMΝ ) operations!! The Viterbi Algorithm Thus, each Ωi corresponds to one path through the trellis(格子) diagram. One of them is the optimum (e.g., black). The classes along the optimal path determine the classes to which ωi are assigned. To each transition corresponds a cost. For our case Equivalently where, Define the cost up to a node ,k, Bellman’s principle now states The optimal path terminates at(终结在) Complexity O (NM2) Channel Equalization(信道均衡p.231) The problem Example In xk three input symbols are involved: Ik, Ik-1, Ik-2 Not all transitions are allowed Then In this context, ωi are related to states. Given the current state(当前状态) and the transmitted bit(转移位), Ik, we determine the next state. The probabilities P(ωi|ωj) define the state dependence model(状态依赖模型). The transition cost(转移代价) for all allowable transitions Assume: Noise white and Gaussian(白的或高斯的) A channel impulse response (通道脉冲响应) estimate to be available The states are determined