Proposition and learning of some belief function contextual correction mechanisms

Knowledge about the quality of a source can take several forms: it may for instance relate to its truthfulness or to its relevance, and may even be uncertain. Of particular interest in this paper is that such knowledge may also be contextual; for instance the reliability of a sensor may be known to depend on the actual object observed. Various tools, called correction mechanisms, have been developed within the theory of belief functions, to take into account knowledge about the quality of a source. Yet, only a single tool is available to account for contextual knowledge about the quality of a source, and precisely about the relevance of a source. There is thus some lack of flexibility since contextual knowledge about the quality of a source does not have to be restricted to its relevance. The first aim of this paper is thus to try and enlarge the set of tools available in belief function theory to deal with contextual knowledge about source quality. This aim is achieved by (1) providing an interpretation to each one of two contextual correction mechanisms introduced initially from purely formal considerations, and (2) deriving extensions – essentially by uncovering contextual forms – of two interesting and non-contextual correction mechanisms. The second aim of this paper is related to the origin of contextual knowledge about the quality of a source: due to the lack of dedicated approaches, it is indeed not clear how to obtain such specific knowledge in practice. A sound, easy to interpret and computationally simple method is therefore provided to learn from data contextual knowledge associated with the contextual correction mechanisms studied in this paper.     

Belief functions combination without the assumption of independence of the information sources

This paper considers the problem of combining belief functions obtained from not necessarily independent sources of information. It introduces two combination rules for the situation in which no assumption is made about the dependence of the information sources. These two rules are based on cautious combinations of plausibility and commonality functions, respectively. The paper studies the properties of these rules and their connection with Dempster’s rules of conditioning and combination and the minimum rule of possibility theory.     

Relevance and truthfulness in information correction and fusion

A general approach to information correction and fusion for belief functions is proposed, where not only may the information items be irrelevant, but sources may lie as well. We introduce a new correction scheme, which takes into account uncertain metaknowledge on the source’s relevance and truthfulness and that generalizes Shafer’s discounting operation. We then show how to reinterpret all connectives of Boolean logic in terms of source behavior assumptions with respect to relevance and truthfulness. We are led to generalize the unnormalized Dempster’s rule to all Boolean connectives, while taking into account the uncertainties pertaining to assumptions concerning the behavior of sources. Eventually, we further extend this approach to an even more general setting, where source behavior assumptions do not have to be restricted to relevance and truthfulness. We also establish the commutativity property between correction and fusion processes, when the behaviors of the sources are independent.     

Stanley decompositions and partitionable simplicial complexes

We study Stanley decompositions and show that Stanley’s conjecture on Stanley decompositions implies his conjecture on partitionable Cohen–Macaulay simplicial complexes. We also prove these conjectures for all Cohen–Macaulay monomial ideals of codimension 2 and all Gorenstein monomial ideals of codimension 3. Dedicated to Takayuki Hibi on the occasion of his fiftieth birthday.     

Claw‐decompositions and tutte‐orientations

We conjecture that, for each tree T, there exists a natural number k_T such that the following holds: If G is a k_T‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K_1,3 (the claw), this holds if and only if there exists a (smallest) natural number k_t such that every k_t‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k_t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006     

Active classification using belief functions and information gain maximization

Obtaining reliable estimates of the parameters of a probabilistic classification model is often a challenging problem because the amount of available training data is limited. In this paper, we present a classification approach based on belief functions that makes the uncertainty resulting from limited amounts of training data explicit and thereby improves classification performance. In addition, we model classification as an active information acquisition problem where features are sequentially selected by maximizing the expected information gain with respect to the current belief distribution, thus reducing uncertainty as quickly as possible. For this, we consider different measures of uncertainty for belief functions and provide efficient algorithms for computing them. As a result, only a small subset of features need to be extracted without negatively impacting the recognition rate. We evaluate our approach on an object recognition task where we compare different evidential and Bayesian methods for obtaining likelihoods from training data and we investigate the influence of different uncertainty measures on the feature selection process.     

Boolean algebras of lattice uniformities and decompositions of modular functions

We study decomposition theorems for modular functions on lattices and the relationship between such decompositions and lattice properties of a suitable system of uniformities. We give a purely topological characterization for the validity of a decomposition theorem of a certain type and examine when this topological condition is satisfied, namely when a system of lattice uniformities is a Boolean algebra consisting of permutable uniformities.      

HAMILTONIAN CYCLES AND DECOMPOSITIONS OFCAYLEY DIGRAPHS OF FINITE ABELIAN GROUPS

In this paper, Hamiltonian cycles and decompositions of Cayley digraphs are investigat-ed. Sufficient conditions are given for these two problems respectively. Furthermore, the conditions are also necesaary for 2-regular Cayley disraphs, In addition, some known results about theCartesian products of two directed cycles are also deduced.     

The Khavinson-Shapiro conjecture and polynomial decompositions

The main result of the paper states the following: Let ψ be a polynomial in n variables. Suppose that there exists a constant C>0 such that any polynomial f has a polynomial decomposition f=ψqf+hf with Δkhf=0 and . Then . Here Δk is the kth iterate of the Laplace operator Δ. As an application, new classes of domains in Rn are identified for which the Khavinson-Shapiro conjecture holds.     

Impact of discounting and competition on benefit of decentralization with strategic customers

With strategic customers, we find that a decentralized channel may have higher profit than that of a centralized channel. We show that in addition to the double marginalization effect, both customer and firm discounting and retailer competition are also driving factors of the higher decentralized channel profit.     

Surgery diagrams and open book decompositions of contact 3-manifolds

Summary We show an algorithmic way for finding a compatible open book decomposition on a contact 3-manifold given by contact (±1)-surgery.     

Designs with mutually orthogonal resolutions and decompositions of edge‐colored graphs

Two resolutions R and R^′ of a combinatorial design are called orthogonal if |R_i∩R|≤1 for all R_i∈R and R∈R^′. A set Q={R¹, R², …, R^d} of d resolutions of a combinatorial design is called a set of mutually orthogonal resolutions (MORs) if the resolutions of Q are pairwise orthogonal. In this paper, we establish necessary and sufficient conditions for the asymptotic existence of a (v, k, 1)‐BIBD with d mutually orthogonal resolutions for d≥2 and k≥3 and necessary and sufficient conditions for the asymptotic existence of a (v, k, k?1)‐BIBD with d mutually orthogonal near resolutions for d≥2 and k≥3. We use complementary designs and the most general form of an asymptotic existence theorem for decompositions of edge‐colored complete digraphs into prespecified edge‐colored subgraphs. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 425–447, 2009     

Telescoping partial fractions decompositions, the little q-Jacobi functions of complex order, and the nonterminating q-Saalschütz sum

We use telescoping partial fractions decompositions to give new proofs of the orthogonality property and the normalization relation for the little q-Jacobi polynomials, and the q-Saalschütz sum. In [20], we followed the development [19] of Schur functions for partitions with complex parts, and we showed that there exist natural little q-Jacobi functions of complex order which satisfy extensions of the orthogonality property and normalization relation of the little q-Jacobi polynomials, and that these two results follow from and together imply the nonterminating form of the q-Saalschütz sum. Writing the q-Pochhammer symbol of complex order as a ratio of infinite products in the usual way, we obtain new telescoping partial fractions decomposition proofs of our results [20] for the little q-Jacobi functions of complex order. We give several new proofs of the q-Saalschütz sum and its nonterminating form. For our friends Dick and Liz 2000 Mathematics Subject Classification Primary—42C05; Secondary—33C45, 33C47     

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V₁ and V₂ such that in G[V₁] every vertex has degree at most k, while G[V₂] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010     

The canonical order and optimization problems

Using the partial order technique, we describe a subclass of objective functions taking their optimum at the greedy point of a given feasible polyhedron inR ⁿ. Supported by the Belarusian Foundatmental Research Found     

On a non-standard class of entire functions

In this article we construct a class of entire functions of arbitrary finite order and with non-zero Taylor coefficients, which is not written in the form of Hadamard's canonical product. Some basic properties of this class are also given.     

Atomic decompositions for tensor products and polynomial spaces

We study the existence of atomic decompositions for tensor products of Banach spaces and spaces of homogeneous polynomials. If a Banach space X admits an atomic decomposition of a certain kind, we show that the symmetrized tensor product of the elements of the atomic decomposition provides an atomic decomposition for the symmetric tensor product , for any symmetric tensor norm μ. In addition, the reciprocal statement is investigated and analogous consequences for the full tensor product are obtained. Finally we apply the previous results to establish the existence of monomial atomic decompositions for certain ideals of polynomials on X.