The syntactic structure of a sentence is often represented using syntactic dependency trees. The sum of the distances between syntactically related words has been in the limelight for the past decades. Research on dependency distances led to the formulation of the principle of dependency distance minimization whereby words in sentences are ordered so as to minimize that sum. Numerous random baselines have been defined to carry out related quantitative studies on languages. The simplest random baseline is the expected value of the sum in unconstrained random permutations of the words in the sentence, namely when all the shufflings of the words of a sentence are allowed and equally likely. Here we focus on a popular baseline: random projective permutations of the words of the sentence, that is, permutations where the syntactic dependency structure is projective, a formal constraint that sentences satisfy often in languages. Thus far, the expectation of the sum of dependency distances in random projective shufflings of a sentence has been estimated approximately with a Monte Carlo procedure whose cost is of the order of $Zn$, where $n$ is the number of words of the sentence and $Z$ is the number of samples; the larger $Z$, the lower the error of the estimation but the larger the time cost. Here we present formulae to compute that expectation without error in time of the order of $n$. Furthermore, we show that star trees maximize it, and devise a dynamic programming algorithm to retrieve the trees that minimize it.
相關內容
The tube method or the volume-of-tube method approximates the tail probability of the maximum of a smooth Gaussian random field with zero mean and unit variance. This method evaluates the volume of a spherical tube about the index set, and then transforms it to the tail probability. In this study, we generalize the tube method to a case in which the variance is not constant. We provide the volume formula for a spherical tube with a non-constant radius in terms of curvature tensors, and the tail probability formula of the maximum of a Gaussian random field with inhomogeneous variance, as well as its Laplace approximation. In particular, the critical radius of the tube is generalized for evaluation of the asymptotic approximation error. As an example, we discuss the approximation of the largest eigenvalue distribution of the Wishart matrix with a non-identity matrix parameter. The Bonferroni method is the tube method when the index set is a finite set. We provide the formula for the asymptotic approximation error for the Bonferroni method when the variance is not constant.
A new format for commutator-free Lie group methods is proposed based on explicit classical Runge-Kutta schemes. In this format exponentials are reused at every stage and the storage is required only for two quantities: the right hand side of the differential equation evaluated at a given Runge-Kutta stage and the function value updated at the same stage. The next stage of the scheme is able to overwrite these values. The result is proven for a 3-stage third order method and a conjecture for higher order methods is formulated. Five numerical examples are provided in support of the conjecture. This new class of structure-preserving integrators has a wide variety of applications for numerically solving differential equations on manifolds.
The Minimum Linear Arrangement problem (MLA) consists of finding a mapping $\pi$ from vertices of a graph to distinct integers that minimizes $\sum_{\{u,v\}\in E}|\pi(u) - \pi(v)|$. In that setting, vertices are often assumed to lie on a horizontal line and edges are drawn as semicircles above said line. For trees, various algorithms are available to solve the problem in polynomial time in $n=|V|$. There exist variants of the MLA in which the arrangements are constrained. Iordanskii, and later Hochberg and Stallmann (HS), put forward $O(n)$-time algorithms that solve the problem when arrangements are constrained to be planar (also known as one-page book embeddings). We also consider linear arrangements of rooted trees that are constrained to be projective (planar embeddings where the root is not covered by any edge). Gildea and Temperley (GT) sketched an algorithm for projective arrangements which they claimed runs in $O(n)$ but did not provide any justification of its cost. In contrast, Park and Levy claimed that GT's algorithm runs in $O(n \log d_{max})$ where $d_{max}$ is the maximum degree but did not provide sufficient detail. Here we correct an error in HS's algorithm for the planar case, show its relationship with the projective case, and derive simple algorithms for the projective and planar cases that run without a doubt in $O(n)$ time.
We study the numerical error in solitary wave solutions of nonlinear dispersive wave equations. A number of existing results for discretizations of solitary wave solutions of particular equations indicate that the error grows quadratically in time for numerical methods that do not conserve energy, but grows only linearly for conservative methods. We provide numerical experiments suggesting that this result extends to a very broad class of equations and numerical methods.
We introduce and illustrate through numerical examples the R package \texttt{SIHR} which handles the statistical inference for (1) linear and quadratic functionals in the high-dimensional linear regression and (2) linear functional in the high-dimensional logistic regression. The focus of the proposed algorithms is on the point estimation, confidence interval construction and hypothesis testing. The inference methods are extended to multiple regression models. We include real data applications to demonstrate the package's performance and practicality.
Regression models in survival analysis based on homogeneous and inhomogeneous phase-type distributions are proposed. The intensity function in this setting plays the role of the hazard function, having the additional benefit of being interpreted in terms of a hidden Markov structure. For unidimensional intensity matrices, we recover the proportional hazards and accelerated failure time models, among others. However, when considering higher dimensions, the proposed methods are only asymptotically equivalent to their classical counterparts and enjoy greater flexibility in the body of the distribution. For their estimation, the latent path representation of inhomogeneous Markov models is exploited. Consequently, an adapted EM algorithm is provided for which the likelihood increases at each iteration. Several examples of practical significance and relevant extensions are examined. The practical feasibility of the models is illustrated on simulated and real-world datasets.
Blackwell's approachability is a framework where two players, the Decision Maker and the Environment, play a repeated game with vector-valued payoffs. The goal of the Decision Maker is to make the average payoff converge to a given set called the target. When this is indeed possible, simple algorithms which guarantee the convergence are known. This abstract tool was successfully used for the construction of optimal strategies in various repeated games, but also found several applications in online learning. By extending an approach proposed by (Abernethy et al., 2011), we construct and analyze a class of Follow the Regularized Leader algorithms (FTRL) for Blackwell's approachability which are able to minimize not only the Euclidean distance to the target set (as it is often the case in the context of Blackwell's approachability) but a wide range of distance-like quantities. This flexibility enables us to apply these algorithms to closely minimize the quantity of interest in various online learning problems. In particular, for regret minimization with $\ell_p$ global costs, we obtain the first bounds with explicit dependence in $p$ and the dimension $d$.
The existence of immune or cured individuals in a population and whether there is sufficient followup in a sample of censored observations on their lifetimes to be confident of their presence are questions of major importance in medical survival analysis. So far only a few candidates have been put forward as possible test statistics for the existence of sufficient followup in a sample. Here we investigate one such statistic and give a detailed analysis, obtaining an exact finite sample as well as asymptotic distributions for it, and use these to calculate the power of the test as a function of the followup in the sample.
We are interested in embedding trees T with maximum degree at most four in a rectangular grid, such that the vertices of T correspond to grid points, while edges of T correspond to non-intersecting straight segments of the grid lines. Such embeddings are called straight models. While each edge is represented by a straight segment, a path of T is represented in the model by the union of the segments corresponding to its edges, which may consist of a path in the model having several bends. The aim is to determine a straight model of a given tree T minimizing the maximum number of bends over all paths of T. We provide a quadratic-time algorithm for this problem. We also show how to construct straight models that have k as its minimum number of bends and with the least number of vertices possible. As an application of our algorithm, we provide an upper bound on the number of bends of EPG models of graphs that are both VPT and EPT.
This paper focuses on the discrimination capacity of aggregation functions: these are the permutation invariant functions used by graph neural networks to combine the features of nodes. Realizing that the most powerful aggregation functions suffer from a dimensionality curse, we consider a restricted setting. In particular, we show that the standard sum and a novel histogram-based function have the capacity to discriminate between any fixed number of inputs chosen by an adversary. Based on our insights, we design a graph neural network aiming, not to maximize discrimination capacity, but to learn discriminative graph representations that generalize well. Our empirical evaluation provides evidence that our choices can yield benefits to the problem of structural graph classification.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191