CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Finding Most Likely Solutions

Mikael Onsjö (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Osamu Watanabe
Proc. CiE 2007: Computability in Europe (1611-3349). Vol. 4497 (2007), p. 758-767.
[Konferensbidrag, refereegranskat]

As a framewrok for simple but basic statistical inference problems we introduce a genetic Most Likely Solution problem, a task of finding a most likely solution (MLS in short) for a given problem instance under some given probability model. Although many MLS problems are NP-hard, we propose, for these problems, to study their average-case complexity under their assumed probability models. We show three examples of MLS problems, and explain that “message passing algorithms” (e.g., belief propagation) work reasonably well for these problems. Some of the technical results of this paper are from the author’s recent work [WY06, OW06].



Denna post skapades 2008-02-20.
CPL Pubid: 68391

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)

Ämnesområden

Datalogi

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Graph Partitioning and Planted Partitions