transitivity


A Bayesian Choice Model for Eliminating Feedback Loops

arXiv.org Machine Learning

Self-reinforcing feedback loops in personalization systems are typically caused by users choosing from a limited set of alternatives presented systematically based on previous choices. We propose a Bayesian choice model built on Luce axioms that explicitly accounts for users' limited exposure to alternatives. Our model is fair---it does not impose negative bias towards unpresented alternatives, and practical---preference estimates are accurately inferred upon observing a small number of interactions. It also allows efficient sampling, leading to a straightforward online presentation mechanism based on Thompson sampling. Our approach achieves low regret in learning to present upon exploration of only a small fraction of possible presentations. The proposed structure can be reused as a building block in interactive systems, e.g., recommender systems, free of feedback loops.


Extension of Rough Set Based on Positive Transitive Relation

arXiv.org Artificial Intelligence

The application of rough set theory in incomplete information systems is a key problem in practice since missing values almost always occur in knowledge acquisition due to the error of data measuring, the limitation of data collection, or the limitation of data comprehension, etc. An incomplete information system is mainly processed by compressing the indiscernibility relation. The existing rough set extension models based on tolerance or symmetric similarity relations typically discard one relation among the reflexive, symmetric and transitive relations, especially the transitive relation. In order to overcome the limitations of the current rough set extension models, we define a new relation called the positive transitive relation and then propose a novel rough set extension model built upon which. The new model holds the merit of the existing rough set extension models while avoids their limitations of discarding transitivity or symmetry. In comparison to the existing extension models, the proposed model has a better performance in processing the incomplete information systems while substantially reducing the computational complexity, taking into account the relation of tolerance and similarity of positive transitivity, and supplementing the related theories in accordance to the intuitive classification of incomplete information. In summary, the positive transitive relation can improve current theoretical analysis of incomplete information systems and the newly proposed extension model is more suitable for processing incomplete information systems and has a broad application prospect.


Differentiating Concepts and Instances for Knowledge Graph Embedding

arXiv.org Artificial Intelligence

Concepts, which represent a group of different instances sharing common properties, are essential information in knowledge representation. Most conventional knowledge embedding methods encode both entities (concepts and instances) and relations as vectors in a low dimensional semantic space equally, ignoring the difference between concepts and instances. In this paper, we propose a novel knowledge graph embedding model named TransC by differentiating concepts and instances. Specifically, TransC encodes each concept in knowledge graph as a sphere and each instance as a vector in the same semantic space. We use the relative positions to model the relations between concepts and instances (i.e., instanceOf), and the relations between concepts and sub-concepts (i.e., subClassOf). We evaluate our model on both link prediction and triple classification tasks on the dataset based on YAGO. Experimental results show that TransC outperforms state-of-the-art methods, and captures the semantic transitivity for instanceOf and subClassOf relation. Our codes and datasets can be obtained from https:// github.com/davidlvxin/TransC.


Navigability with Bounded Recall

AAAI Conferences

The paper studies navigability by machines with bounded recall in mazes with imperfect information. The main result is a sound and complete logical system for the relation  "there is a machine with at most n states that can navigate from a set of classes of indistinguishable rooms X to a set of classes of indistinguishable rooms Y .'' The axioms of the system generalize Armstrong's axioms of functional dependency from database theory.


Cycles and Intractability in a Large Class of Aggregation Rules

Journal of Artificial Intelligence Research

We introduce the (j,k)-Kemeny rule -- a generalization of Kemeny's voting rule that aggregates j-chotomous weak orders into a k-chotomous weak order. Special cases of (j,k)-Kemeny include approval voting, the mean rule and Borda mean rule, as well as the Borda count and plurality voting. Why, then, is the winner problem computationally tractable for each of these other rules, but intractable for Kemeny? We show that intractability of winner determination for the (j,k)-Kemeny rule first appears at the j=3, k=3 level. The proof rests on a reduction of max cut to a related problem on weighted tournaments, and reveals that computational complexity arises from the cyclic part in the fundamental decomposition of a weighted tournament into cyclic and cocyclic components. Thus the existence of majority cycles -- the engine driving both Arrow's impossibility theorem and the Gibbard-Satterthwaite theorem -- also serves as a source of computational complexity in social choice.


Hyperbolic Entailment Cones for Learning Hierarchical Embeddings

arXiv.org Machine Learning

Learning graph representations via low-dimensional embeddings that preserve relevant network properties is an important class of problems in machine learning. We here present a novel method to embed directed acyclic graphs. Following prior work, we first advocate for using hyperbolic spaces which provably model tree-like structures better than Euclidean geometry. Second, we view hierarchical relations as partial orders defined using a family of nested geodesically convex cones. We prove that these entailment cones admit an optimal shape with a closed form expression both in the Euclidean and hyperbolic spaces. Moreover, they canonically define the embedding learning process. Experiments show significant improvements of our method over strong recent baselines both in terms of representational capacity and generalization.


Armstrong's Axioms and Navigation Strategies

AAAI Conferences

The paper investigates navigability with imperfect information. It shows that the properties of navigability with perfect recall are exactly those captured by Armstrong's axioms from database theory. If the assumption of perfect recall is omitted, then Armstrong's transitivity axiom is not valid, but it can be replaced by a weaker principle. The main technical results are soundness and completeness theorems for the logical systems describing properties of navigability with and without perfect recall.


COBRA: A Fast and Simple Method for Active Clustering with Pairwise Constraints

arXiv.org Machine Learning

Clustering is inherently ill-posed: there often exist multiple valid clusterings of a single dataset, and without any additional information a clustering system has no way of knowing which clustering it should produce. This motivates the use of constraints in clustering, as they allow users to communicate their interests to the clustering system. Active constraint-based clustering algorithms select the most useful constraints to query, aiming to produce a good clustering using as few constraints as possible. We propose COBRA, an active method that first over-clusters the data by running K-means with a $K$ that is intended to be too large, and subsequently merges the resulting small clusters into larger ones based on pairwise constraints. In its merging step, COBRA is able to keep the number of pairwise queries low by maximally exploiting constraint transitivity and entailment. We experimentally show that COBRA outperforms the state of the art in terms of clustering quality and runtime, without requiring the number of clusters in advance.


A Logic for Making Hard Decisions

AAAI Conferences

We tackle the problem of providing engineering decision makers with relevant information extracted from data obtained via a process model based on deliberation and voting. We list examples of potential applications from the area of bug-fix scheduling for software, as well as space-vehicles 'go'-'no-go' decision making. In such application domains, important decisions have to be made hastily and therefore the decision factors have to be informed timely of the main issues discovered by the teams. A logic is proposed for reasoning with comments available in such deliberations. Search based algorithms are proposed which recommend the best justifications for a decision and retain the voting decisions for interested parties to tally. We have developed a Bayesian network for generating data by simulation based on probabilistic models that we can train from collected deliberation databases. The data generated in this way was used for evaluating the proposed search algorithm, showing how it can provide better than random recommendations of arguments to decision makers.


Why Do Men Get More Attention? Exploring Factors Behind Success in An Online Design Community

AAAI Conferences

Online platforms are an increasingly popular tool for people to produce, promote or sell their work. However recent studies indicate that social disparities and biases present in the real world might transfer to online platforms and could be exacerbated by seemingly harmless design choices on the site (for example: recommendation systems or publicly visible success measures). In this paper we analyze an exclusive online community of teams of design professionals called Dribbble and investigate apparent differences in outcomes by gender. Overall, we find that men produce more work, and are able to show it to a larger audience thus receiving more likes. Some of this effect can be explained by the fact that women have different skills and design different images. Most importantly however, women and men position themselves differently in the Dribbble community. Our investigation of users' position in the social network shows that women have more clustered and gender homophilous following relations, which leads them to have smaller and more closely knit social networks. Overall, our study demonstrates that looking behind the apparent patterns of gender inequalities in online markets with the help of social networks and product differentiation helps us to better understand gender differences in success and failure.