Weighted Programming
We study weighted programming, a programming paradigm for specifying mathematical models. More specifically, the weighted programs we investigate are like usual imperative programs with two additional features: (1) nondeterministic branching and (2) weighting execution traces. Weights can be numbers but also other objects like words from an alphabet, polynomials, formal power series, or cardinal numbers. We argue that weighted programming as a paradigm can be used to specify mathematical models beyond probability distributions (as is done in probabilistic programming). We develop weakest-precondition- and weakest-liberal-precondition-style calculi \`{a} la Dijkstra for reasoning about mathematical models specified by weighted programs. We present several case studies. For instance, we use weighted programming to model the ski rental problem - an optimization problem. We model not only the optimization problem itself, but also the best deterministic online algorithm for solving this problem as weighted programs. By means of weakest-precondition-style reasoning, we can determine the competitive ratio of the online algorithm on source code level.
Code (0)
등록된 구현이 없습니다.
Tasks
Probabilistic ProgrammingSimilar Papers 제목 키워드 기반
DPMC: Weighted Model Counting by Dynamic Programming on Project-Join Trees
We propose a unifying dynamic-programming framework to compute exact literal-weighted model counts of formulas in conjunctive normal form. At the center of our framework are project-join trees, which specify efficient pr…
Tree DecompositionLinear programming analysis of loopy belief propagation for weighted matching
Loopy belief propagation has been employed in a wide variety of applications with great empirical success, but it comes with few theoretical guarantees. In this paper we investigate the use of the max-product form of bel…
ASP(AC): Answer Set Programming with Algebraic Constraints
Weighted Logic is a powerful tool for the specification of calculations over semirings that depend on qualitative information. Using a novel combination of Weighted Logic and Here-and-There (HT) Logic, in which this depe…
Weighted parsing for grammar-based language models
We develop a general framework for weighted parsing which is built on top of grammar-based language models and employs flexible weight algebras. It generalizes previous work in that area (semiring parsing, weighted deduc…
Weighted second-order cone programming twin support vector machine for imbalanced data classification
We propose a method of using a Weighted second-order cone programming twin support vector machine (WSOCP-TWSVM) for imbalanced data classification. This method constructs a graph based under-sampling method which is util…
General Classification