13992541
Enhancing relevance scoring with chronological term rank
We introduce a new relevance scoring technique that enhances existing relevance scoring schemes with term position information. This technique uses chronological term rank (CTR) which captures the positions of terms as they occur in the sequence of words in a document. CTR is both conceptually and computationally simple when compared to other approaches that use document structure information, such as term proximity, term order and document features. CTR works well when paired with Okapi BM25. We evaluate the performance of various combinations of CTR with Okapi BM25 in order to identify the most effective formula. We then compare the performance of the selected approach against the performance of existing methods such as Okapi BM25, pivoted length normalization and language models. Significant improvements are seen consistently across a variety of TREC data and topic sets, measured by the major retrieval performance metrics. This seems to be the first use of this statistic for relevance scoring. There is likely to be greater retrieval improvements possible using chronological term rank enhanced methods in future work.
717123
Experimenting with Power Default Reasoning
In this paper we explore the computational aspects of Propositional Power Default Reasoning (PDR), a form of non-monotonic reasoning in which the underlying logic is Kleene's 3-valued propositional logic. PDR leads to a concise meaning of the problem of skeptical entailment which has better complexity characteristics than the usual formalisms (co-NP(3)-Complete instead of ?2P-Complete). We take advantage of this in an implementation called powdef to encode and solve hard graph problems and explore randomly generated instances of skeptical entailment.
14387948
Axiomatic Aspects of Default Inference
This paper studies axioms for nonmonotonic consequences from a semantics-based point of view, focusing on a class of mathematical structures for reasoning about partial information without a predefined syntax/logic. This structure is called a default structure. We study axioms for the nonmonotonic consequence relation derived from extensions as in Reiter's default logic, using skeptical reasoning, but extensions are now used for the construction of possible worlds in a default information structure. 
In previous work we showed that skeptical reasoning arising from default-extensions obeys a well-behaved set of axioms including the axiom of cautious cut. We show here that, remarkably, the converse is also true: any consequence relation obeying this set of axioms can be represented as one constructed from skeptical reasoning. We provide representation theorems to relate axioms for nonmonotonic consequence relation and properties about extensions, and provide one-to-one correspondence between nonmonotonic systems which satisfies the law of cautious monotony and default structures with unique extensions. Our results give a theoretical justification for a set of basic rules governing the update of nonmonotonic knowledge bases, demonstrating the derivation of them from the more concrete and primitive construction of extensions. It is also striking to note that proofs of the representation theorems show that only shallow extensions are necessary, in the sense that the number of iterations needed to achieve an extension is at most three. All of these developments are made possible by taking a more liberal view of consistency: consistency is a user defined predicate, satisfying some basic properties.
12232435
Rational Transformations of Formal Power Series
Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve rationality, generalizing the recent results of Zhang [15] to the formal power series setting. We show, for example, that the "square-root" operation, while preserving regularity for formal languages, preserves rationality for formal power series when the underlying semiring is commutative or locally finite, but not in general.
1726106
Defaults in Domain Theory
Abstract This paper uses ideas from artificial intelligence to show how default notions can be defined over Scott domains. We combine these ideas with ideas arising in domain theory to shed some light on the properties of nonmonotonicity in a general model-theoretic setting. We consider in particular a notion of default nonmonotonic entailment between prime open sets in the Scott topology of a domain. We investigate in what ways this notion obeys the so-called laws of cautious monotony and cautious cut , proposed by Gabbay, Kraus, Lehmann, and Magidor. Our notion of nonmonotonic entailment does not necessarily satisfy cautious monotony, but does satisfy cautious cut. In fact, we show that any reasonable notion of nonmonotonic entailment on prime opens over a Scott domain, satisfying in particular the law of cautious cut, can be concretely represented using our notion of default entailment. We also give a variety of sufficient conditions for defaults to induce cumulative entailments, those satisfying cautious monotony. In particular, we show that defaults with unique extensions are a representation of cumulative nonmonotonic entailment. Furthermore, a simple characterization is given for those default sets which determine unique extensions in coherent domains. Finally, a characterization is given for Scott domains in which default entailment must be cumulative. This is the class of daisy domains ; it is shown to be cartesian closed, a purely domain-theoretic result.
10438151
Complexity of power default reasoning
This paper derives a new and surprisingly low complexity result for inference in a new form of Reiter's propositional default logic (1980). The problem studied here is the default inference problem whose fundamental importance was pointed out by Kraus, Lehmann, and Magidor (1980). We prove that "normal" default inference, in propositional logic, is a problem complete for co-NP(3), the third level of the Boolean hierarchy. Our result (by changing the underlying semantics) contrasts favorably with a similar result of Gottlob (1992), who proves that standard default inference is II/sub 2//sup P/-complete. Our inference relation also obeys all of the laws for preferential consequence relations set forth by Kraus, Lehmann, and Magidor (1990). In particular we get the property of being able to reason by cases and the law of cautious monotony. Both of these laws fail for standard propositional default logic. The key technique for our results is the use of Scott's domain theory to integrate defaults into partial model theory of the logic, instead of keeping defaults as quasiproof rules in the syntax. In particular, reasoning disjunctively entails using the Smyth powerdomain.
38503566
Pseudo-one-factorizations of regular graphs of odd order - II. products of graphs
Abstract We study the pseudo-one-factorization of regular graphs of odd order. It is shown that some classes of products (including composition and cartesian product) of graphs are pseudo-one- factorizable. In particular, we prove that a complete regular t -partite graph of odd order has this property.
7172030
Information-theoretic inequalities for contoured probability distributions
We show that for a special class of probability distributions that we call contoured distributions, information-theoretic invariants and inequalities are equivalent to geometric invariants and inequalities of bodies in Euclidean space associated with the distributions. Using this, we obtain characterizations of contoured distributions with extremal Shannon and Renyi entropy. We also obtain a new reverse information-theoretic inequality for contoured distributions.
7914535
Stereoscopic Video Synthesis from a Monocular Video
This paper presents an automatic and robust approach to synthesize stereoscopic videos from ordinary monocular videos acquired by commodity video cameras. Instead of recovering the depth map, the proposed method synthesizes the binocular parallax in stereoscopic video directly from the motion parallax in monocular video, The synthesis is formulated as an optimization problem via introducing a cost function of the stereoscopic effects, the similarity, and the smoothness constraints. The optimization selects the most suitable frames in the input video for generating the stereoscopic video frames. With the optimized selection, convincing and smooth stereoscopic video can be synthesized even by simple constant-depth warping. No user interaction is required. We demonstrate the visually plausible results obtained given the input clips acquired by ordinary handheld video camera.
41994930
On the partition and coloring of a graph by cliques
Abstract We first introduce the concept of the k -chromatic index of a graph, and then discuss some of its properties. A characterization of the clique partition number of the graph G ⋁ K c m for any simple graph G is given, together with some of its applications. Graphs with maximum valency 3 are also considered.
13849872
As-consistent-As-possible compositing of virtual objects and video sequences
We present an efficient approach that merges the virtual objects into video sequences taken by a freely moving camera in a realistic manner. The composition is visually and geometrically consistent through three main steps. First, a robust camera tracking algorithm based on key frames is proposed, which precisely recovers the focal length with a novel multi-frame strategy. Next, the concerned 3D models of the real scenes are reconstructed by means of an extended multi-baseline algorithm. Finally, the virtual objects in the form of 3D models are integrated into the real scenes, with special cares on the interaction consistency including shadow casting, occlusions, and object animation. A variety of experiments have been implemented, which demonstrate the robustness and efficiency of our approach. Copyright © 2006 John Wiley & Sons, Ltd.