Learning intersections and thresholds of halfspaces

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution on the Boolean hypercube to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any Boolean function of a polylog number of polynomial-weight halfspaces under any distribution on the Boolean hypercube. As special cases of these results we obtain algorithms for learning intersections and thresholds of halfspaces. Our uniform distribution learning algorithms involve a novel non-geometric approach to learning halfspaces; we use Fourier techniques together with a careful analysis of the noise sensitivity of functions of halfspaces. Our algorithms for learning under any distribution use techniques from real approximation theory to construct low-degree polynomial threshold functions. Finally, we also observe that any function of a constant number of polynomial-weight halfspaces can be learned in polynomial time in the model of exact learning from membership and equivalence queries.     

Unconditional lower bounds for learning intersections of halfspaces

We prove new lower bounds for learning intersections of halfspaces, one of the most important concept classes in computational learning theory. Our main result is that any statistical-query algorithm for learning the intersection of $\sqrt{n}$ halfspaces in n dimensions must make $2^{\varOmega (\sqrt{n})}$ queries. This is the first non-trivial lower bound on the statistical query dimension for this concept class (the previous best lower bound was n ^Ω(log?n)). Our lower bound holds even for intersections of low-weight halfspaces. In the latter case, it is nearly tight. We also show that the intersection of two majorities (low-weight halfspaces) cannot be computed by a polynomial threshold function (PTF) with fewer than n ^{Ω(log?n/log?log?n)} monomials. This is the first super-polynomial lower bound on the PTF length of this concept class, and is nearly optimal. For intersections of k=ω(log?n) low-weight halfspaces, we improve our lower bound to $\min\{2^{\varOmega (\sqrt{n})},n^{\varOmega (k/\log k)}\},$ which too is nearly optimal. As a consequence, intersections of even two halfspaces are not computable by polynomial-weight PTFs, the most expressive class of functions known to be efficiently learnable via Jackson’s Harmonic Sieve algorithm. Finally, we report our progress on the weak learnability of intersections of halfspaces under the uniform distribution.     

Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts

The complexity of on-line learning is investigated for the basic classes of geometrical objects over a discrete (digitized) domain. In particular, upper and lower bounds are derived for the complexity of learning algorithms for axis-parallel rectangles, rectangles in general position, balls, halfspaces, intersections of half-spaces, and semi-algebraic sets. The learning model considered is the standard model for on-line learning from counterexamples.     

The regularized least squares algorithm and the problem of learning halfspaces

We provide sample complexity of the problem of learning halfspaces with monotonic noise, using the regularized least squares algorithm in the reproducing kernel Hilbert spaces (RKHS) framework.     

Cryptographic hardness for learning intersections of halfspaces

We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time algorithm for PAC learning intersections of $n^{\mathrm{?}}$ halfspaces (for a constant $\mathrm{?}>0$) in n dimensions would yield a polynomial-time solution to $\stackrel{?}{O}(n^{1.5})$-$\mathsf{uSVP}$ (unique shortest vector problem). We also prove that PAC learning intersections of $n^{\mathrm{?}}$ low-weight halfspaces would yield a polynomial-time quantum solution to $\stackrel{?}{O}(n^{1.5})$-$\mathsf{SVP}$ and $\stackrel{?}{O}(n^{1.5})$-$\mathsf{SIVP}$ (shortest vector problem and shortest independent vector problem, respectively). Our approach also yields the first representation-independent hardness results for learning polynomial-size depth-2 neural networks and polynomial-size depth-3 arithmetic circuits.     

基于博弈学习的多Agent城市交通协调控制

交通路口中的各Agent之间的协调问题是一个博弈问题。在有限理性的基础上,利用博弈学习思想,构建多智能体（multi-Agent）博弈学习协调算法,利用此学习协调算法对出行者行为分析并修正,实现城市交通路口的畅通,进而达到区域、全局的交通优化。最后通过实例仿真验证其可行性。     

PAC Learning Intersections of Halfspaces with Membership Queries

A randomized learning algorithm {POLLY} is presented that efficiently learns intersections of s halfspaces in n dimensions, in time polynomial in both s and n . The learning protocol is the PAC (probably approximately correct) model of Valiant, augmented with membership queries. In particular, {POLLY} receives a set S of m = poly(n,s,1/ε,1/δ) randomly generated points from an arbitrary distribution over the unit hypercube, and is told exactly which points are contained in, and which points are not contained in, the convex polyhedron P defined by the halfspaces. {POLLY} may also obtain the same information about points of its own choosing. It is shown that after poly(n , s , 1/ε , 1/δ , log(1/d) ) time, the probability that {POLLY} fails to output a collection of s halfspaces with classification error at most ε , is at most δ . Here, d is the minimum distance between the boundary of the target and those examples in S that are not lying on the boundary. The parameter log(1/d) can be bounded by the number of bits needed to encode the coefficients of the bounding hyperplanes and the coordinates of the sampled examples S . Moreover, {POLLY} can be extended to learn unions of k disjoint polyhedra with each polyhedron having at most s facets, in time poly(n , k , s , 1/ε , 1/δ , log(1/d) , 1/γ ) where γ is the minimum distance between any two distinct polyhedra. Received February 5, 1997; revised July 1, 1997.     

基于深度强化学习的无信号灯交叉路口车辆控制

利用深度强化学习技术实现无信号灯交叉路口车辆控制是智能交通领域的研究热点。现有研究存在无法适应自动驾驶车辆数量动态变化、训练收敛慢、训练结果只能达到局部最优等问题。文中研究在无信号灯交叉路口,自动驾驶车辆如何利用分布式深度强化方法来提升路口的通行效率。首先,提出了一种高效的奖励函数,将分布式强化学习算法应用到无信号灯交叉路口场景中,使得车辆即使无法获取整个交叉路口的状态信息,只依赖局部信息也能有效提升交叉路口的通行效率。然后,针对开放交叉路口场景中强化学习方法训练效率低的问题,使用了迁移学习的方法,将封闭的8字型场景中训练好的策略作为暖启动,在无信号灯交叉路口场景继续训练,提升了训练效率。最后,提出了一种可以适应所有自动驾驶车辆比例的策略,此策略在任意比例自动驾驶车辆的场景中均可提升交叉路口的通行效率。在仿真平台Flow上对TD3强化学习算法进行了验证,实验结果表明,改进后的算法训练收敛快,能适应自动驾驶车辆比例的动态变化,能有效提升路口的通行效率。     

Complexity theoretic hardness results for query learning

We investigate the complexity of learning for the well-studied model in which the learning algorithm may ask membership and equivalence queries. While complexity theoretic techniques have previously been used to prove hardness results in various learning models, these techniques typically are not strong enough to use when a learning algorithm may make membership queries. We develop a general technique for proving hardness results for learning with membership and equivalence queries (and for more general query models). We apply the technique to show that, assuming , no polynomial-time membership and (proper) equivalence query algorithms exist for exactly learning read-thrice DNF formulas, unions of halfspaces over the Boolean domain, or some other related classes. Our hardness results are representation dependent, and do not preclude the existence of representation independent algorithms.?The general technique introduces the representation problem for a class F of representations (e.g., formulas), which is naturally associated with the learning problem for F. This problem is related to the structural question of how to characterize functions representable by formulas in F, and is a generalization of standard complexity problems such as Satisfiability. While in general the representation problem is in , we present a theorem demonstrating that for "reasonable" classes F, the existence of a polynomial-time membership and equivalence query algorithm for exactly learning F implies that the representation problem for F is in fact in co-NP. The theorem is applied to prove hardness results such as the ones mentioned above, by showing that the representation problem for specific classes of formulas is NP-hard. Received: December 6, 1994     

Trial and Error

A pac-learning algorithm is -space bounded, if it stores at most examples from the sample at any time. We characterize the -space learnable concept classes. For this purpose we introduce the compression parameter of a concept class and design our Trial and Error Learning Algorithm. We show : is -space learnable if and only if the compression parameter of is at most . This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes: – all intersection closed concept classes with finite VC–dimension. – convex -gons in . – halfspaces in . – unions of triangles in . We further relate the compression parameter to the VC–dimension, and discuss variants of this parameter. Received May 24, 1994 / July 4, 1995     

两相邻路口交通信号的协调控制

传统路口的控制算法大多研究单个路口的信号控制情况.该文根据路口之间的相互关 系,利用高阶广义神经网络及模糊推理提出了两个相邻交通路口的协调算法.利用此算法设计 的交通信号控制器,可以有效地协调两相邻路口的红绿灯信号,在一定程度上改善了交通路口 的交通状况.     

Intelligent traffic light systems using edge flow predictions

In this paper, we propose a novel graph-based semi-supervised learning approach for traffic light management in multiple intersections. Specifically, the basic premise behind our paper is that if we know some of the occupied roads and predict which roads will be congested, we can dynamically change traffic lights at the intersections that are connected to the roads anticipated to be congested. Comparative performance evaluations show that the proposed approach can produce comparable average vehicle waiting time and reduce the training/learning time of learning adequate traffic light configurations for all intersections within a few seconds, while a deep learning-based approach can be trained in a few days for learning similar light configurations.     

结合状态预测的深度强化学习交通信号控制

深度强化学习（deep reinforcement learning,DRL）可广泛应用于城市交通信号控制领域,但在现有研究中,绝大多数的DRL智能体仅使用当前的交通状态进行决策,在交通流变化较大的情况下控制效果有限。提出一种结合状态预测的DRL信号控制算法。首先,利用独热编码设计简洁且高效的交通状态;然后,使用长短期记忆网络（long short-term memory,LSTM）预测未来的交通状态;最后,智能体根据当前状态和预测状态进行最优决策。在SUMO（simulation of urban mobility）仿真平台上的实验结果表明,在单交叉口、多交叉口的多种交通流量条件下,与三种典型的信号控制算法相比,所提算法在平均等待时间、行驶时间、燃油消耗、CO2排放等指标上都具有最好的性能。     

多边形链求交的改进算法

多边形链求交是CAD&CG及相关领域研究中的一个基本问题 利用多边形链的凸凹性、单调性等特性 ,结合包围盒技术 ,在扫描线算法基础上 ,提出一种多边形链求交的改进算法 该算法特别适用于包含大量直线段且交点数相对于顶点数少得多的多边形链求交的情况     

Pencil curve detection from visibility data

The trajectory of the ball-center point of a ball-end mill slid along a concave-edge region on a part surface becomes a pencil curve, and the ball-end milling along the pencil curve is called pencil curve machining. Presented in the paper is a procedure for computing pencil curves for 3-axis sculptured surface machining. The proposed algorithm traces pencil curves from an offset triangular mesh having numerous intersections (self-intersections). Since the outer skin of an offset triangular mesh makes the valid CL-surface, pencil curves can be obtained by connecting valid intersections lying on the outer skin of the offset mesh. The underlying concept of the proposed algorithm is that visible intersections are always valid for pencil curves. To obtain the visibility data of intersections, the proposed algorithm uses a graphics board, which performs hidden surface removal at a rate of up to a million polygons per second. Various examples have been tested with implementation of the algorithm, and some examples are presented for illustration.     

基于行人安全的交通信号灯智能控制算法研究

提出了一种基于深度确定性策略梯度(DDPG, deep deterministic policy gradient)的行人安全智能交通信号控制算法;通过对交叉口数据的实时观测,综合考虑行人安全与车辆通行效率,智能地调控交通信号周期时长,相位顺序以及相位持续时间,实现交叉路口安全高效的智能控制;同时,采用优先经验回放提高采样效率,加速了算法收敛;由于行人安全与车辆通行效率存在相互矛盾,研究中通过精确地设计强化学习的奖励函数,折中考虑行人违规引起的与车辆的冲突量和车辆通行的速度,引导交通信号灯学习路口行人的行为,学习最佳的配时方案;仿真结果表明在动态环境下,该算法在行人与车辆冲突量,车辆的平均速度、等待时间和队列长度均优于现有的固定配时方案和其他的智能配时方案。     

基于注意力机制的深度强化学习交通信号控制

深度强化学习（DRL）广泛应用于具有高度不确定性的城市交通信号控制问题中,但现有的DRL交通信号控制方法中,仅仅使用传统的深度神经网络,复杂交通场景下其感知能力有限。此外,状态作为强化学习的三要素之一,现有方法中的交通状态也需要人工精心的设计。因此,提出了一种基于注意力机制（attention mechanism）的DRL交通信号控制算法。通过引入注意力机制,使得神经网络自动地关注重要的状态分量以增强网络的感知能力,提升了信号控制效果,并减少了状态向量设计的难度。在SUMO（simulation of urban mobility）仿真平台上的实验结果表明,在单交叉口、多交叉口中,在低、高交通流量条件下,仅仅使用简单的交通状态,与三种基准信号控制算法相比,所提算法在平均等待时间、行驶时间等指标上都具有最好的性能。     

基于改进密度峰值聚类的路网划分方法

城市路网的合理划分对于优化区域交通控制以及协调策略的实施具有重要意义。为提高道路通行效率,提出基于密度峰值聚类算法的城市路网划分方法,首先,综合考虑交叉口静态和动态因素的影响,构建相邻交叉口的关联度模型,为合理量化交叉口之间的关联程度提供定量描述。其次,提出改进的密度峰值聚类算法,结合相邻交叉口之间的关联度对路网区域进行划分。针对密度峰值聚类算法中局部密度在不同规模数据集上差异较大的问题,引入KNN的思想,重新对局部密度进行描述,其次为避免算法聚类中心人工选取的主观性导致的误差问题,采用肘部法则实现聚类中心的自动选取。实验结果表明,与改进的Newman算法及Ncut算法相比,提出的改进算法在优化子区平均匀质度上可分别降低12.5%和22.8%,提高了控制子区的划分效果,使区域划分效果更合理。     

基于深度强化学习的交通信号控制方法

交通信号的智能控制是智能交通研究中的热点问题。为更加及时有效地自适应协调交通,文中提出了一种基于分布式深度强化学习的交通信号控制模型,采用深度神经网络框架,利用目标网络、双Q网络、价值分布提升模型表现。将交叉路口的高维实时交通信息离散化建模并与相应车道上的等待时间、队列长度、延迟时间、相位信息等整合作为状态输入,在对相位序列及动作、奖励做出恰当定义的基础上,在线学习交通信号的控制策略,实现交通信号Agent的自适应控制。为验证所提算法,在SUMO(Simulation of Urban Mobility)中相同设置下,将其与3种典型的深度强化学习算法进行对比。实验结果表明,基于分布式的深度强化学习算法在交通信号Agent的控制中具有更好的效率和鲁棒性,且在交叉路口车辆的平均延迟、行驶时间、队列长度、等待时间等方面具有更好的性能表现。     

An iterative/subdivision hybrid algorithm for?curve/curve?intersection

The problem of finding all intersections between two space curves is one of the fundamental problems in computer-aided geometric design and computational geometry. This article proposes a new iterative/subdivision hybrid algorithm for this problem. We use a test based on Kantorovich’s theorem to detect the starting point from which Newton’s method converges quadratically and a subdivision scheme to exclude certain regions that do not contain any intersections. Our algorithm is guaranteed to detect all intersections in the domain for nondegenerate and non-ill-posed cases.