检索结果-内蒙古大学图书馆

Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications

学校读者我要写书评

暂无评论

Beyond the Lovász Local Lemma: Point to Set Correlations an...

Annual IEEE Symposium on Foundations of computer science

作者： Dimitris Achlioptas Fotis Iliopoulos Alistair Sinclair Dept. of Computer Science UC Santa Cruz Santa Cruz U.S.A. Dept. of Electrical Engineering and Computer Science UC Berkeley Berkeley U.S.A.

Following the groundbreaking algorithm of Moser and Tardos for the Lovasz Local Lemma (LLL), there has been a plethora of results analyzing local search algorithms for various constraint satisfaction problems. The algorithms considered fall into two broad categories: resampling algorithms, analyzed via different algorithmic LLL conditions; and backtracking algorithms, analyzed via entropy compression arguments. This paper introduces a new convergence condition that seamlessly handles resampling, backtracking, and hybrid algorithms, i.e., algorithms that perform both resampling and backtracking steps. Unlike previous work on the LLL, our condition replaces the notion of a dependency or causality graph by quantifying point-to-set correlations between bad events. As a result, our condition simultaneously: (i) captures the most general algorithmic LLL condition known as a special case; (ii) significantly simplifies the analysis of entropy compression applications; (iii) relates backtracking algorithms, which are conceptually very different from resampling algorithms, to the LLL; and most importantly (iv) allows for the analysis of hybrid algorithms, which were outside the scope of previous techniques. We give several applications of our condition, including a new hybrid vertex coloring algorithm that extends the recent breakthrough result of Molloy for coloring triangle-free graphs to arbitrary graphs.

关键词： Backtracking Computational complexity Constraint theory Search problems Entropy Graph theory

Learning how to dynamically route autonomous vehicles on shared roads

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Lazar, Daniel A. Bıyık, Erdem Sadigh, Dorsa Pedarsani, Ramtin Department of Electrical and Computer Engineering UC Santa Barbara Department of Electrical Engineering Stanford University Departments of Computer Science and Electrical Engineering Stanford University

Road congestion induces significant costs across the world, and road network disturbances, such as traffic accidents, can cause highly congested traffic patterns. If a planner had control over the routing of all vehicles in the network, they could easily reverse this effect. In a more realistic scenario, we consider a planner that controls autonomous cars, which are a fraction of all present cars. We study a dynamic routing game, in which the route choices of autonomous cars can be controlled and the human drivers react selfishly and dynamically. As the problem is prohibitively large, we use deep reinforcement learning to learn a policy for controlling the autonomous vehicles. This policy indirectly influences human drivers to route themselves in such a way that minimizes congestion on the network. To gauge the effectiveness of our learned policies, we establish theoretical results characterizing equilibria and empirically compare the learned policy results with best possible equilibria. We prove properties of equilibria on parallel roads and provide a polynomial-time optimization for computing the most efficient equilibrium. Moreover, we show that in the absence of these policies, high demand and network perturbations would result in large congestion, whereas using the policy greatly decreases the travel times by minimizing the congestion. To the best of our knowledge, this is the first work that employs deep reinforcement learning to reduce congestion by indirectly influencing humans’ routing decisions in mixed-autonomy traffic. Copyright © 2019, The Authors. All rights reserved.

关键词： Autonomous vehicles

REINFORCEMENT LEARNING FROM IMPERFECT DEMONSTRATIONS 6

学校读者我要写书评

暂无评论

REINFORCEMENT LEARNING FROM IMPERFECT DEMONSTRATIONS

6th International Conference on Learning Representations, ICLR 2018

作者： Gaoy, Yang Xuy, Huazhe Harry Linz, Ji Yuy, Fisher Leviney, Sergey Darrelly, Trevor UC Berkeley Department of Electrical Engineering and Computer Science Tsinghua University Department of Electrical Engineering

Robust real-world learning should benefit from both demonstrations and interaction with the environment. Current approaches to learning from demonstration and reward perform supervised learning on expert demonstration data and use reinforcement learning to further improve performance based on reward from the environment. These tasks have divergent losses which are difficult to jointly optimize;further, such methods can be very sensitive to noisy demonstrations. We propose a unified reinforcement learning algorithm, Normalized Actor-Critic (NAC), that effectively normalizes the Q-function, reducing the Q-values of actions unseen in the demonstration data. NAC learns an initial policy network from demonstration and refines the policy in a real environment. Crucially, both learning from demonstration and interactive refinement use exactly the same objective, unlike prior approaches that combine distinct supervised and reinforcement losses. This makes NAC robust to suboptimal demonstration data, since the method is not forced to mimic all of the examples in the dataset. We show that our unified reinforcement learning algorithm can learn robustly and outperform existing baselines when evaluated on several realistic driving games. © 2019 International Conference on Learning Representations, ICLR. All rights reserved.

关键词： Demonstrations

Workload-aware opportunistic energy efficiency in multi-FPGA platforms

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Salamat, Sahand Khaleghi, Behnam Imani, Mohsen Rosing, Tajana Computer Science and Engineering Department UC San Diego San DiegoCA92093 United States

The continuous growth of big data applications with high computational and scalability demands has resulted in increasing popularity of cloud computing. Optimizing the performance and power consumption of cloud resources is therefore crucial to relieve the costs of data centers. In recent years, multi-FPGA platforms have gained traction in data centers as low-cost yet high-performance solutions particularly as acceleration engines, thanks to the high degree of parallelism they provide. Nonetheless, the size of data centers workloads varies during service time, leading to significant underutilization of computing resources while consuming a large amount of power, which turns out as a key factor of data center inefficiency, regardless of the underlying hardware structure. In this paper, we propose an efficient framework to throttle the power consumption of multi-FPGA platforms by dynamically scaling the voltage and hereby frequency during runtime according to prediction of, and adjustment to the workload level, while maintaining the desired Quality of Service (QoS). This is in contrast to, and more efficient than, conventional approaches that merely scale (i.e., power-gate) the computing nodes or frequency. The proposed framework carefully exploits a pre-characterized library of delay-voltage, and power-voltage information of FPGA resources, which we show is indispensable to obtain the efficient operating point due to the different sensitivity of resources w.r.t. voltage scaling, particularly considering multiple power rails residing in these devices. Our evaluations by implementing state-of-the-art deep neural network accelerators revealed that, providing an average power reduction of 4.0×, the proposed framework surpasses the previous works by 33.6% (up to 83%). Copyright © 2019, The Authors. All rights reserved.

关键词： Electric power utilization

Splaying Preorders and Postorders∗

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Levy, Caleb C. Tarjan, Robert E. Baskin School of Engineering UC Santa Cruz Department of Computer Science Princeton University Intertrust Technologies

Let T be a binary search tree of n nodes with root r, left subtree L = left(r), and right subtree R = right(r). The preorder and postorder of T are defined as follows: the preorder and postorder of the empty tree is the empty sequence, and preorder(T) = (r) preorder(L) preorder(R) postorder(T) = postorder(L) postorder(R) (r), where denotes sequence concatenation.1 We prove the following results about the behavior of splaying [21] preorders and postorders: 1. Inserting the nodes of preorder(T) into an empty tree via splaying costs O(n). (Theorem 2.) 2. Inserting the nodes of postorder(T) into an empty tree via splaying costs O(n). (Theorem 3.) 3. If T0 has the same keys as T and T is weight-balanced [18] then splaying either preorder(T) or postorder(T) starting from T0 costs O(n). (Theorem 4.) For 1 and 2, we use the fact that preorders and postorders are pattern-avoiding: i.e. they contain no subsequences that are order-isomorphic to (2, 3, 1) and (3, 1, 2), respectively. Pattern-avoidance implies certain constraints on the manner in which items are inserted. We exploit this structure with a simple potential function that counts inserted nodes lying on access paths to uninserted nodes. Our methods can likely be extended to permutations that avoid more general patterns. The proof of 3 uses the fact that preorders and postorders of balanced search trees do not contain many large "jumps" in symmetric order, and exploits this fact using the dynamic finger theorem [6, 5]. Items 2 and 3 are both novel. Item 1 was originally proved by Chaudhuri and Höft [4];our proof simplifies theirs. These results provide further evidence in favor of the elusive dynamic optimality conjecture [21]. Copyright © 2019, The Authors. All rights reserved.

关键词： Binary trees

A simple neural attentive meta-learner 6

学校读者我要写书评

暂无评论

A simple neural attentive meta-learner

6th International Conference on Learning Representations, ICLR 2018

作者： Mishra, Nikhil Rohaninejad, Mostafa Chen, Xi Abbeel, Pieter UC Berkeley Department of Electrical Engineering and Computer Science Embodied Intelligence United States

Deep neural networks excel in regimes with large amounts of data, but tend to struggle when data is scarce or when they need to adapt quickly to changes in the task. In response, recent work in meta-learning proposes training a meta-learner on a distribution of similar tasks, in the hopes of generalization to novel but related tasks by learning a high-level strategy that captures the essence of the problem it is asked to solve. However, many recent meta-learning approaches are extensively hand-designed, either using architectures specialized to a particular application, or hard-coding algorithmic components that constrain how the meta-learner solves the task. We propose a class of simple and generic meta-learner architectures that use a novel combination of temporal convolutions and soft attention;the former to aggregate information from past experience and the latter to pinpoint specific pieces of information. In the most extensive set of meta-learning experiments to date, we evaluate the resulting Simple Neural AttentIve Learner (or SNAIL) on several heavily-benchmarked tasks. On all tasks, in both supervised and reinforcement learning, SNAIL attains state-of-the-art performance by significant margins. © Learning Representations, ICLR 2018 - Conference Track *** right reserved.

关键词： Reinforcement learning

HDNA: Energy-efficient DNA sequencing using hyperdimensional computing

学校读者我要写书评

暂无评论

HDNA: Energy-efficient DNA sequencing using hyperdimensional...

2018 IEEE EMBS International Conference on Biomedical and Health Informatics, BHI 2018

作者： Imani, Mohsen Nassar, Tarek Rahimi, Abbas Rosing, Tajana Computer Science and Engineering UC San Diego San DiegoCA92093 United States Electrical Engineering and Computer Sciences UC Berkeley BerkeleyCA94720 United States

ISBN: (纸本)9781538624050

DNA sequencing has a vast number of applications in a multitude of applied fields including, but not limited to, medical diagnosis and biotechnology. In this paper, we propose HDNA to apply the concepts of hyperdimensional (HD) computing (computing with hypervectors) to DNA sequencing. HDNA first assigns holographic and (pseudo)random hyper-vectors to DNA bases. Using an encoder, it then exploits the orthogonality of these hypervectors to represent a DNA sequence by generating a class hypervector. The class hypervector keeps the information of combined individual hypervectors (i.e., the DNA bases) with high probability. HDNA uses the same encoding to map a DNA sequence with unknown labels to a query hypervectors and performs the classification task by checking the similarity of the query hypervector against all class hypervectors. Our experimental evaluation shows that HDNA can achieve 99.7% classification accuracy for Empirical dataset which is 5.2% higher than state-of-the-art techniques for the same dataset. Moreover, our HDNA can improve the execution time and energy consumption of classification by 4.32 × and 2.05 × respectively, when compared against prior techniques. © 2018 IEEE.

关键词： DNA sequences

Interval and -interval rational parking functions

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Aguilar-Fraga, Tomás Elder, Jennifer Garcia, Rebecca E. Hadaway, Kimberly P. Harris, Pamela E. Harry, Kimberly J. Hogan, Imhotep B. Johnson, Jakeyl Kretschmann, Jan Lawson-Chavanu, Kobe Carlos Martínez Mori, J. Monroe, Casandra D. Quiñonez, Daniel Tolson, Dirk Williams, Dwight Anderson Department of Mathematics Harvey Mudd College ClaremontCA United States Department of Computer Science Mathematics and Physics Missouri Western State University MO United States Department of Mathematics and Computer Science Colorado College Colorado SpringsCO United States Department of Mathematics Iowa State University AmesIA United States Department of Mathematical Sciences University of Wisconsin-Milwaukee MilwaukeeWI United States Department of Mathematics Florida A&M University TallahasseeFL United States Department of Mathematics San Francisco State University San FranciscoCA United States Department of Mathematics Emory College AtlantaGA United States H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology AtlantaGA United States Department of Mathematics University of Texas at Austin AustinTX United States Department of Mathematics UC Irvine IrvineCA United States Department of Mathematics and statistics Sonoma State University Rohnert ParkCA United States Department of Mathematics Morgan State University BaltimoreMD United States

Interval parking functions are a generalization of parking functions in which cars have an interval preference for their parking. We generalize this definition to parking functions with n cars and m ≥ n parking spots, which we call interval rational parking functions and provide a formula for their enumeration. By specifying an integer parameter ≥ 0, we then consider the subset of interval rational parking functions in which each car parks at most spots away from their initial preference. We call these -interval rational parking functions and provide recursive formulas to enumerate this set for all positive integers m ≥ n and . We also establish formulas for the number of nondecreasing -interval rational parking functions via the outcome map on rational parking functions. We also consider the intersection between -interval parking functions and Fubini rankings and show the enumeration of these sets is given by generalized Fibonacci numbers. We conclude by specializing = 1, and establish that the set of 1-interval rational parking functions with n cars and m spots are in bijection with the set of barred preferential arrangements of [n] with m−n bars. This readily implies enumerative formulas. Further, in the case where = 1, we recover the results of Hadaway and Harris that unit interval parking functions are in bijection with the set of Fubini rankings, which are enumerated by the Fubini *** Codes 05A05, 05A15, 05A18, 05A19 Copyright © 2023, The Authors. All rights reserved.

关键词： Rational functions

Doubly-efficient pseudo-deterministic proofs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Goemans, Michel Goldwasser, Shafi Holden, Dhiraj Department of Mathematics MIT Simons Institute for the Theory of Computing UC Berkeley Department of Electrical Engineering and Computer Science MIT

In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions are possible. They showed that whereas there exists a constant round pseudo deterministic proof for graph isomorphism where the canonical solution is the lexicographically smallest isomorphism, the existence of pseudo-deterministic interactive proofs for NP-hard problems would imply the collapse of the polynomial time hierarchy. Copyright © 2019, The Authors. All rights reserved.

关键词： Polynomial approximation