Gibbs classifiers
Author:
B. A. Zalesky
Translated by:
The author
Original publication:
Teoriya Imovirnostei ta Matematichna Statistika, tom 70 (2004).
Journal:
Theor. Probability and Math. Statist. 70 (2005), 4151
MSC (2000):
Primary 60G60, 62H30; Secondary 90C27
Published electronically:
August 5, 2005
MathSciNet review:
2109821
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: New statistical classifiers for dependent observations with Gibbs prior distributions of the exponential or Gaussian type are presented. It is assumed that the observations are characterized by feature functions that assume values in finite sets of rational numbers. The distributions of observations are either Gibbs exponential or Gibbs Gaussian. Arbitrary neighborhoods on a completely connected graph are considered instead of local neighborhoods of the nearest observation. The models studied in this paper can be used for some problems of the classification of random fields, in statistical physics, and for image processing. A method of finding an optimal Bayes decision rule is described. The method is based on the reduction of the problem to the evaluation of the minimal cut of an appropriate graph. The method can be used for the fast evaluation of optimal Bayes decision rules for large samples.
 1.
S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intel. PAMI6 6 (1984), 721741.
 2.
Basilis
Gidas, Metropolistype Monte Carlo simulation algorithms and
simulated annealing, Topics in contemporary probability and its
applications, Probab. Stochastics Ser., CRC, Boca Raton, FL, 1995,
pp. 159–232. MR 1410538
(98b:60128)
 3.
B.
A. Zalesky, Stochastic relaxation for building some classes of
piecewise linear regression functions, Monte Carlo Methods Appl.
6 (2000), no. 2, 141–157. MR
1773375, http://dx.doi.org/10.1515/mcma.2000.6.2.141
 4.
D. M. Greig, B. T. Porteous, and A. H. Seheult, Exact maximum a posteriori estimation for binary images, J. R. Statist. Soc. B. 58 (1989), 271279.
 5.
Yu. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Trans. Pattern Anal. Machine Intel. 23 (2001), no. 11, 12221239.
 6.
V. Kolmogorov and R. Zabih, What Energy Functions Can Be Minimized Via Graph Cuts?, Cornell CS Technical Report, TR20011857 (2001).
 7.
B. A. Zalesky, Computation of Gibbs estimates of grayscale images by discrete optimization methods, Proceedings of the Sixth International Conference PRIP'2001 (Minsk, May 1820, 2001), pp. 8185.
 8.
B.
A. Zalesskiĭ, Efficient minimization of quadratic
polynomials in integer variables with quadratic monomials
𝑏_{𝑖,𝑗}²(𝑥ᵢ𝑥ⱼ)²,
Dokl. Nats. Akad. Nauk Belarusi 45 (2001), no. 6,
9–11, 134 (Russian, with English and Russian summaries). MR 1984687
(2003m:90073)
 9.
B. A. Zalesky, Network Flow Optimization for Restoration of Images, Preprint AMS, Mathematics ArXiv, math.OC/0106180.
 10.
S. A. Aivazyan, B. M. Bukhshtaber, I. S. Enyukov, and L. D. Meshalkin, Applied Statistics: Classification and Dimensionality Reduction, ``Finansy i statistika'', Moscow, 1989. (Russian)
 11.
Geoffrey
J. McLachlan, Discriminant analysis and statistical pattern
recognition, Wiley Series in Probability and Mathematical Statistics:
Applied Probability and Statistics, John Wiley & Sons Inc., New York,
1992. A WileyInterscience Publication. MR 1190469
(94a:62091)
 12.
V.
V. Mottl′ and I.
B. Muchnik, Skrytye markovskie modeli v strukturnom analize
signalov, FizikoMatematicheskaya Literatura, Moscow, 1999 (Russian,
with Russian summary). MR 1778152
(2001m:94014)
 13.
E. E. Zhuk and Yu. S. Kharin, Stability in the Cluster Analysis of Multivariate Data, Belgosuniversitet, Minsk, 1998. (Russian)
 14.
B. V. Cherkassky and A. V. Goldberg, On Implementing PushRelabel Method for the Maximum Flow Problem, Technical Report STANCS941523, Department of Computer Science, Stanford University, 1994.
 15.
J.
C. Picard and H.
D. Ratliff, Minimum cuts and related problems, Networks
5 (1975), no. 4, 357–370. MR 0391960
(52 #12778)
 1.
 S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intel. PAMI6 6 (1984), 721741.
 2.
 B. Gidas, Metropolis Type Monte Carlo Simulation Algorithm and Simulated Annealing, Topics in Contemp. Probab. Appl., Stochastics Ser., CRC, Boca Raton, Fl, 1995. MR 1410538 (98b:60128)
 3.
 B. A. Zalesky, Sthochastic relaxation for buildind some classes of piecewise linear regression functions, MonteCarlo Meth. Appl. 6 (2000), no. 2, 141157. MR 1773375
 4.
 D. M. Greig, B. T. Porteous, and A. H. Seheult, Exact maximum a posteriori estimation for binary images, J. R. Statist. Soc. B. 58 (1989), 271279.
 5.
 Yu. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Trans. Pattern Anal. Machine Intel. 23 (2001), no. 11, 12221239.
 6.
 V. Kolmogorov and R. Zabih, What Energy Functions Can Be Minimized Via Graph Cuts?, Cornell CS Technical Report, TR20011857 (2001).
 7.
 B. A. Zalesky, Computation of Gibbs estimates of grayscale images by discrete optimization methods, Proceedings of the Sixth International Conference PRIP'2001 (Minsk, May 1820, 2001), pp. 8185.
 8.
 B. A. Zalesski, Efficient minimization of quadratic polynomials in integer variables with quadratic monomials , Dokl. Nats. Akad. Nauk Belarusi 45 (2001), no. 6, 911. (Russian) MR 1984687 (2003m:90073)
 9.
 B. A. Zalesky, Network Flow Optimization for Restoration of Images, Preprint AMS, Mathematics ArXiv, math.OC/0106180.
 10.
 S. A. Aivazyan, B. M. Bukhshtaber, I. S. Enyukov, and L. D. Meshalkin, Applied Statistics: Classification and Dimensionality Reduction, ``Finansy i statistika'', Moscow, 1989. (Russian)
 11.
 G. J. McLachlan, Discriminant Analysis and Statistical Pattern Recognition, John Wiley, New York, 1992. MR 1190469 (94a:62091)
 12.
 V. V. Mottl' and I. B. Muchnik, Hidden Markov Models in Structural Analysis of Signals, Fizmatlit, Moscow, 1999. (Russian) MR 1778152 (2001m:94014)
 13.
 E. E. Zhuk and Yu. S. Kharin, Stability in the Cluster Analysis of Multivariate Data, Belgosuniversitet, Minsk, 1998. (Russian)
 14.
 B. V. Cherkassky and A. V. Goldberg, On Implementing PushRelabel Method for the Maximum Flow Problem, Technical Report STANCS941523, Department of Computer Science, Stanford University, 1994.
 15.
 J. C. Picard and H. D. Ratliff, Minimal cuts and related problems, Networks 5 (1975), 357370. MR 0391960 (52:12778)
Similar Articles
Retrieve articles in Theory of Probability and Mathematical Statistics
with MSC (2000):
60G60,
62H30,
90C27
Retrieve articles in all journals
with MSC (2000):
60G60,
62H30,
90C27
Additional Information
B. A. Zalesky
Affiliation:
Joint Institute of Problems in Informatics, National Academy of Sciences, Surganov Street 6, Minsk 220012, Belarus
Email:
zalesky@newman.basnet.by
DOI:
http://dx.doi.org/10.1090/S0094900005006290
PII:
S 00949000(05)006290
Received by editor(s):
April 4, 2002
Published electronically:
August 5, 2005
Additional Notes:
Supported by a grant of MNTC B–517.
Article copyright:
© Copyright 2005 American Mathematical Society
