Många verkliga beslutsfattande uppgifter kräver att vi väljer bland flera dyra observationer. I ett sensornätverk är det till exempel viktigt att välja den undergrupp av sensorer som förväntas ge den starkaste minskningen av osäkerheten. I medicinska beslutsfattande uppgifter, måste man välja vilka tester att administrera innan man beslutar om den mest effektiva behandlingen. Det har varit allmän praxis att använda heuristiska-styrda procedurer för att välja observationer. I den här artikeln presenterar vi de första effektiva optimala algoritmerna för att välja observationer för en klass av probabilistiska grafiska modeller. Till exempel gör våra algoritmer det möjligt att optimalt märka dolda variabler i dolda Markov-modeller (HMM). Vi ger resultat både för att välja den optimala undergruppen av observationer och för att få en optimal villkorlig observationsplan. Dessutom visar vi ett överraskande resultat: I de flesta grafiska modeller uppgifter, om man designar en effektiv algoritm för kedja grafer, såsom HMMs, detta förfarande kan generaliseras till polytree grafiska modeller. Vi bevisar att optimera värdet av information är NP PP - hård även för polytrees. Det följer också av våra resultat att bara computing beslut teoretiskt värde av information objektiva funktioner, som ofta används i praktiken, är ett #P-komplett problem även på Naive Bayes modeller (ett enkelt specialfall av polytrees). Dessutom överväger vi flera tillägg, till exempel att använda våra algoritmer för schemaläggning av observationsval för flera sensorer. Vi demonstrerar effektiviteten i vår strategi för flera verkliga dataset, inklusive en prototyp sensor nätverk utbyggnad för energibesparing i byggnader.
Krause m.fl. REF presenterar optimala algoritmer för beräkning och optimerar värdet av information om en kedja grafiska modeller.
Optimal Value of Information in Graphical Models
{'venue': 'Journal Of Artificial Intelligence Research, Volume 35, pages 557-591, 2009', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}