Learning compact Markov logic networks with decision trees

Statistical-relational learning combines logical syntax with probabilistic methods. Markov Logic Networks (MLNs) are a prominent model class that generalizes both first-order logic and undirected graphical models (Markov networks). The qualitative component of an MLN is a set of clauses and the quantitative component is a set of clause weights. Generative MLNs model the joint distribution of relationships and attributes. A state-of-the-art structure learning method is the moralization approach: learn a set of directed Horn clauses, then convert them to conjunctions to obtain MLN clauses. The directed clauses are learned using Bayes net methods. The moralization approach takes advantage of the high-quality inference algorithms for MLNs and their ability to handle cyclic dependencies. A?weakness of moralization is that it leads to an unnecessarily large number of clauses. In this paper we show that using decision trees to represent conditional probabilities in the Bayes net is an effective remedy that leads to much more compact MLN structures. In experiments on benchmark datasets, the decision trees reduce the number of clauses in the moralized MLN by a factor of 5?C25, depending on the dataset. The accuracy of predictions is competitive with the models obtained by standard moralization, and in many cases superior.     

Modelling relational statistics with Bayes Nets

Class-level models capture relational statistics over object attributes and their connecting links, answering questions such as “what is the percentage of friendship pairs where both friends are women?” Class-level relationships are important in themselves, and they support applications like policy making, strategic planning, and query optimization. We represent class statistics using Parametrized Bayes Nets (PBNs), a first-order logic extension of Bayes nets. Queries about classes require a new semantics for PBNs, as the standard grounding semantics is only appropriate for answering queries about specific ground facts. We propose a novel random selection semantics for PBNs, which does not make reference to a ground model, and supports class-level queries. The parameters for this semantics can be learned using the recent pseudo-likelihood measure (Schulte in SIAM SDM, pp. 462–473, 2011) as the objective function. This objective function is maximized by taking the empirical frequencies in the relational data as the parameter settings. We render the computation of these empirical frequencies tractable in the presence of negated relations by the inverse Möbius transform. Evaluation of our method on four benchmark datasets shows that maximum pseudo-likelihood provides fast and accurate estimates at different sample sizes.     

WENO Scheme with Subcell Resolution for Computing Nonconservative Euler Equations with Applications to One-Dimensional Compressible Two-Medium Flows

High order path-conservative schemes have been developed for solving nonconservative hyperbolic systems in (Parés, SIAM J.?Numer. Anal. 44:300?C321, 2006; Castro et al., Math. Comput. 75:1103?C1134, 2006; J.?Sci. Comput. 39:67?C114, 2009). Recently, it has been observed in (Abgrall and Karni, J.?Comput. Phys. 229:2759?C2763, 2010) that this approach may have some computational issues and shortcomings. In this paper, a modification to the high order path-conservative scheme in (Castro et al., Math. Comput. 75:1103?C1134, 2006) is proposed to improve its computational performance and to overcome some of the shortcomings. This modification is based on the high order finite volume WENO scheme with subcell resolution and it uses an exact Riemann solver to catch the right paths at the discontinuities. An application to one-dimensional compressible two-medium flows of nonconservative or primitive Euler equations is carried out to show the effectiveness of this new approach.     

Better and Simpler Approximation Algorithms for?the?Stable Marriage Problem

We first consider the problem of finding a maximum size stable matching if incomplete lists and ties are both allowed, but ties are on one side only. For this problem we give a simple, linear time 3/2-approximation algorithm, improving on the best known approximation factor 5/3 of Irving and Manlove (J. Comb. Optim., doi:10.1007/s10878-007-9133-x, 2007). Next, we show how this extends to the Hospitals/Residents problem with the same ratio if the residents have strict orders. We also give a simple linear time algorithm for the general problem with approximation factor 5/3, improving the best known 15/8-approximation algorithm of Iwama, Miyazaki and Yamauchi (SODA ??07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.?288?C297, 2007). For the cases considered in this paper it is NP-hard to approximate within a factor of 21/19 by the result of Halldórsson et?al. (ACM Transactions on Algorithms 3(3):30, 2007). Our algorithms not only give better approximation ratios than the cited ones, but are much simpler and run significantly faster. Also we may drop a restriction used in (J. Comb. Optim., doi:10.1007/s10878-007-9133-x, 2007) and the analysis is substantially more moderate. Preliminary versions of this paper appeared in (Király, Egres Technical Report TR-2008-04, www.cs.elte.hu/egres/, 2008; Király in Proceedings of MATCH-UP 2008: Matching Under Preferences??Algorithms and Complexity, Satellite Workshop of ICALP, July 6, 2008, Reykjavík, Iceland, pp.?36?C45, 2008; Király in ESA 2008, Lecture Notes in Computer Science, vol.?5193, pp.?623?C634, 2008). For the related results obtained thenceforth see Sect.?5.     

Obtaining a Planar Graph by Vertex Deletion

In the?k-Apex problem the task is to find at most?k vertices whose deletion makes the given graph planar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of Robertson and Seymour (J.?Comb. Theory, Ser.?B 63(1):65–110, 1995; J.?Comb. Theory, Ser.?B 92(2):325–357, 2004), there is a cubic algorithm for every fixed value of?k. However, the proof is extremely complicated and the constants hidden by the big-O notation are huge. Here we give a much simpler algorithm for this problem with quadratic running time, by iteratively reducing the input graph and then applying techniques for graphs of bounded treewidth.     

Dual Norm Based Iterative Methods for Image Restoration

A convergent iterative regularization procedure based on the square of a dual norm is introduced for image restoration models with general (quadratic or non-quadratic) convex fidelity terms. Iterative regularization methods have been previously employed for image deblurring or denoising in the presence of Gaussian noise, which use L ² (Tadmor et?al. in Multiscale Model. Simul. 2:554?C579, 2004; Osher et?al. in Multiscale Model. Simul. 4:460?C489, 2005; Tadmor et?al. in Commun. Math. Sci. 6(2):281?C307, 2008), and L ¹ (He et?al. in J.?Math. Imaging Vis. 26:167?C184, 2005) data fidelity terms, with rigorous convergence results. Recently, Iusem and Resmerita (Set-Valued Var. Anal. 18(1):109?C120, 2010) proposed a proximal point method using inexact Bregman distance for minimizing a convex function defined on a non-reflexive Banach space (e.g. BV(??)), which is the dual of a separable Banach space. Based on this method, we investigate several approaches for image restoration such as image deblurring in the presence of noise or image deblurring via (cartoon+texture) decomposition. We show that the resulting proximal point algorithms approximate stably a true image. For image denoising-deblurring we consider Gaussian, Laplace, and Poisson noise models with the corresponding convex fidelity terms as in the Bayesian approach. We test the behavior of proposed algorithms on synthetic and real images in several numerical experiments and compare the results with other state-of-the-art iterative procedures based on the total variation penalization as well as the corresponding existing one-step gradient descent implementations. The numerical experiments indicate that the iterative procedure yields high quality reconstructions and superior results to those obtained by one-step standard gradient descent, with faster computational time.     

Cross-categorization of legal concepts across boundaries of legal systems: in consideration of inferential links

This work contrasts Giovanni Sartor’s view of inferential semantics of legal concepts (Sartor in Artif Intell Law 17:217–251, 2009) with a probabilistic model of theory formation (Kemp et al. in Cognition 114:165–196, 2010). The work further explores possibilities of implementing Kemp’s probabilistic model of theory formation in the context of mapping legal concepts between two individual legal systems. For implementing the legal concept mapping, we propose a cross-categorization approach that combines three mathematical models: the Bayesian Model of Generalization (BMG; Tenenbaum and Griffiths in Behav Brain Sci 4:629–640, 2001), the probabilistic model of theory formation, i.e., the Infinite Relational Model (IRM) first introduced by Kemp et al. (The twenty-first national conference on artificial intelligence, 2006, Cognition 114:165–196, 2010) and its extended model, i.e., the normal-IRM (n-IRM) proposed by Herlau et al. (IEEE International Workshop on Machine Learning for Signal Processing, 2012). We apply our cross-categorization approach to datasets where legal concepts related to educational systems are respectively defined by the Japanese- and the Danish authorities according to the International Standard Classification of Education. The main contribution of this work is the proposal of a conceptual framework of the cross-categorization approach that, inspired by Sartor (Artif Intell Law 17:217–251, 2009), attempts to explain reasoner’s inferential mechanisms.     

An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion

The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph?G and an integer k, one can delete at most k vertices from?G so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied Feedback Vertex Set (FVS) problem, where the deletion of at most k vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et?al. (WG, Lecture Notes in Computer Science, vol.?6410, pp.?196?C207, 2010) initiated the study of the parameterized complexity of POVD, showing a quartic kernel and an algorithm which runs in time 7 ^k n ^O(1). In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65 ^k n ^O(1), thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp.?251?C260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for FVS, due to Thomassé (ACM Trans. Algorithms 6(2), 2010).     

Functional un|unparsing

Danvy??s functional unparsing problem (Danvy in J. Funct. Program. 8(6), 621?C625, 1998) is to implement a type-safe ??printf?? function, which converts a sequence of heterogeneous arguments to a string according to a given format. The dual problem is to implement a type-safe ??scanf?? function, which extracts a sequence of heterogeneous arguments from a string by interpreting (Friedman and Wand in LFP, pp. 348?C355, 1984 and in Essentials of Programming Languages, MIT Press, 2008) the same format as an equally heterogeneous sequence of patterns that binds zero or more variables. We derive multiple solutions to both problems (Wand in J. ACM 27(1), 164?C180, 1980) from their formal specifications (Wand in Theor. Comput. Sci. 20(1), 3?C32, 1982). On one hand, our solutions show how the Hindley-Milner type system, unextended, permits accessing heterogeneous sequences with the static assurance of type safety. On the other hand, our solutions demonstrate the use of control operators (Felleisen et al. in Proceedings of the 1988 ACM Conference on Lisp and Functional Programming, pp. 52?C62, ACM Press, New York, 1988; Wand in POPL 85: Conference Record of the Annual ACM Symposium on Principles of Programming Languages, vol. 16, ACM Press, New York, 1985; Meyer and Wand in Logics of Programs, Lecture Notes in Computer Science, vol. 193, pp. 219?C224, Springer, Berlin, 1985) to communicate with formats as coroutines (Wand in Proceedings of the 1980 ACM Conference on Lisp and Functional Programming, vol. 12, pp. 285?C299, ACM Press, New York, 1980 and Haynes et al. in LFP, pp. 293?C298, 1984).     

Expected Optimal Feedback with Time-Varying Parameters

In this paper we derive the closed loop form of the Expected Optimal Feedback rule, sometimes called passive learning stochastic control, with time varying parameters. As such this paper extends the work of Kendrick (Stochastic control for economic models, 1981; Stochastic control for economic models, 2002, Chap. 6) where parameters are assumed to vary randomly around a known constant mean. Furthermore, we show that the cautionary myopic rule in Beck and Wieland (J Econ Dyn Control 26:1359–1377, 2002) model, a test bed for comparing various stochastic optimizations approaches, can be cast into this framework and can be treated as a special case of this solution.     

Multi-player epistemic games: Guiding the enactment of classroom knowledge-building communities

Teachers and students face many challenges in shifting from traditional classroom cultures to enacting the Knowledge-Building Communities model (KBC model) supported by the CSCL environment, Knowledge Forum (Bereiter, 2002; Bereiter & Scardamalia, 1993; Scardamalia, 2002; Scardamalia & Bereiter, 2006). Enacting the model involves socializing students into knowledge work, similar to disciplinary communities. A useful construct in the field of the Learning Sciences for understanding knowledge work is “epistemic games” (Collins & Ferguson, 1993; Morrison & Collins 1995; Perkins, 1997). We propose that a powerful means for supporting classroom enactments of the KBC model entails conceptualizing Knowledge Forum as a collective space for playing multi-player epistemic games. Participation in knowledge-building communities is then scaffolded through learning the moves of such games. We have designed scaffolding tools that highlight particular knowledge-building moves for practice and reflection as a means of supporting students and teachers in coming to understand how to collectively work together toward the progressive improvement of ideas. In order to examine our design theories in practice, we present research on Ideas First, a design-based research program involving enactments of the KBC model in Singaporean primary science classrooms (Bielaczyc & Ow, 2007, 2010; Ow & Bielaczyc, 2007; 2008).     

Can They Beat the Cournot Equilibrium? Learning with Memory and Convergence to Equilibria in a Cournot Oligopoly

This article analyses the ability of the learning firms in a Cournot oligopoly to discover market solutions more collusive that the Cournot equilibrium (CE). We start from the results of Vallée and Y?ld?zo?lu (J Econ Behav Organ 72:670–690, 2009) and of Alós-Ferrer (Int J Ind Organ 22:193–217, 2004), and qualify the role of random experimenting, social learning (imitation), and (updated) memory in helping firms to discover such solutions. Our new computational results show, in contradiction with Alós-Ferrer (2004), that memory and its continuous update can indeed allow firms to beat the CE, and benefit from significant periods with higher profits. We show that the results of the literature on evolutionary learning in oligopoly can analytically be characterized through the interaction of three forces, and indicate when these forces can yield more collusive outcomes. We confirm these results with complementary computational experiments that clearly show the role of long memory.     

On anonymizing transactions with sensitive items

K-anonymity (Samarati and Sweeny 1998; Samarati, IEEE Trans Knowl Data Eng, 13(6):1010–1027, 2001; Sweeny, Int J Uncertain, Fuzziness Knowl-Based Syst, 10(5):557–570, 2002) and its variants, l-diversity (Machanavajjhala et al., ACM TKDD, 2007) and tcloseness (Li et al. 2007) among others are anonymization techniques for relational data and transaction data, which are used to protect privacy against re-identification attacks. A relational dataset D is k-anonymous if every record in D has at least k-1 other records with identical quasi-identifier attribute values. The combination of released data with external data will never allow the recipient to associate each released record with less than k individuals (Samarati, IEEE Trans Knowl Data Eng, 13(6):1010–1027, 2001). However, the current concept of k-anonymity on transaction data treats all items as quasi-identifiers. The anonymized data set has k identical transactions in groups and suffers from lower data utility (He and Naughton 2009; He et al. 2011; Liu and Wang 2010; Terrovitis et al., VLDB J, 20(1):83–106, 2011; Terrovitis et al. 2008). To improve the utility of anonymized transaction data, this work proposes a novel anonymity concept on transaction data that contain both quasi-identifier items (QID) and sensitive items (SI). A transaction that contains sensitive items must have at least k-1 other identical transactions (Ghinita et al. IEEE TKDE, 33(2):161–174, 2011; Xu et al. 2008). For a transaction that does not contain a sensitive item, no anonymization is required. A transaction dataset that satisfies this property is said to be sensitive k-anonymous. Three algorithms, Sensitive Transaction Neighbors (STN) Gray Sort Clustering (GSC) and Nearest Neighbors for K-anonymization (K-NN), are developed. These algorithms use adding/deleting QID items and only adding SI to achieve sensitive k-anonymity on transaction data. Additionally, a simple “privacy value” is proposed to evaluate the degree of privacy for different types of k-anonymity on transaction data. Extensive numerical simulations were carried out to demonstrate the characteristics of the proposed algorithms and also compared to other types of k-anonymity approaches. The results show that each technique possesses its own advantage under different criteria such as running time, operation, and information loss. The results obtained here can be used as a guideline of the selection of anonymization technique on different data sets and for different applications.     

On sunflowers and matrix multiplication

We present several variants of the sunflower conjecture of Erd?s & Rado (J Lond Math Soc 35:85–90, 1960) and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to the questions of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990) and Cohn et al. (2005) regarding possible approaches for obtaining fast matrix-multiplication algorithms. Specifically, we show that the Erd?s–Rado sunflower conjecture (if true) implies a negative answer to the “no three disjoint equivoluminous subsets” question of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990); we also formulate a “multicolored” sunflower conjecture in ${\mathbb{Z}_3^n}$ and show that (if true) it implies a negative answer to the “strong USP” conjecture of Cohn et al. (2005) (although it does not seem to impact a second conjecture in Cohn et al. (2005) or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith–Winograd conjecture actually implies the Cohn et al. conjecture. The multicolored sunflower conjecture in ${\mathbb{Z}_3^n}$ is a strengthening of the well-known (ordinary) sunflower conjecture in ${\mathbb{Z}_3^n}$ , and we show via our connection that a construction from Cohn et al. (2005) yields a lower bound of (2.51 . . .) ⁿ on the size of the largest multicolored 3-sunflower-free set, which beats the current best-known lower bound of (2.21 . . . ) ⁿ Edel (2004) on the size of the largest 3-sunflower-free set in ${\mathbb{Z}_3^n}$ .     

Incentive-compatible interdomain routing

The routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP, Rekhter and Li in RFC 4271 of the Internet Engineering Task Force, 2006). Using BGP, ASes can apply semantically rich routing policies to choose interdomain routes in a distributed fashion. This expressiveness in routing-policy choice supports domains?? autonomy in network operations and in business decisions, but it comes at a price: The interaction of locally defined routing policies can lead to unexpected global anomalies, including route oscillations or overall protocol divergence (see, e.g., Varadhan et?al. in Comput Networks 32(1):1?C16, 2000). Networking researchers have addressed this problem by devising constraints on policies that guarantee BGP convergence without unduly limiting expressiveness and autonomy (see, e.g., Gao and Rexford in IEEE/ACM Trans Network 9(6):681?C692, 2001; Griffin et?al. in Proceedings of 9th ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM??03), pp. 61?C72. ACM Press, New York, 2003). In addition to taking this engineering or ??protocol- design?? approach, researchers have approached interdomain routing from an economic or ??mechanism-design?? point of view. It is known that lowest-cost-path (LCP) routing can be implemented in an incentive-compatible, BGP-compatible manner (Feigenbaum et?al. in Distribut. Comput 18(1):61?C72, 2005; Shneidman and Parkes in Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC??04), pp. 88?C97. ACM Press, New York, 2004) but that several other natural classes of policies cannot (Feigenbaum et?al. in Theor Comput Sci 378(2):175?C189, 2007; Feigenbaum et?al. in Distribut Comput 18(4):293?C305, 2006). In this paper, we present the first example of a class of interdomain-routing policies that is more general than LCP routing and for which BGP itself is both incentive-compatible and guaranteed to converge. We also present several steps toward a general theory of incentive-compatible, BGP-compatible interdomain routing.     

Modeling and optimization of the hot embossing process for micro- and nanocomponent fabrication

Hot embossing, a polymer molding process conceived by Forschungszentrum Karlsruhe, is one of the established replication processes for microstructures The process is especially well suited for manufacturing small and medium series of microcomponents (SPIE Conference 1997; Polymer News 25:224–229, 2000; J Micromech Microeng 14:R1–14, 2004; Sensors Actuators 3:130–135, 2000). However, a wider application of the process currently is seriously hampered by the lack of adequate simulation tools for process optimization and part design. This situation is becoming more critical, as the dimension of the microstructures shrink from micron and submicron levels to the nanoscale and as productivity requirements dictate the enlargement of formats to process larger numbers of devices in parallel. Based on the current scientific work (Forschungszentrum Karlsruhe, FZKA-Bericht 7058 2003; DTIP Conference Montreux 2004; Microsystem Tech 10:432–437 2004), a German–Canadian cooperation has been started. The objective of this cooperation is to fill the gap mentioned above by developing reliable computer models and simulation tools for the hot embossing process and to incorporate these models in a user-friendly computer code. The present paper will give an overview of the activities in the project. The activities related to material characterization, especially the development of a viscoelastic material model, the characterization of friction between polymer and mold during demolding, the development of an 8-in. microstructured mold, and the fabrication of nanostructured molds will be discussed.     

Fermat’s last theorem and chaoticity

Proving that a dynamical system is chaotic is a central problem in chaos theory (Hirsch in Chaos, fractals and dynamics, 1985]. In this note we apply the computational method developed in (Calude and Calude in Complex Syst 18:267?C285, 2009; Calude and Calude in Complex Syst 18:387?C401, 2010; Calude et al in J Multi Valued Log Soft Comput 12:285?C307, 2006) to show that Fermat??s last theorem is in the lowest complexity class ${{\mathfrak C}_{U,1}}$ . Using this result we prove the existence of a two-dimensional Hamiltonian system for which the proof that the system has a Smale horseshoe is in the class ${{\mathfrak C}_{U,1}}$ , i.e. it is not too complex.     

Some types of filters in residuated lattices

In this paper, inspired by some types of $BL$ -algebra filters (deductive systems) introduced in Haveshki et al. (Soft Comput 10:657–664, 2006), Kondo and Dudek (Soft Comput 12:419–423, 2008) and Turunen (Arch Math Log 40:467–473, 2001), we defined residuated lattice versions of them and study them in connection with Van Gasse et al. (Inf Sci 180(16):3006–3020, 2010), Lianzhen and Kaitai (Inf Sci 177:5725–5738, 2007), Zhu and Xu (Inf Sci 180:3614–3632, 2010). Also we consider some relations between these filters and quotient residuated lattice that are constructed via these filters.     

Analytic expressions of quantum correlations in qutrit Werner states

Quantum correlations in qutrit Werner states are extensively investigated with five popular methods, namely, original quantum discord (OQD) (Ollivier and Zurek in Phys Rev Lett 88:017901, 2001), measurement-induced disturbance (MID) (Luo in Phys Rev A 77:022301, 2008), ameliorated MID (AMID) (Girolami et al. in J Phys A Math Theor 44:352002, 2011), relative entropy (RE) (Modi et al. in Phys Rev Lett 104:080501, 2010) and geometric discord (GD) (Daki? et al. in Phys Rev Lett 105:190502, 2010). Two different analytic expressions of quantum correlations are derived. Quantum correlations captured by the former four methods are same and bigger than those obtained via the GD method. Nonetheless, they all qualitatively characterize quantum correlations in the concerned states. Moreover, as same as the qubit case, there exist quantum correlations in separable qutrit Werner states, too.