An official website of the United States government
Templated graphical models (TGMs) encode model structure using rules that capture recurring relationships between multiple random variables. While the rules in TGMs are interpretable, it is not clear how they can be used to generate explanations for the individual predictions of the model. Further, learning these rules from data comes with high computational costs: it typically requires an expensive combinatorial search over the space of rules and repeated optimization over rule weights. In this work, we propose a new structure learning algorithm, Explainable Structured Model Search (ESMS), that learns a templated graphical model and an explanation framework for its predictions. ESMS uses a novel search procedure to efficiently search the space of models and discover models that trade-off predictive accuracy and explainability. We introduce the notion of relational stability and prove that our proposed explanation framework is stable. Further, our proposed piecewise pseudolikelihood (PPLL) objective does not require re-optimizing the rule weights across models during each iteration of the search. In our empirical evaluation on three realworld datasets, we show that our proposed approach not only discovers models that are explainable, but also significantly outperforms existing state-out-the-art structure learning approaches.
more »
« less
Designing Core-Selecting Payment Rules: A Computational Search Approach
We study the design of core-selecting payment rules for combinatorial auctions, a challenging setting where no strategyproof rules exist. We show that the rule most commonly used in practice, the Quadratic rule, can be improved on in terms of efficiency, incentives, and revenue. We present a new computational search framework for finding good mechanisms, and we apply it toward a search for good core-selecting rules. Within our framework, we use an algorithmic Bayes–Nash equilibrium solver to evaluate 366 rules across 31 settings to identify rules that outperform the Quadratic rule. Our main finding is that our best-performing rules are large-style rules—that is, they provide bidders with large values with better incentives than does the Quadratic rule. Finally, we identify two particularly well-performing rules and suggest that they may be considered for practical implementation in place of the Quadratic rule.
more »
« less
- Award ID(s):
- 1761163
- PAR ID:
- 10384278
- Date Published:
- Journal Name:
- Information Systems Research
- ISSN:
- 1047-7047
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)The brain modifies its synaptic strengths during learning in order to better adapt to its environment. However, the underlying plasticity rules that govern learning are unknown. Many proposals have been suggested, including Hebbian mechanisms, explicit error backpropagation, and a variety of alternatives. It is an open question as to what specific experimental measurements would need to be made to determine whether any given learning rule is operative in a real biological system. In this work, we take a "virtual experimental" approach to this problem. Simulating idealized neuroscience experiments with artificial neural networks, we generate a large-scale dataset of learning trajectories of aggregate statistics measured in a variety of neural network architectures, loss functions, learning rule hyperparameters, and parameter initializations. We then take a discriminative approach, training linear and simple non-linear classifiers to identify learning rules from features based on these observables. We show that different classes of learning rules can be separated solely on the basis of aggregate statistics of the weights, activations, or instantaneous layer-wise activity changes, and that these results generalize to limited access to the trajectory and held-out architectures and learning curricula. We identify the statistics of each observable that are most relevant for rule identification, finding that statistics from network activities across training are more robust to unit undersampling and measurement noise than those obtained from the synaptic strengths. Our results suggest that activation patterns, available from electrophysiological recordings of post-synaptic activities on the order of several hundred units, frequently measured at wider intervals over the course of learning, may provide a good basis on which to identify learning rules.more » « less
-
Autonomous vehicles (AV) hold great potential to increase road safety, reduce traffic congestion, and improve mobility systems. However, the deployment of AVs introduces new liability challenges when they are involved in car accidents. A new legal framework should be developed to tackle such a challenge. This paper proposes a legal framework, incorporating liability rules to rear-end crashes in mixed-traffic platoons with AVs and human-propelled vehicles (HV). We leverage a matrix game approach to understand interactions among players whose utility captures crash loss for drivers according to liability rules. We investigate how liability rules may impact the game equilibrium between vehicles and whether human drivers’ moral hazards arise if liability is not designed properly. We find that compared to the no-fault liability rule, contributory and comparative rules make road users have incentives to execute a smaller reaction time to improve road safety. There exists moral hazards for human drivers when risk-averse AV players are in the car platoon.more » « less
-
We introduce the General Video Game Rule Gen- eration problem, and the eponymous software framework which will be used in a new track of the General Video Game AI (GVGAI) competition. The problem is, given a game level as input, to generate the rules of a game that fits that level. This can be seen as the inverse of the General Video Game Level Generation problem. Conceptualizing these two problems as separate helps breaking the very hard problem of generating complete games into smaller, more manageable subproblems. The proposed framework builds on the GVGAI software and thus asks the rule generator for rules defined in the Video Game Description Language. We describe the API, and three different rule generators: a random, a constructive and a search- based generator. Early results indicate that the constructive generator generates playable and somewhat interesting game rules but has a limited expressive range, whereas the search- based generator generates remarkably diverse rulesets, but with an uneven quality.more » « less
-
While deep learning approaches to information extraction have had many successes, they can be difficult to augment or maintain as needs shift. Rule-based methods, on the other hand, can be more easily modified. However, crafting rules requires expertise in linguistics and the domain of interest, making it infeasible for most users. Here we attempt to combine the advantages of these two directions while mitigating their drawbacks. We adapt recent advances from the adjacent field of program synthesis to information extraction, synthesizing rules from provided examples. We use a transformer-based architecture to guide an enumerative search, and show that this reduces the number of steps that need to be explored before a rule is found. Further, we show that our synthesized rules achieve state-of-the-art performance on the 1-shot scenario of a task that focuses on few-shot learning for relation classification, and competitive performance in the 5-shot scenario.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1287/isre.2022.1108
