Programkänslighet, även känd som Lipschitz kontinuitet, beskriver hur små förändringar i ett programs ingång leder till avgränsade förändringar i utdata. Vi föreslår en genomsnittlig begrepp av programkänslighet för probabilistiska program — förväntade känslighet — att genomsnitt en distans funktion över en probabilistisk koppling av två output distributioner från två liknande ingångar. Genom att variera avståndet återvinner den förväntade känsligheten användbara föreställningar om probabilistisk funktionskänslighet, inklusive stabilitet i maskininlärningsalgoritmer och konvergens av Markovkedjor. Dessutom uppfyller den förväntade känsligheten rena sammansättningsegenskaper och kan användas för formell kontroll. Vi utvecklar en relationell programlogik som kallas EpRHL för att bevisa förväntade känslighetsegenskaper. Vår logik innehåller två huvudidéer. För det första uttrycks relationsförutsättningar och postvillkor med hjälp av avstånd, en verkligt värderad generalisering av typiska booleanska-värderade (relationella) påståenden. För det andra tolkas domarna i termer av förväntningskoppling, en ny kvantitativ generalisering av probabilistiska kopplingar som stöder kompositionstänkande. Vi visar vår logik på exempel som är utom räckhåll för tidigare relationslogik. Vårt huvudexempel formaliserar den stokastiska lutningsmetodens enhetliga stabilitet. Dessutom visar vi oss hastig blandning för en probabilistisk modell av befolkningsdynamik. Vi utökar också vår logik med en transitivitetsprincip för förväntan kopplingar för att fånga vägen koppling bevis teknik av Bubley och Dyer [1997], och formalisera snabb blandning av Glauber dynamik från statistisk fysik.
REF identifierade tåglägesmått som ett användbart koncept för formell verifiering, i samband med spårkopplingssäker teknik.
Proving expected sensitivity of probabilistic programs
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}