Search

Modern artificial intelligence (AI) systems are powered by foundation models. This paper presents a new set of foundation models, called Llama 3. It is a herd of language models that natively support multilinguality, coding, reasoning, and tool usage. Our largest model is a dense Transformer with 405B parameters and a context window of up to 128K tokens. This paper presents an extensive empirical evaluation of Llama 3. We find that Llama 3 delivers comparable quality to leading language models such as GPT-4 on a plethora of tasks. We publicly release Llama 3, including pre-trained and post-trained versions of the 405B parameter language model and our Llama Guard 3 model for input and output safety. The paper also presents the results of experiments in which we integrate image, video, and speech capabilities into Llama 3 via a compositional approach. We observe this approach performs competitively with the state-of-the-art on image, video, and speech recognition tasks. The resulting models are not yet being broadly released as they are still under development.

Active learning can improve the efficiency of training prediction models by identifying the most informative new labels to acquire. However, non-response to label requests can impact active learning's effectiveness in real-world contexts. We conceptualise this degradation by considering the type of non-response present in the data, demonstrating that biased non-response is particularly detrimental to model performance. We argue that biased non-response is likely in contexts where the labelling process, by nature, relies on user interactions. To mitigate the impact of biased non-response, we propose a cost-based correction to the sampling strategy--the Upper Confidence Bound of the Expected Utility (UCB-EU)--that can, plausibly, be applied to any active learning algorithm. Through experiments, we demonstrate that our method successfully reduces the harm from labelling non-response in many settings. However, we also characterise settings where the non-response bias in the annotations remains detrimental under UCB-EU for specific sampling methods and data generating processes. Finally, we evaluate our method on a real-world dataset from an e-commerce platform. We show that UCB-EU yields substantial performance improvements to conversion models that are trained on clicked impressions. Most generally, this research serves to both better conceptualise the interplay between types of non-response and model improvements via active learning, and to provide a practical, easy-to-implement correction that mitigates model degradation.

Cataloguing specific URLs, posts, and applications with digital traces is the new best practice for measuring media use and content consumption. Despite the apparent accuracy that comes with greater granularity, however, digital traces may introduce additional ambiguity and new errors into the measurement of media use. In this note, we identify three new measurement challenges when using Digital Trace Data that were recently uncovered using a new measurement framework - Screenomics - that records media use at the granularity of individual screenshots obtained every few seconds as people interact with mobile devices. We label the considerations as follows: (1) entangling - the common measurement error introduced by proxying exposure to content by exposure to format; (2) flattening - aggregating unique segments of media interaction without incorporating temporal information, most commonly intraindividually and (3) bundling - summation of the durations of segments of media interaction, indiscriminate with respect to variations across media segments., Comment: 15 pages with refs, 1 figure, 1 table

Allocation and planning with a collection of tasks and a group of agents is an important problem in multiagent systems. One commonly faced bottleneck is scalability, as in general the multiagent model increases exponentially in size with the number of agents. We consider the combination of random task assignment and multiagent planning under multiple-objective constraints, and show that this problem can be decentralised to individual agent-task models. We present an algorithm of point-oriented Pareto computation, which checks whether a point corresponding to given cost and probability thresholds for our formal problem is feasible or not. If the given point is infeasible, our algorithm finds a Pareto-optimal point which is closest to the given point. We provide the first multi-objective model checking framework that simultaneously uses GPU and multi-core acceleration. Our framework manages CPU and GPU devices as a load balancing problem for parallel computation. Our experiments demonstrate that parallelisation achieves significant run time speed-up over sequential computation.

DoS and DDoS attacks are widely used and pose a constant threat. Here we explore Probability Packet Marking (PPM), one of the important methods for reconstructing the attack-graph and detect the attackers. We present two algorithms. Differently from others, their stopping time is not fixed a priori. It rather depends on the actual distance of the attacker from the victim. Our first algorithm returns the graph at the earliest feasible time, and turns out to guarantee high success probability. The second algorithm enables attaining any predetermined success probability at the expense of a longer runtime. We study the performance of the two algorithms theoretically, and compare them to other algorithms by simulation. Finally, we consider the order in which the marks corresponding to the various edges of the attack graph are obtained by the victim. We show that, although edges closer to the victim tend to be discovered earlier in the process than farther edges, the differences are much smaller than previously thought., Comment: 30 pages, 4 figures, 4 tables

We tackle some fundamental problems in probability theory on corrupted random processes on the integer line. We analyze when a biased random walk is expected to reach its bottommost point and when intervals of integer points can be detected under a natural model of noise. We apply these results to problems in learning thresholds and intervals under a new model for learning under adversarial design., Comment: 18 pages

A $t$-spanner of a graph $G$ is a subgraph $H$ in which all distances are preserved up to a multiplicative $t$ factor. A classical result of Alth\"ofer et al. is that for every integer $k$ and every graph $G$, there is a $(2k-1)$-spanner of $G$ with at most $O(n^{1+1/k})$ edges. But for some settings the more interesting notion is not the number of edges, but the degrees of the nodes. This spurred interest in and study of spanners with small maximum degree. However, this is not necessarily a robust enough objective: we would like spanners that not only have small maximum degree, but also have "few" nodes of "large" degree. To interpolate between these two extremes, in this paper we initiate the study of graph spanners with respect to the $\ell_p$-norm of their degree vector, thus simultaneously modeling the number of edges (the $\ell_1$-norm) and the maximum degree (the $\ell_{\infty}$-norm). We give precise upper bounds for all ranges of $p$ and stretch $t$: we prove that the greedy $(2k-1)$-spanner has $\ell_p$ norm of at most $\max(O(n), O(n^{(k+p)/(kp)}))$, and that this bound is tight (assuming the Erd\H{o}s girth conjecture). We also study universal lower bounds, allowing us to give "generic" guarantees on the approximation ratio of the greedy algorithm which generalize and interpolate between the known approximations for the $\ell_1$ and $\ell_{\infty}$ norm. Finally, we show that at least in some situations, the $\ell_p$ norm behaves fundamentally differently from $\ell_1$ or $\ell_{\infty}$: there are regimes ($p=2$ and stretch $3$ in particular) where the greedy spanner has a provably superior approximation to the generic guarantee.

A significant proportion of individuals' daily activities is experienced through digital devices. Smartphones in particular have become one of the preferred interfaces for content consumption and social interaction. Identifying the content embedded in frequently-captured smartphone screenshots is thus a crucial prerequisite to studies of media behavior and health intervention planning that analyze activity interplay and content switching over time. Screenshot images can depict heterogeneous contents and applications, making the a priori definition of adequate taxonomies a cumbersome task, even for humans. Privacy protection of the sensitive data captured on screens means the costs associated with manual annotation are large, as the effort cannot be crowd-sourced. Thus, there is need to examine utility of unsupervised and semi-supervised methods for digital screenshot classification. This work introduces the implications of applying clustering on large screenshot sets when only a limited amount of labels is available. In this paper we develop a framework for combining K-Means clustering with Active Learning for efficient leveraging of labeled and unlabeled samples, with the goal of discovering latent classes and describing a large collection of screenshot data. We tested whether SVM-embedded or XGBoost-embedded solutions for class probability propagation provide for more well-formed cluster configurations. Visual and textual vector representations of the screenshot images are derived and combined to assess the relative contribution of multi-modal features to the overall performance., Comment: 10 pages

We show that certain vertex algebras without vacuum vector may be embedded into vertex algebras. The result is a partial analogue of the simple classical fact that any rng can be embedded into a ring. A one-line proof of the case of a vacuum-free vertex algebra (whose vertex operator map is by definition injective) appeared in Robinson (2010) using a powerful result from the representation theory of vertex algebras as algebras of mutually local weak vertex operators. Here we present a more elementary proof of a somewhat more general case. We also show that our constructions are canonical., Comment: 23 pages

Using some new logarithmic formal calculus, we construct a well known vertex algebra, obtaining the Jacobi identity directly, in an essentially self-contained treatment., Comment: 14 pages, typos corrected, reference added

We calculate the formal analytic expansions of certain formal translations in a space of formal iterated logarithmic and exponential variables. The results show how the algebraic structure naturally involves the Stirling numbers of the first and second kinds, and certain extensions of these, which appear as expansion coefficients., Comment: 24 pages

We prove a recursive identity involving formal iterated logarithms and formal iterated exponentials. These iterated logarithms and exponentials appear in a natural extension of the logarithmic formal calculus used in the study of logarithmic intertwining operators and logarithmic tensor category theory for modules for a vertex operator algebra. This extension has a variety of interesting arithmetic properties. We develop one such result here, the aforementioned recursive identity. We have applied this identity elsewhere to certain formal series expansions related to a general formal Taylor theorem and these series expansions in turn yield a sequence of combinatorial identities which have as special cases certain classical combinatorial identities involving (separately) the Stirling numbers of the first and second kinds., Comment: 8 pages

In this paper we use the viewpoint of the formal calculus underlying vertex operator algebra theory to study certain aspects of the classical umbral calculus and we introduce and study certain operators generalizing the classical umbral shifts. We begin by calculating the exponential generating function of the higher derivatives of a composite function, following a short, elementary proof which naturally arose as a motivating computation related to a certain crucial "associativity" property of an important class of vertex operator algebras. Very similar (somewhat forgotten) proofs had appeared by the 19-th century, of course without any motivation related to vertex operator algebras. Using this formula, we derive certain results, including especially the calculation of certain adjoint operators, of the classical umbral calculus. This is, roughly speaking, a reversal of the logical development of some standard treatments, which have obtained formulas for the higher derivatives of a composite function, most notably Fa\`a di Bruno's formula, as a consequence of umbral calculus. We set our results in the context of some standard material in what seems a natural fashion given our point of view. We also show a connection between the Virasoro algebra and the classical umbral shifts. This leads naturally to a more general class of operators, which we introduce, and which include the classical umbral shifts as a special case. We prove a few basic facts about these operators., Comment: 30 pages. Major revisions and abridgements, referees comments addressed, references added

We discuss certain aspects of the formal calculus used to describe vertex algebras. In the standard literature on formal calculus, the expression $(x+y)^{n}$, where $n$ is not necessarily a nonnegative integer, is defined as the formal Taylor series given by the binomial series in nonnegative powers of the second-listed variable (namely, $y$). We present a viewpoint that for some purposes of generalization of the formal calculus including and beyond "logarithmic formal calculus", it seems useful, using the formal Taylor theorem as a guide, to instead take as the definition of $(x+y)^{n}$ the formal series which is the result of acting on $x^{n}$ by a formal translation operator, a certain exponentiated derivation. These differing approaches are equivalent, and in the standard generality of formal calculus or logarithmic formal calculus there is no reason to prefer one approach over the other. However, using this second point of view, we may more easily, and in fact do, consider extensions in two directions, sometimes in conjunction. The first extension is to replace $x^{n}$ by more general objects such as the formal variable $\log x$, which appears in the logarithmic formal calculus, and also, more interestingly, by iterated-logarithm expressions. The second extension is to replace the formal translation operator by a more general formal change of variable operator. In addition, we note some of the combinatorics underlying the formal calculus which we treat, and we end by briefly mentioning a connection to Fa\`a di Bruno's classical formula for the higher derivatives of a composite function and the classical umbral calculus. Many of these results are extracted from more extensive papers \cite{R1} and \cite{R2}, to appear., Comment: 14 pages, To appear in the Proceedings of the Conference on Vertex Operator Algebras edited by: Maarten Bergvelt, Gaywalee Yamskulna, and Wenhua Zhao; reference added

We discuss the axioms for vertex algebras and their modules, using formal calculus. Following certain standard treatments, we take the Jacobi identity as our main axiom and we recall weak commutativity and weak associativity. We derive a third, companion property that we call "weak skew-associativity." This third property in some sense completes an $\mathcal{S}_{3}$-symmetry of the axioms, which is related to the known $\mathcal{S}_{3}$-symmetry of the Jacobi identity. We do not initially require a vacuum vector, which is analogous to not requiring an identity element in ring theory. In this more general setting, one still has a property, occasionally used in standard treatments, which is closely related to skew-symmetry, which we call "vacuum-free skew-symmetry." We show how certain combinations of these properties are equivalent to the Jacobi identity for both vacuum-free vertex algebras and their modules. We then specialize to the case with a vacuum vector and obtain further replacement axioms. In particular, in the final section we derive our main result, which says that, in the presence of certain minor axioms, the Jacobi identity for a module is equivalent to either weak associativity or weak skew-associativity. The first part of this result has previously appeared and been used to show the (nontrivial) equivalence of representations of and modules for a vertex algebra. Many but not all of our results appear in standard treatments; some of our arguments are different from the usual ones., Comment: 31 pages, to appear in Journal of Pure & Applied Algebra. v3: no changes

Dreidel is a popular game played during the festival of Chanukah. Players start with an equal number of tokens, donate one token each to a common pot, and take turns spinning a four-sided top, called the dreidel. Depending on the side showing up, the spinner takes all the tokens in the pot, takes half the tokens in the pot, gives a token to the pot, or does nothing. Whenever the pot goes empty, everyone donates a token to the pot. The game continues till all players, except one, go broke. We prove that the expected length of a game of dreidel is at most quadratic in the number of tokens, irrespective of the number of players. This proves a conjecture of Doron Zeilberger.