About: The Power of LP Relaxation for MAP Inference

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: The Power of LP Relaxation for MAP Inference Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	ftp://cmp.felk.cvut.cz/pub/cmp/articles/werner/ZivWerPru-LP-MIT2014.pdf
Description	Minimization of a partially separable function of many discrete variables is ubiquitous in machine learning and computer vision, in tasks like maximum a posteriori (MAP) inference in graphical models, or structured prediction. Among successful approaches to this problem is linear programming (LP) relaxation. We discuss this LP relaxation from two aspects. First, we review recent results which characterize languages (classes of functions permitted to form the objective function) for which the problem is solved by the relaxation exactly. Second, we show that solving the LP relaxation is not easier than solving any linear program, which makes a discovery of an efficient algorithm for the LP relaxation unlikely. Minimization of a partially separable function of many discrete variables is ubiquitous in machine learning and computer vision, in tasks like maximum a posteriori (MAP) inference in graphical models, or structured prediction. Among successful approaches to this problem is linear programming (LP) relaxation. We discuss this LP relaxation from two aspects. First, we review recent results which characterize languages (classes of functions permitted to form the objective function) for which the problem is solved by the relaxation exactly. Second, we show that solving the LP relaxation is not easier than solving any linear program, which makes a discovery of an efficient algorithm for the LP relaxation unlikely. (en)
Title	The Power of LP Relaxation for MAP Inference The Power of LP Relaxation for MAP Inference (en)
skos:prefLabel	The Power of LP Relaxation for MAP Inference The Power of LP Relaxation for MAP Inference (en)
skos:notation	RIV/68407700:21230/14:00223600!RIV15-MSM-21230___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(7E10047), P(7E11036), P(GAP202/12/2071)
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Průša, Daniel Werner, Tomáš
http://linked.open.../riv/druhVysledku	C - Kapitola v knize
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	České vysoké učení technické v Praze / Fakulta elektrotechnická
http://linked.open...dnocenehoVysledku	38289
http://linked.open...ai/riv/idVysledku	RIV/68407700:21230/14:00223600
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	graphical model; Markov random field; discrete energy minimization; valued constraint satisfaction; linear programming relaxation (en)
http://linked.open.../riv/klicoveSlovo	linear programming relaxation Markov random field graphical model discrete energy minimization valued constraint satisfaction
http://linked.open...ontrolniKodProRIV	[19DBB84DEF2C]
http://linked.open...i/riv/mistoVydani	Boston
http://linked.open...i/riv/nazevZdroje	Advanced Structured Prediction
http://linked.open...in/vavai/riv/obor	JD
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...v/pocetStranKnihy	456 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Strukturované statistické modely pro porozumění obrazům Humanoids with auditory and visual abilities in populated spaces Dextrous Assembler Robot Working with embodied INtelligence
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Průša, Daniel Werner, Tomáš Živný, S.
number of pages	24 (xsd:int)
http://purl.org/ne...btex#hasPublisher	MIT PRESS
https://schema.org/isbn	978-0-262-02837-0
http://localhost/t...ganizacniJednotka	21230

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software