Bound on the probability of HMM misclassification
Date
2011ISBN
978-1-4577-0125-2Source
2011 19th Mediterranean Conference on Control and Automation, MED 20112011 19th Mediterranean Conference on Control and Automation, MED 2011
Pages
449-454Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
In this paper we consider the problem of classifying a sequence of observations among two known hidden Markov models (HMMs). We use a classifier that minimizes the probability of error (i.e., the probability of misclassification), and we are interested in assessing its performance by computing the a priori probability of error (before any observations are made). This probability (that the classifier makes an incorrect decision) can be obtained, as a function of the length of the sequence of observations, by summing up the probability of misclassification over all possible observation sequences, weighted by their corresponding probabilities. In an effort to avoid the high complexity associated with the computation of the exact probability of error, we establish an upper bound on the probability of error, and we find the necessary and sufficient conditions for this bound to tend to zero exponentially with the number of observation steps. We focus on classification among two HMMs that have the same language, which is the most difficult case to characterize; our approach can easily be applied to classification among any two arbitrary HMMs. The bound we obtain can also be used to approximate the dissimilarity between the two given HMMs. © 2011 IEEE.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Conference Object
Bounds on the probability of misclassification among hidden Markov models
Keroglou, C.; Hadjicostis, Christoforos N. (2011)Given a sequence of observations, classification among two known hidden Markov models (HMMs) can be accomplished with a classifier that minimizes the probability of error (i.e., the probability of misclassification) by ...
-
Conference Object
Hidden markov model classification based on empirical frequencies of observed symbols
Keroglou, C.; Hadjicostis, Christoforos N. (IFAC Secretariat, 2014)Given a sequence of observations, classification among two known hidden Markov models (HMMs) can be accomplished with a classifier that minimizes the probability of error (i.e., the probability of misclassification) by ...
-
Article
Measurement of the top-quark mass with dilepton events selected using neuroevolution at CDF
Aaltonen, T.; Adelman, J.; Akimoto, T.; Albrow, M. G.; Ãlvarez Gonzãlez, B.; Amerio, S.; Amidei, D.; Anastassov, A.; Annovi, A.; Antos, J.; Apollinari, G.; Apresyan, A.; Arisawa, T.; Artikov, A.; Ashmanskas, W.; Attal, A.; Aurisano, A.; Azfar, F.; Azzurri, P.; Badgett, W.; Barbaro-Galtieri, A.; Barnes, V. E.; Barnett, B. A.; Bartsch, V.; Bauer, G.; Beauchemin, P. -H; Bedeschi, F.; Bednar, P.; Beecher, D.; Behari, S.; Bellettini, G.; Bellinger, J.; Benjamin, D.; Beretvas, Andrew; Beringer, J.; Bhatti, A.; Binkley, M.; Bisello, D.; Bizjak, I.; Blair, R. E.; Blocker, C.; Blumenfeld, B.; Bocci, A.; Bodek, A.; Boisvert, V.; Bolla, G.; Bortoletto, D.; Boudreau, J.; Boveia, A.; Brau, B.; Bridgeman, A.; Brigliadori, L.; Bromberg, C.; Brubaker, E.; Budagov, J.; Budd, H. S.; Budd, S.; Burkett, K.; Busetto, G.; Bussey, P.; Buzatu, A.; Byrum, K. L.; Cabrera, S.; Calancha, C.; Campanelli, M.; Campbell, M.; Canelli, Florencia M.; Canepa, A.; Carlsmith, D.; Carosi, R.; Carrillo, S.; Carron, S.; Casal, B.; Casarsa, M.; Castro, A.; Catastini, P.; Cauz, D.; Cavaliere, V.; Cavalli-Sforza, M.; Cerri, A.; Cerrito, L.; Chang, S. H.; Chen, Y. C.; Chertok, M.; Chiarelli, G.; Chlachidze, G.; Chlebana, F.; Cho, K.; Chokheli, D.; Chou, J. P.; Choudalakis, G.; Chuang, S. H.; Chung, K.; Chung, W. H.; Chung, Y. S.; Ciobanu, C. I.; Ciocci, M. A.; Clark, A.; Clark, D.; Compostella, G.; Convery, M. E.; Conway, J.; Copic, K.; Cordelli, M.; Cortiana, G.; Cox, D. J.; Crescioli, F.; Cuenca Almenar, C.; Cuevas, J.; Culbertson, R.; Cully, J. C.; Dagenhart, D.; Datta, M.; Davies, T.; De Barbaro, P.; De Cecco, S.; Deisher, A.; De Lorenzo, G.; Dell'Orso, M.; Deluca, C.; Demortier, L.; Deng, J.; Deninno, M.; Derwent, P. F.; Di Giovanni, G. P.; Dionisi, Carlo; Di Ruzza, B.; Dittmann, J. R.; D'Onofrio, M.; Donati, S.; Dong, P.; Donini, J.; Dorigo, T.; Dube, S.; Efron, J.; Elagin, A.; Erbacher, R.; Errede, D.; Errede, S.; Eusebi, R.; Fang, H. C.; Farrington, S.; Fedorko, W. T.; Feild, R. G.; Feindt, M.; Fernandez, J. P.; Ferrazza, C.; Field, R.; Flanagan, G.; Forrest, R.; Franklin, M.; Freeman, J. C.; Furic, I.; Gallinaro, M.; Galyardt, J.; Garberson, F.; Garcia, J. E.; Garfinkel, A. F.; Genser, K.; Gerberich, H.; Gerdes, D.; Gessler, A.; Giagu, S.; Giakoumopoulou, V. A.; Giannetti, P.; Gibson, K.; Gimmell, J. L.; Ginsburg, C. M.; Giokaris, N.; Giordani, M.; Giromini, P.; Giunta, M.; Giurgiu, G.; Glagolev, V.; Glenzinski, D.; Gold, M.; Goldschmidt, N.; Golossanov, A.; Gomez, G.; Gomez-Ceballos, G.; Goncharov, M.; González, O.; Gorelov, I.; Goshaw, A. T.; Goulianos, Konstantin; Gresele, A.; Grinstein, S.; Grosso-Pilcher, C.; Group, R. C.; Grundler, U.; Guimaraes Da Costa, J.; Gunay-Unalan, Z.; Haber, C.; Hahn, K.; Hahn, S. R.; Halkiadakis, Eva; Han, B. -Y; Han, J. Y.; Handler, R.; Happacher, F.; Hara, K.; Hare, D.; Hare, M.; Harper, S.; Harr, R. F.; Harris, R. M.; Hartz, M.; Hatakeyama, K.; Hauser, J.; Hays, C.; Heck, M.; Heijboer, A.; Heinemann, B.; Heinrich, J.; Henderson, C.; Herndon, M.; Heuser, J.; Hewamanage, S.; Hidas, D.; Hill, C. S.; Hirschbuehl, D.; Hocker, A.; Hou, S.; Houlden, M.; Hsu, S. -C; Huffman, B. T.; Hughes, R. E.; Husemann, U.; Huston, J.; Incandela, J.; Introzzi, G.; Iori, M.; Ivanov, A.; James, E.; Jayatilaka, B.; Jeon, E. J.; Jha, M. K.; Jindariani, S.; Johnson, W.; Jones, M.; Joo, K. K.; Jun, S. Y.; Jung, J. E.; Junk, T. R.; Kamon, T.; Kar, D.; Karchin, P. E.; Kato, Y.; Kephart, R.; Keung, J.; Khotilovich, V.; Kilminster, B.; Kim, D. H.; Kim, H. S.; Kim, J. E.; Kim, M. J.; Kim, S. B.; Kim, S. H.; Kim, Y. K.; Kimura, N.; Kirsch, L.; Klimenko, S.; Knuteson, B.; Ko, B. R.; Koay, S. A.; Kondo, K.; Kong, D. J.; Konigsberg, J.; Korytov, A.; Kotwal, A. V.; Kreps, M.; Kroll, J.; Krop, D.; Krumnack, N.; Kruse, M.; Krutelyov, V.; Kubo, T.; Kuhr, T.; Kulkarni, N. P.; Kurata, M.; Kusakabe, Y.; Kwang, S.; Laasanen, A. T.; Lami, S.; Lammel, S.; Lancaster, M.; Lander, R. L.; Lannon, K.; Lath, A.; Latino, G.; Lazzizzera, I.; Lecompte, T.; Lee, E.; Lee, S. W.; Leone, S.; Lewis, J. D.; Lin, C. S.; Linacre, J.; Lindgren, M.; Lipeles, E.; Lister, A.; Litvintsev, D. O.; Liu, C.; Liu, T.; Lockyer, N. S.; Loginov, A.; Loreti, M.; Lovas, L.; Lu, R. -S; Lucchesi, D.; Lueck, J.; Luci, C.; Lujan, P.; Lukens, P.; Lungu, G.; Lyons, L.; Lys, J.; Lysak, R.; Lytken, E.; MacK, P.; MacQueen, D.; Madrak, R.; Maeshima, K.; Makhoul, K.; Maki, T.; Maksimovic, P.; Malde, S.; Malik, S.; Manca, G.; Manousakis-Katsikakis, A.; Margaroli, F.; Marino, C.; Marino, C. P.; Martin, A.; Martin, V.; Martínez, M.; Martínez-Ballarín, R.; Maruyama, T.; Mastrandrea, P.; Masubuchi, T.; Mattson, M. E.; Mazzanti, P.; McFarland, K. S.; McIntyre, P.; McNulty, R.; Mehta, A.; Mehtala, P.; Menzione, A.; Merkel, P.; Mesropian, C.; Miao, T.; Miladinovic, N.; Miller, R.; Mills, C.; Milnik, M.; Mitra, A.; Mitselmakher, G.; Miyake, H.; Moggi, N.; Moon, C. S.; Moore, R.; Morello, M. J.; Morlok, J.; Movilla Fernández, Pedro A.; Mülmenstädt, J.; Mukherjee, A.; Muller, T.; Mumford, R.; Murat, P.; Mussini, M.; Nachtman, J.; Nagai, Y.; Nagano, A.; Naganoma, J.; Nakamura, K.; Nakano, I.; Napier, A.; Necula, V.; Neu, C.; Neubauer, M. S.; Nielsen, J.; Nodulman, L.; Norman, M.; Norniella, O.; Nurse, E.; Oakes, L.; Oh, S. H.; Oh, Y. D.; Oksuzian, I.; Okusawa, T.; Orava, R.; Osterberg, K.; Pagan Griso, S.; Pagliarone, C.; Palencia, E.; Papadimitriou, Vaia; Papaikonomou, A.; Paramonov, A. A.; Parks, B.; Pashapour, S.; Patrick, J.; Pauletta, G.; Paulini, M.; Paus, C.; Pellett, D. E.; Penzo, A.; Phillips, T. J.; Piacentino, G.; Pianori, E.; Pinera, L.; Pitts, K.; Plager, C.; Pondrom, L.; Poukhov, O.; Pounder, N.; Prakoshyn, F.; Pronko, A.; Proudfoot, J.; Ptohos, Fotios; Pueschel, E.; Punzi, G.; Pursley, J.; Rademacker, J.; Rahaman, A.; Ramakrishnan, V.; Ranjan, N.; Redondo, I.; Reisert, B.; Rekovic, V.; Renton, P.; Rescigno, M.; Richter, S.; Rimondi, F.; Ristori, L.; Robson, A.; Rodrigo, T.; Rodriguez, T.; Rogers, E.; Rolli, S.; Roser, R.; Rossi, M.; Rossin, R.; Roy, P.; Ruiz, A.; Russ, J.; Rusu, V.; Saarikko, H.; Safonov, A.; Sakumoto, W. K.; Saltó, O.; Santi, L.; Sarkar, S.; Sartori, L.; Sato, K.; Savoy-Navarro, A.; Scheidle, T.; Schlabach, P.; Schmidt, A.; Schmidt, E. E.; Schmidt, M. A.; Schmidt, M. P.; Schmitt, M.; Schwarz, T.; Scodellaro, L.; Scott, A. L.; Scribano, A.; Scuri, F.; Sedov, A.; Seidel, S.; Seiya, Y.; Semenov, A.; Sexton-Kennedy, L.; Sfyrla, A.; Shalhout, S. Z.; Shears, T.; Shekhar, R.; Shepard, P. F.; Sherman, D.; Shimojima, M.; Shiraishi, S.; Shochet, M.; Shon, Y.; Shreyber, I.; Sidoti, A.; Sinervo, P.; Sisakyan, A.; Slaughter, A. J.; Slaunwhite, J.; Sliwa, K.; Smith, J. R.; Snider, F. D.; Snihur, R.; Soha, A.; Somalwar, S.; Sorin, V.; Spalding, J.; Spreitzer, T.; Squillacioti, P.; Stanitzki, M.; St.denis, R.; Stelzer, B.; Stelzer-Chilton, O.; Stentz, D.; Strologas, John; Stuart, D.; Suh, J. S.; Sukhanov, A.; Suslov, I.; Suzuki, T.; Taffard, A.; Takashima, R.; Takeuchi, Y.; Tanaka, R.; Tecchio, M.; Teng, P. K.; Terashi, K.; Thom, J.; Thompson, A. S.; Thompson, G. A.; Thomson, E.; Tipton, P.; Tiwari, V.; Tkaczyk, S.; Toback, D.; Tokar, S.; Tollefson, K.; Tomura, T.; Tonelli, D.; Torre, S.; Torretta, D.; Totaro, P.; Tourneur, S.; Tu, Y.; Turini, N.; Ukegawa, F.; Vallecorsa, S.; Van Remortel, Nick; Varganov, A.; Vataga, E.; Vázquez, F.; Velev, G.; Vellidis, C.; Veszprémi, V.; Vidal, M.; Vidal, R.; Vila, I.; Vilar, R.; Vine, T.; Vogel, M.; Volobouev, I.; Volpi, G.; Würthwein, F.; Wagner, P.; Wagner, R. G.; Wagner, R. L.; Wagner-Kuhr, J.; Wagner, W.; Wakisaka, T.; Wallny, R.; Wang, S. M.; Warburton, A.; Waters, D.; Weinberger, M.; Wester, W. C.; Whitehouse, B.; Whiteson, D.; Whiteson, S.; Wicklund, A. B.; Wicklund, E.; Williams, G.; Williams, H. H.; Wilson, P.; Winer, B. L.; Wittich, P.; Wolbers, S.; Wolfe, C.; Wright, T.; Wu, X.; Wynne, S. M.; Xie, S.; Yagil, A.; Yamamoto, K.; Yamaoka, J.; Yang, U. K.; Yang, Y. C.; Yao, W. M.; Yeh, G. P.; Yoh, J.; Yorita, K.; Yoshida, T.; Yu, G. B.; Yu, I.; Yu, S. S.; Yun, J. C.; Zanello, L.; Zanetti, A.; Zaw, I.; Zhang, X.; Zheng, Y.; Zucchelli, S. (2009)We report a measurement of the top-quark mass Mt in the dilepton decay channel tt̄→bl′+νl′b̄l-ν̄l. Events are selected with a neural network which has been directly optimized for statistical precision in top-quark mass ...