We study subtrajectory clustering under the Fr\'echet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a good clustering structure. We approach this problem via a new set cover formulation, which we think provides a natural formalization of the problem as it is studied in many applications. Given a polygonal curve $P$ with $n$ vertices in fixed dimension, integers $k$, $\ell \geq 1$, and a real value $\Delta > 0$, the goal is to find $k$ center curves of complexity at most $\ell$ such that every point on $P$ is covered by a subtrajectory that has small Fr\'echet distance to one of the $k$ center curves ($\leq \Delta$). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter $\ell$. Our main result is a tri-criterial approximation algorithm: if there exists a solution for given parameters $k$, $\ell$, and $\Delta$, then our algorithm finds a set of $k'$ center curves of complexity at most $\ell'$ with covering radius $\Delta'$ with $k' \in O( k \ell^2 \log (k \ell))$, $\ell'\leq 2\ell$, and $\Delta'\leq 19 \Delta$. Moreover, within these approximation bounds, we can minimize $k$ while keeping the other parameters fixed. If $\ell$ is a constant independent of $n$, then, the approximation factor for the number of clusters $k$ is $O(\log k)$ and the approximation factor for the radius $\Delta$ is constant. In this case, the algorithm has expected running time in $ \tilde{O}\left( k m^2 + mn\right)$ and uses space in $O(n+m)$, where $m=\lceil\frac{L}{\Delta}\rceil$ and $L$ is the total arclength of the curve $P$. For the important case of clustering with line segments ($\ell$=2) we obtain bi-criteria approximation algorithms, where the approximation criteria are the number of clusters and the radius of the clustering.
相關內容
We study the optimal batch-regret tradeoff for batch linear contextual bandits. For any batch number $M$, number of actions $K$, time horizon $T$, and dimension $d$, we provide an algorithm and prove its regret guarantee, which, due to technical reasons, features a two-phase expression as the time horizon $T$ grows. We also prove a lower bound theorem that surprisingly shows the optimality of our two-phase regret upper bound (up to logarithmic factors) in the \emph{full range} of the problem parameters, therefore establishing the exact batch-regret tradeoff. Compared to the recent work \citep{ruan2020linear} which showed that $M = O(\log \log T)$ batches suffice to achieve the asymptotically minimax-optimal regret without the batch constraints, our algorithm is simpler and easier for practical implementation. Furthermore, our algorithm achieves the optimal regret for all $T \geq d$, while \citep{ruan2020linear} requires that $T$ greater than an unrealistically large polynomial of $d$. Along our analysis, we also prove a new matrix concentration inequality with dependence on their dynamic upper bounds, which, to the best of our knowledge, is the first of its kind in literature and maybe of independent interest.
In this paper we propose a variant of New Q-Newton's method Backtracking (which is relevant to Levenberg-Marquardt algorithm, but with the argumentation chosen by New Q-Newton's method idea for good theoretical guarantee, and with Backtracking line search added) for to use specifically with systems of m equations in m variables. We fix $\delta _0=0 $ and $\delta _1=2$, and a number $0<\tau <1$. If $A$ is a square matrix, we denote by $minsp(A)=\min \{|\lambda |: $ $\lambda$ is an eigenvalue of $A\}$. Also, we denote by $A^{\intercal}$ the transpose of $A$. Given $F:\mathbb{R}^m\rightarrow \mathbb{R}^m$ a $C^1$ function, we denote by $H(x)=JF(x)$ the Jacobian of $F$, and $f(x)=||F(x)||^2$. If $x\in \mathbb{R}^m$ is such that $F(x)\not= 0$, we define various : $\delta (x)$ be the first element $\delta _j$ in $\{\delta _0,\delta _1\}$ so that $minsp(H(x)+\delta _j||F(x)||^{\tau } )\geq \min \{ ||F(x)||^{\tau},1\}$; $A(x)=H(x)^{\intercal}H(x)+\delta (x)||F(x)||^{\tau }Id$; $w(x)=A(x)^{-1}H(x)^{\intercal}F(x)$; (if $x$ is close to a non-degenerate zero of $F$, then $w(x)=H(x)^{-1}F(x)$ the usual Newton's direction) Note: we can normalise $w(x)/\max \{||w(x)|| ,1\}$ if needed $\gamma (x)$ is chosen from Armijo's Backtracking line search: it is the largest number $\gamma$ among $\{1,1/2,(1/2)^2,\ldots \}$ so that: $f(x-\gamma w(x))-f(x)\leq -\gamma <w(x),H(x)^{\intercal}F(x)>$; The update rule of our method is $x\mapsto x-\gamma (x)w(x)$. Good theoretical guarantees are proven, in particular for systems of polynomial equations. In "generic situations", we will also discuss a way to avoid that the limit of the constructed sequence is a solution of $H(x)^{\intercal}F(x)=0$ but not of $F(x)=0$.
In this work we consider a class of non-linear eigenvalue problems that admit a spectrum similar to that of a Hamiltonian matrix, in the sense that the spectrum is symmetric with respect to both the real and imaginary axis. More precisely, we present a method to iteratively approximate the eigenvalues of such non-linear eigenvalue problems closest to a given purely real or imaginary shift, while preserving the symmetries of the spectrum. To this end the presented method exploits the equivalence between the considered non-linear eigenvalue problem and the eigenvalue problem associated with a linear but infinite-dimensional operator. To compute the eigenvalues closest to the given shift, we apply a specifically chosen shift-invert transformation to this linear operator and compute the eigenvalues with the largest modulus of the new shifted and inverted operator using an (infinite) Arnoldi procedure. The advantage of the chosen shift-invert transformation is that the spectrum of the transformed operator has a "real skew-Hamiltonian"-like structure. Furthermore, it is proven that the Krylov space constructed by applying this operator, satisfies an orthogonality property in terms of a specifically chosen bilinear form. By taking this property into account in the orthogonalization process, it is ensured that even in the presence of rounding errors, the obtained approximation for, e.g., a simple, purely imaginary eigenvalue is simple and purely imaginary. The presented work can thus be seen as an extension of [V. Mehrmann and D. Watkins, "Structure-Preserving Methods for Computing Eigenpairs of Large Sparse Skew-Hamiltonian/Hamiltonian Pencils", SIAM J. Sci. Comput. (22.6), 2001], to the considered class of non-linear eigenvalue problems. Although the presented method is initially defined on function spaces, it can be implemented using finite dimensional linear algebra operations.
Finding a suitable density function is essential for density-based clustering algorithms such as DBSCAN and DPC. A naive density corresponding to the indicator function of a unit $d$-dimensional Euclidean ball is commonly used in these algorithms. Such density suffers from capturing local features in complex datasets. To tackle this issue, we propose a new kernel diffusion density function, which is adaptive to data of varying local distributional characteristics and smoothness. Furthermore, we develop a surrogate that can be efficiently computed in linear time and space and prove that it is asymptotically equivalent to the kernel diffusion density function. Extensive empirical experiments on benchmark and large-scale face image datasets show that the proposed approach not only achieves a significant improvement over classic density-based clustering algorithms but also outperforms the state-of-the-art face clustering methods by a large margin.
Nonlinear trajectory optimization algorithms have been developed to handle optimal control problems with nonlinear dynamics and nonconvex constraints in trajectory planning. The performance and computational efficiency of many trajectory optimization methods are sensitive to the initial guess, i.e., the trajectory guess needed by the recursive trajectory optimization algorithm. Motivated by this observation, we tackle the initialization problem for trajectory optimization via policy optimization. To optimize a policy, we propose a guided policy search method that has two key components: i) Trajectory update; ii) Policy update. The trajectory update involves offline solutions of a large number of trajectory optimization problems from different initial states via Sequential Convex Programming (SCP). Here we take a single SCP step to generate the trajectory iterate for each problem. In conjunction with these iterates, we also generate additional trajectories around each iterate via a feedback control law. Then all these trajectories are used by a stochastic gradient descent algorithm to update the neural network policy, i.e., the policy update step. As a result, the trained policy makes it possible to generate trajectory candidates that are close to the optimality and feasibility and that provide excellent initial guesses for the trajectory optimization methods. We validate the proposed method via a real-world 6-degree-of-freedom powered descent guidance problem for a reusable rocket.
Optimal $k$-thresholding algorithms are a class of sparse signal recovery algorithms that overcome the shortcomings of traditional hard thresholding algorithms caused by the oscillation of the residual function. In this paper, we provide a novel theoretical analysis for the data-time tradeoffs of optimal $k$-thresholding algorithms. Both the analysis and numerical results demonstrate that when the number of measurements is small, the algorithms cannot converge; when the number of measurements is suitably large, the number of measurements required for successful recovery has a negative correlation with the number of iterations and the algorithms can achieve linear convergence. Furthermore, the theory presents that the transition point of the number of measurements is on the order of $k \log({en}/{k})$, where $n$ is the dimension of the target signal.
This work presents a two part framework for online planning and execution of dynamic aerial motions on a quadruped robot. Motions are planned via a centroidal momentum-based nonlinear optimization that is general enough to produce rich sets of novel dynamic motions based solely on the user-specified contact schedule and desired launch velocity of the robot. Since this nonlinear optimization is not tractable for real-time receding horizon control, motions are planned once via nonlinear optimization in preparation of an aerial motion and then tracked continuously using a variational-based optimal controller that offers robustness to the uncertainties that exist in the real hardware such as modeling error or disturbances. Motion planning typically takes between 0.05-0.15 seconds, while the optimal controller finds stabilizing feedback inputs at 500 Hz. Experimental results on the MIT Mini Cheetah demonstrate that the framework can reliably produce successful aerial motions such as jumps onto and off of platforms, spins, flips, barrel rolls, and running jumps over obstacles.
This paper proposes a model-free Reinforcement Learning (RL) algorithm to synthesise policies for an unknown Markov Decision Process (MDP), such that a linear time property is satisfied. We convert the given property into a Limit Deterministic Buchi Automaton (LDBA), then construct a synchronized MDP between the automaton and the original MDP. According to the resulting LDBA, a reward function is then defined over the state-action pairs of the product MDP. With this reward function, our algorithm synthesises a policy whose traces satisfies the linear time property: as such, the policy synthesis procedure is "constrained" by the given specification. Additionally, we show that the RL procedure sets up an online value iteration method to calculate the maximum probability of satisfying the given property, at any given state of the MDP - a convergence proof for the procedure is provided. Finally, the performance of the algorithm is evaluated via a set of numerical examples. We observe an improvement of one order of magnitude in the number of iterations required for the synthesis compared to existing approaches.
Clustering is an essential data mining tool that aims to discover inherent cluster structure in data. For most applications, applying clustering is only appropriate when cluster structure is present. As such, the study of clusterability, which evaluates whether data possesses such structure, is an integral part of cluster analysis. However, methods for evaluating clusterability vary radically, making it challenging to select a suitable measure. In this paper, we perform an extensive comparison of measures of clusterability and provide guidelines that clustering users can reference to select suitable measures for their applications.
During recent years, active learning has evolved into a popular paradigm for utilizing user's feedback to improve accuracy of learning algorithms. Active learning works by selecting the most informative sample among unlabeled data and querying the label of that point from user. Many different methods such as uncertainty sampling and minimum risk sampling have been utilized to select the most informative sample in active learning. Although many active learning algorithms have been proposed so far, most of them work with binary or multi-class classification problems and therefore can not be applied to problems in which only samples from one class as well as a set of unlabeled data are available. Such problems arise in many real-world situations and are known as the problem of learning from positive and unlabeled data. In this paper we propose an active learning algorithm that can work when only samples of one class as well as a set of unlabelled data are available. Our method works by separately estimating probability desnity of positive and unlabeled points and then computing expected value of informativeness to get rid of a hyper-parameter and have a better measure of informativeness./ Experiments and empirical analysis show promising results compared to other similar methods.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191