A Bayes-true data generator for evaluation of supervised and unsupervised learning methods

Benchmarking pattern recognition, machine learning and data mining methods commonly relies on real-world data sets. However, there are some disadvantages in using real-world data. On one hand collecting real-world data can become difficult or impossible for various reasons, on the other hand real-world variables are hard to control, even in the problem domain; in the feature domain, where most statistical learning methods operate, exercising control is even more difficult and hence rarely attempted. This is at odds with the scientific experimentation guidelines mandating the use of as directly controllable and as directly observable variables as possible. Because of this, synthetic data possesses certain advantages over real-world data sets. In this paper we propose a method that produces synthetic data with guaranteed global and class-specific statistical properties. This method is based on overlapping class densities placed on the corners of a regular k-simplex. This generator can be used for algorithm testing and fair performance evaluation of statistical learning methods. Because of the strong properties of this generator researchers can reproduce each others experiments by knowing the parameters used, instead of transmitting large data sets.     

Making Logical Inferences in Inconsistent Systems

A new basis for making logical inference in inconsistent systems is considered. Main inference rules and the completeness theorem (in narrow sense) of the calculus proposed are proved. The approach proposed can underlie the creation of systems of substantiation of inconsistent and unreliable solutions obtained, for instance, in designing intelligent robots and expert systems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 29–41, September–October 2005.     

Searching for circles of pure proofs

When given a set of properties or conditions (say, three) that are claimed to be equivalent, the claim can be verified by supplying what we call acircle of proofs. In the case in point, one proves the second property or condition from the first, the third from the second, and the first from the third. If the proof that 1 implies 2 does not rely on 3, then we say that the proof is pure with respect to 3, or simply say theproof is pure. If one can renumber the three properties or conditions in such a way that one can find a circle of three pure proofs — technically, each proof pure with respect to the condition that is neither the hypothesis nor the conclusion — then we say that acircle of pure proofs has been found. Here we study the specific question of the existence of a circle of pure proofs for the thirteen shortest single axioms for equivalential calculus, subject to the requirement that condensed detachment be used as the rule of inference. For an indication of the difficulty of answering the question, we note that a single application of condensed detachment to the (shortest single) axiom known asP4 (also known asUM) with itself yields the (shortest single) axiomP5 (also known asXGF), and two applications of condensed detachment beginning withP5 as hypothesis yieldsP4. Therefore, except forP5, one cannot find a pure proof of any of the twelve shortest single axioms when usingP4 as hypothesis or axiom, for the first application of condensed detachment must focus on two copies ofP4, which results in the deduction ofP5, forcingP5 to be present in all proofs that useP4 as the only axiom. Further, the close proximity in the proof sense ofP4 when using as the only axiomP5 threatens to make impossible the discovery of a circle of pure proofs for the entire set of thirteen shortest single axioms. Perhaps more important than our study of pure proofs, and of a more general nature, we also present the methodology used to answer the cited specific question, a methodology that relies on various strategies and features offered by W. McCune's automated reasoning programOtter. The strategies and features ofOtter we discuss here offer researchers the needed power to answer deep questions and solve difficult problems. We close this article (in the last two sections) with some challenges and some topics for research and (in the Appendix) with a sample input file and some proofs for study.Author supported by the Mathematical, Information, and Computational Sciences Division, Subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

现代密码学基本思想及其展望

本文简要综述了现代密码学的基本思想,提出了密码学研究的一些新方向,介绍了Shannon的度量密码系统安全性的指标,给出了构造公钥密码的一般步骤,讨论了分组密码的新进展,对零知识证明也作了一些探讨。     

A Legacy Recalled and a Tradition Continued

Since the first presentation of classical sentential logic as an axiomatic system by Frege in 1879, the study of a variety of sentential calculi has flourished. One major area of investigation, initiated by ukasiewicz and his colleagues in the first half of the twentieth century and carried into the second half by Meredith, Thomas, Prior, et al., focuses on alternative axiom sets for such logics, and on formal proofs within them. This paper recalls a sampling of the results obtained heretofore, noting along the way how the papers in this special issue of the Journal of Automated Reasoning fit into that larger tradition of which they now form a part. It also suggests a number of further questions, open problems, and projects to which the methods developed in these papers seem ideally suited and might well be fruitfully applied.     

Partiality and Nondeterminacy in Program Proofs

Specifications and programs make much use of nondeterministic and/or partial expressions, i.e. expressions which may yield several or no outcomes for some values of their free variables. Traditional 2-valued logics do not comfortably accommodate reasoning about undefined expressions, and do not cater at all for nondeterministic expressions. We seek to rectify this with a 4-valued typed logic E4 which classifies formulae as either “true”, “false”, “neither true nor false”, or “possibly true, possibly false”. The logic is derived in part from the 2-valued logic E and the 3-valued LPF, and preserves most of the theorems of E. Indeed, the main result is that nondeterminacy can be added to a logic covering partiality at little cost. Received July 1996 / Accepted in revised form April 1998     

Testing Positiveness of Polynomials

Many problems in mathematics, logic, computer science, and engineering can be reduced to the problem of testing positiveness of polynomials (over real numbers). Although the problem is decidable (shown by Tarski in 1930), the general decision methods are not always practically applicable because of their high computational time requirements. Thus several partial methods were proposed in the field of term rewriting systems. In this paper, we exactly determine how partial these methods are, and we propose simpler and/or more efficient methods with the same power.     

On the Power of Quantum,One Round,Two Prover Interactive Proof Systems

We analyze quantum two prover one round interactive proof systems, in which noninteracting provers can share unlimited entanglement. The maximum acceptance probability is characterized as a superoperator norm. We get some partial results and in particular we analyze the “rank one” case.      

A new ring signature scheme with signer-admission property

In this paper, we introduce an extended ring signature scheme in which the actual signer has the ability to admit to having signed a document at his will. Generally speaking, this scheme can be considered as an extension and improvement of the ring signature suggested by Rivest et al. in 2001. The proposed scheme is called signer-admission ring signature which combines the idea of the designated confirmer signatures proposed by Chaum in 1994 and the designated verifier proofs proposed by Jakobsson et al. in 1996. This paper presents a scenario explaining why the signer-admission property is valuable in real-life applications. An actual signer may possibly want to expose himself if, in doing so, he will acquire an enormous benefit. Here, we propose a generic construction of the signer-admission ring signature as well as a demonstration modified from Rivest et al.’s scheme to achieve signer-admission.     

A compositional natural semantics and Hoare logic for low-level languages

The advent of proof-carrying code has generated significant interest in reasoning about low-level languages. It is widely believed that low-level languages with jumps must be difficult to reason about because of being inherently non-modular. We argue that this is untrue. We take it seriously that, unlike statements of a high-level language, pieces of low-level code are multiple-entry and multiple-exit. And we define a piece of code as consisting of either a single labelled instruction or a finite union of pieces of code. Thus we obtain a compositional natural semantics and a matching Hoare logic for a basic low-level language with jumps. By their simplicity and intuitiveness, these are comparable to the standard natural semantics and Hoare logic of While. The Hoare logic is sound and complete wrt the semantics and allows for compilation of proofs of the Hoare logic of While.