Search

We study the problem of clock synchronization in a networked system with arbitrary starts for all nodes. We consider a synchronous network of $n$ nodes, where each node has a local clock that is an integer counter. Eventually, clocks must be all equal and increase by one in each round modulo some period $P$. The purpose of this paper is to study whether clock synchronization can be achieved with bounded memory, that is every node maintains a number of states that does not depend on the network size. In particular, we are interested in clock synchronization algorithms which work in dynamic networks, i.e., tolerate that communication links continuously fail and come-up. We first focus on self-stabilizing solutions for clock synchronization, and prove that there is no such algorithm that is bounded memory, even in the case of static networks. More precisely, we show a lower bound of $n+1$ states at each node required to achieve clock synchronization in static strongly connected networks with at most $n$ nodes, and derive a lower bound of $n-2$ rounds on synchronization time, in the worst case. We then prove that, when the self-stabilizing requirement is removed, the impossibility of clock synchronization with bounded memory still holds in the dynamic setting: every solution for the clock synchronization problem in dynamic networks with at most $n$ nodes requires each node to have $\Omega(\log n)$ states.

We consider the fundamental problem of clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually indicate the same value. Previous algorithms worked in static networks with drastic connectivity properties and assumed that global information is available at each agent. In this paper, we propose different solutions for time-varying topologies that require neither strong connectivity nor any global knowledge on the network. First, we study the case of unbounded clocks, and propose a self-stabilizing $MinMax$ algorithm that works if, in each sufficiently long but bounded period of time, there is an agent, called a root, that can send messages, possibly indirectly, to all other agents. Such networks are highly dynamic in the sense that roots may change arbitrarily over time. Moreover, the bound on the time required for achieving this rootedness property is unknown to the agents. Then we present a finite-state algorithm that synchronizes periodic clocks in dynamic networks that are strongly connected over bounded period of time. Here also, the bound on the time for achieving strong connectivity exists, but is not supposed to be known. Interestingly, our algorithm unifies several seemingly different algorithms proposed previously for static networks. Next, we show that strong connectivity is actually not required: our algorithm still works when the network is just rooted over bounded period of time with a set of roots that becomes stable. Finally, we study the time and space complexities of our algorithms, and discuss how initial timing information allows for more efficient solutions.

This memoir is devoted to the study of formal-analytic arithmetic surfaces. These are arithmetic counterparts, in the context of Arakelov geometry, of germs of smooth complex-analytic surfaces along a projective complex curve. Formal-analytic surfaces provide a natural framework for arithmetic algebraization theorems, old and new. Formal-analytic arithmetic surfaces admit a rich geometry which parallels the geometry of complex analytic surfaces. Notably the dichotomy between pseudoconvexity and pseudoconcavity plays a central role in their geometry. Our study of formal-analytic arithmetic surfaces relies crucially on the use of real-valued invariants. Some of these are intersection-theoretic, in the spirit of Arakelov intersection theory. Some other invariants involve infinite-dimensional geometry of numbers. Relating our new intersection-theoretic invariants to more classical invariants of Arakelov geometry leads us to investigate a new invariant, the Archimedean overflow, attached to an analytic map from a pointed compact Riemann surface with boundary to a Riemann surface. It is related to the characteristic functions of Nevanlinna theory. Our results on the geometry of formal-analytic arithmetic surfaces admit applications to concrete problems of arithmetic geometry. Notably we generalize the arithmetic holonomicity theorem of Calegari-Dimitrov-Tang regarding the dimension of spaces of power series with integral coefficients satisfying some convergence conditions. We also establish an arithmetic counterpart of theorems of Lefschetz and Nori by providing a bound on the index, in the \'etale fundamental group of an arithmetic surface, of the closed subgroup generated by the \'etale fundamental groups of some arithmetic curve and of some compact Riemann surfaces mapping to the arithmetic surface., Comment: 189 pages, comments welcome. Figures added. Numerous typos corrected. Contents of Sections 4.4, 6.2, 9.1 and 9.2 of Version 1 corrected and completed

In Multi-Task Learning (MTL), it is a common practice to train multi-task networks by optimizing an objective function, which is a weighted average of the task-specific objective functions. Although the computational advantages of this strategy are clear, the complexity of the resulting loss landscape has not been studied in the literature. Arguably, its optimization may be more difficult than a separate optimization of the constituting task-specific objectives. In this work, we investigate the benefits of such an alternative, by alternating independent gradient descent steps on the different task-specific objective functions and we formulate a novel way to combine this approach with state-of-the-art optimizers. As the separation of task-specific objectives comes at the cost of increased computational time, we propose a random task grouping as a trade-off between better optimization and computational efficiency. Experimental results over three well-known visual MTL datasets show better overall absolute performance on losses and standard metrics compared to an averaged objective function and other state-of-the-art MTL methods. In particular, our method shows the most benefits when dealing with tasks of different nature and it enables a wider exploration of the shared parameter space. We also show that our random grouping strategy allows to trade-off between these benefits and computational efficiency.

When networked systems of autonomous agents carry out complex tasks, the control and coordination sought after generally depend on a few fundamental control primitives. Chief among these primitives is consensus, where agents are to converge to a common estimate within the range of initial values, which becomes average consensus when the joint limit should be the average of the initial values. To provide reliable services that are easy to deploy, these primitives should operate even when the network is subject to frequent and unpredictable changes. Moreover, they should mobilize few computational resources so that low powered, deterministic, and anonymous agents can partake in the network. In this stringent adversarial context, we investigate the distributed implementation of these primitives over networks with bidirectional, but potentially short-lived, communication links. Inspired by the classic EqualNeighbor and Metropolis agreement rules for multi-agent systems, we design distributed algorithms for consensus and average consensus, which we show to operate in polynomial time in a synchronous temporal model. These algorithms are fully distributed, requiring neither symmetry-breaking devices such as unique identifiers, nor global control or knowledge of the network. Our strategy consists in making agents learn simple structural parameters of the network -- namely, their largest degrees -- which constitutes enough information to build simple update rules, implementable locally with little computational and memory overhead.

We develop a generic method for bounding the convergence rate of an averaging algorithm running in a multi-agent system with a time-varying network, where the associated stochastic matrices have a time-independent Perron vector. This method provides bounds on convergence rates that unify and refine most of the previously known bounds. They depend on geometric parameters of the dynamic communication graph such as the normalized diameter or the bottleneck measure. As corollaries of these geometric bounds, we show that the convergence rate of the Metropolis algorithm in a system of $n$ agents is less than $1-1/4n^2$ with any communication graph that may vary in time, but is permanently connected and bidirectional. We prove a similar upper bound for the EqualNeighbor algorithm under the additional assumptions that the number of neighbors of each agent is constant and that the communication graph is not too irregular. Moreover our bounds offer improved convergence rates for several averaging algorithms and specific families of communication graphs. Finally we extend our methodology to a time-varying Perron vector and show how convergence times may dramatically degrade with even limited variations of Perron vectors.

Multi-task learning has gained popularity due to the advantages it provides with respect to resource usage and performance. Nonetheless, the joint optimization of parameters with respect to multiple tasks remains an active research topic. Sub-partitioning the parameters between different tasks has proven to be an efficient way to relax the optimization constraints over the shared weights, may the partitions be disjoint or overlapping. However, one drawback of this approach is that it can weaken the inductive bias generally set up by the joint task optimization. In this work, we present a novel way to partition the parameter space without weakening the inductive bias. Specifically, we propose Maximum Roaming, a method inspired by dropout that randomly varies the parameter partitioning, while forcing them to visit as many tasks as possible at a regulated frequency, so that the network fully adapts to each update. We study the properties of our method through experiments on a variety of visual multi-task data sets. Experimental results suggest that the regularization brought by roaming has more impact on performance than usual partitioning optimization strategies. The overall method is flexible, easily applicable, provides superior regularization and consistently achieves improved performances compared to recent multi-task learning formulations., Comment: Accepted at the 35th AAAI Conference on Artificial Intelligence (AAAI 2021)

For over a decade, TV series have been drawing increasing interest, both from the audience and from various academic fields. But while most viewers are hooked on the continuous plots of TV serials, the few annotated datasets available to researchers focus on standalone episodes of classical TV series. We aim at filling this gap by providing the multimedia/speech processing communities with Serial Speakers, an annotated dataset of 161 episodes from three popular American TV serials: Breaking Bad, Game of Thrones and House of Cards. Serial Speakers is suitable both for investigating multimedia retrieval in realistic use case scenarios, and for addressing lower level speech related tasks in especially challenging conditions. We publicly release annotations for every speech turn (boundaries, speaker) and scene boundary, along with annotations for shot boundaries, recurring shots, and interacting speakers in a subset of episodes. Because of copyright restrictions, the textual content of the speech turns is encrypted in the public version of the dataset, but we provide the users with a simple online tool to recover the plain text from their own subtitle files.

In recent years, representation learning approaches have disrupted many multimedia computing tasks. Among those approaches, deep convolutional neural networks (CNNs) have notably reached human level expertise on some constrained image classification tasks. Nonetheless, training CNNs from scratch for new task or simply new data turns out to be complex and time-consuming. Recently, transfer learning has emerged as an effective methodology for adapting pre-trained CNNs to new data and classes, by only retraining the last classification layer. This paper focuses on improving this process, in order to better transfer knowledge between CNN architectures for faster trainings in the case of fine tuning for image classification. This is achieved by combining and transfering supplementary weights, based on similarity considerations between source and target classes. The study includes a comparison between semantic and content-based similarities, and highlights increased initial performances and training speed, along with superior long term performances when limited training samples are available.

These are the notes of lectures delivered at Grenoble's summer school on \emph{Arakelov Geo\-me\-try and Diophantine Applications}, in June 2017. They constitute an introduction to the study of Euclidean lattices and of their invariants defined in terms of theta series. Recall that Euclidean lattice is defined as a pair $\bar{E}:= (E, \Vert .\Vert)$ where $E$ is some free $\mathbb{Z}$-module of finite rank $E$ and $\Vert. \Vert$ is some Euclidean norm on the real vector space $E_\mathbb{R} := E \otimes \mathbb{R}$. The most basic of these invariants is the non-negative real number: $$h^0_\theta(\bar{E}) := \log \sum_{v \in E} e^{- \pi \Vert v \Vert^2}.$$ In these notes, we explain how such invariants naturally arise when one investigates basic questions concerning classical invariants of Euclidean lattices, such as their successive minima, their covering radius, or the number of lattice points in balls of a given radius. We notably discuss their significance from the perspective of Arakelov geometry and of the analogy between number fields and function fields, their role (discovered by Banaszczyk) in the derivation of optimal transference estimates, and their interpretation in terms of the formalism of statistical thermodynamics. These notes have been primarily written for an audience of arithmetic geometers, but should also be suited to a wider circle of mathematicians and theoretical physicists with some interest in Euclidean lattices or in the mathematical foundations of statistical physics., Comment: Notes of lectures at the summer school "Arakelov Geometry and Diophantine applications" held in June 2017 in Grenoble; 71 pages

Today's popular TV series tend to develop continuous, complex plots spanning several seasons, but are often viewed in controlled and discontinuous conditions. Consequently, most viewers need to be re-immersed in the story before watching a new season. Although discussions with friends and family can help, we observe that most viewers make extensive use of summaries to re-engage with the plot. Automatic generation of video summaries of TV series' complex stories requires, first, modeling the dynamics of the plot and, second, extracting relevant sequences. In this paper, we tackle plot modeling by considering the social network of interactions between the characters involved in the narrative: substantial, durable changes in a major character's social environment suggest a new development relevant for the summary. Once identified, these major stages in each character's storyline can be used as a basis for completing the summary with related sequences. Our algorithm combines such social network analysis with filmmaking grammar to automatically generate character-oriented video summaries of TV series from partially annotated data. We carry out evaluation with a user study in a real-world scenario: a large sample of viewers were asked to rank video summaries centered on five characters of the popular TV series Game of Thrones, a few weeks before the new, sixth season was released. Our results reveal the ability of character-oriented summaries to re-engage viewers in television series and confirm the contributions of modeling the plot content and exploiting stylistic patterns to identify salient sequences.

A character network is a graph extracted from a narrative, in which vertices represent characters and edges correspond to interactions between them. A number of narrative-related problems can be addressed automatically through the analysis of character networks, such as summarization, classification, or role detection. Character networks are particularly relevant when considering works of fictions (e.g. novels, plays, movies, TV series), as their exploitation allows developing information retrieval and recommendation systems. However, works of fiction possess specific properties making these tasks harder. This survey aims at presenting and organizing the scientific literature related to the extraction of character networks from works of fiction, as well as their analysis. We first describe the extraction process in a generic way, and explain how its constituting steps are implemented in practice, depending on the medium of the narrative, the goal of the network analysis, and other factors. We then review the descriptive tools used to characterize character networks, with a focus on the way they are interpreted in this context. We illustrate the relevance of character networks by also providing a review of applications derived from their analysis. Finally, we identify the limitations of the existing approaches, and the most promising perspectives.

In the stabilizing consensus problem, each agent of a networked system has an input value and is repeatedly writing an output value; it is required that eventually all the output values stabilize to the same value which, moreover, must be one of the input values. We study this problem for a synchronous model with identical and anonymous agents that are connected by a time-varying topology. Our main result is a generic MinMax algorithm that solves the stabilizing consensus problem in this model when, in each sufficiently long but bounded period of time, there is an agent, called a root, that can send messages, possibly indirectly, to all the agents. Such topologies are highly dynamic (in particular, roots may change arbitrarily over time) and enforce no strong connectivity property (an agent may be never a root). Our distributed MinMax algorithms require neither central control (e.g., synchronous starts) nor any global information (eg.,on the size of the network), and are quite efficient in terms of message size and storage requirements.

Deep learning is at the core of recent spoken language understanding (SLU) related tasks. More precisely, deep neural networks (DNNs) drastically increased the performances of SLU systems, and numerous architectures have been proposed. In the real-life context of theme identification of telephone conversations, it is common to hold both a human, manual (TRS) and an automatically transcribed (ASR) versions of the conversations. Nonetheless, and due to production constraints, only the ASR transcripts are considered to build automatic classifiers. TRS transcripts are only used to measure the performances of ASR systems. Moreover, the recent performances in term of classification accuracy, obtained by DNN related systems are close to the performances reached by humans, and it becomes difficult to further increase the performances by only considering the ASR transcripts. This paper proposes to distillates the TRS knowledge available during the training phase within the ASR representation, by using a new generative adversarial network called M2H-GAN to generate a TRS-like version of an ASR document, to improve the theme identification performances., Comment: Submitted at INTERSPEECH 2019

This paper deals with the automatic analysis of conversations between a customer and an agent in a call centre of a customer care service. The purpose of the analysis is to hypothesize themes about problems and complaints discussed in the conversation. Themes are defined by the application documentation topics. A conversation may contain mentions that are irrelevant for the application purpose and multiple themes whose mentions may be interleaved portions of a conversation that cannot be well defined. Two methods are proposed for multiple theme hypothesization. One of them is based on a cosine similarity measure using a bag of features extracted from the entire conversation. The other method introduces the concept of thematic density distributed around specific word positions in a conversation. In addition to automatically selected words, word bi-grams with possible gaps between successive words are also considered and selected. Experimental results show that the results obtained with the proposed methods outperform the results obtained with support vector machines on the same data. Furthermore, using the theme skeleton of a conversation from which thematic densities are derived, it will be possible to extract components of an automatic conversation report to be used for improving the service performance. Index Terms: multi-topic audio document classification, hu-man/human conversation analysis, speech analytics, distance bigrams, Comment: arXiv admin note: text overlap with arXiv:1812.07207

Speaker diarization may be difficult to achieve when applied to narrative films, where speakers usually talk in adverse acoustic conditions: background music, sound effects, wide variations in intonation may hide the inter-speaker variability and make audio-based speaker diarization approaches error prone. On the other hand, such fictional movies exhibit strong regularities at the image level, particularly within dialogue scenes. In this paper, we propose to perform speaker diarization within dialogue scenes of TV series by combining the audio and video modalities: speaker diarization is first performed by using each modality, the two resulting partitions of the instance set are then optimally matched, before the remaining instances, corresponding to cases of disagreement between both modalities, are finally processed. The results obtained by applying such a multi-modal approach to fictional films turn out to outperform those obtained by relying on a single modality.

The paper deals with the automatic analysis of real-life telephone conversations between an agent and a customer of a customer care service (ccs). The application domain is the public transportation system in Paris and the purpose is to collect statistics about customer problems in order to monitor the service and decide priorities on the intervention for improving user satisfaction. Of primary importance for the analysis is the detection of themes that are the object of customer problems. Themes are defined in the application requirements and are part of the application ontology that is implicit in the ccs documentation. Due to variety of customer population, the structure of conversations with an agent is unpredictable. A conversation may be about one or more themes. Theme mentions can be interleaved with mentions of facts that are irrelevant for the application purpose. Furthermore, in certain conversations theme mentions are localized in specific conversation segments while in other conversations mentions cannot be localized. As a consequence, approaches to feature extraction with and without mention localization are considered. Application domain relevant themes identified by an automatic procedure are expressed by specific sentences whose words are hypothesized by an automatic speech recognition (asr) system. The asr system is error prone. The word error rates can be very high for many reasons. Among them it is worth mentioning unpredictable background noise, speaker accent, and various types of speech disfluencies. As the application task requires the composition of proportions of theme mentions, a sequential decision strategy is introduced in this paper for performing a survey of the large amount of conversations made available in a given time period. The strategy has to sample the conversations to form a survey containing enough data analyzed with high accuracy so that proportions can be estimated with sufficient accuracy. Due to the unpredictable type of theme mentions, it is appropriate to consider methods for theme hypothesization based on global as well as local feature extraction. Two systems based on each type of feature extraction will be considered by the strategy. One of the four methods is novel. It is based on a new definition of density of theme mentions and on the localization of high density zones whose boundaries do not need to be precisely detected. The sequential decision strategy starts by grouping theme hypotheses into sets of different expected accuracy and coverage levels. For those sets for which accuracy can be improved with a consequent increase of coverage a new system with new features is introduced. Its execution is triggered only when specific preconditions are met on the hypotheses generated by the basic four systems. Experimental results are provided on a corpus collected in the call center of the Paris transportation system known as ratp. The results show that surveys with high accuracy and coverage can be composed with the proposed strategy and systems. This makes it possible to apply a previously published proportion estimation approach that takes into account hypothesization errors .

Speaker diarization of audio streams turns out to be particularly challenging when applied to fictional films, where many characters talk in various acoustic conditions (background music, sound effects, variations in intonation...). Despite this acoustic variability, such movies exhibit specific visual patterns, particularly within dialogue scenes. In this paper, we introduce a two-step method to achieve speaker diarization in TV series: speaker diarization is first performed locally within scenes visually identified as dialogues; then, the hypothesized local speakers are compared to each other during a second clustering process in order to detect recurring speakers: this second stage of clustering is subject to the constraint that the different speakers involved in the same dialogue have to be assigned to different clusters. The performances of our approach are compared to those obtained by standard speaker diarization tools applied to the same data., Comment: in French

Speaker diarization, usually denoted as the ''who spoke when'' task, turns out to be particularly challenging when applied to fictional films, where many characters talk in various acoustic conditions (background music, sound effects...). Despite this acoustic variability , such movies exhibit specific visual patterns in the dialogue scenes. In this paper, we introduce a two-step method to achieve speaker diarization in TV series: a speaker diarization is first performed locally in the scenes detected as dialogues; then, the hypothesized local speakers are merged in a second agglomerative clustering process, with the constraint that speakers locally hypothesized to be distinct must not be assigned to the same cluster. The performances of our approach are compared to those obtained by standard speaker diarization tools applied to the same data.

Identifying and characterizing the dynamics of modern tv series subplots is an open problem. One way is to study the underlying social network of interactions between the characters. Standard dynamic network extraction methods rely on temporal integration, either over the whole considered period, or as a sequence of several time-slices. However, they turn out to be inappropriate in the case of tv series, because the scenes shown onscreen alternatively focus on parallel storylines, and do not necessarily respect a traditional chronology. In this article, we introduce Narrative Smoothing, a novel network extraction method taking advantage of the plot properties to solve some of their limitations. We apply our method to a corpus of 3 popular series, and compare it to both standard approaches. Narrative smoothing leads to more relevant observations when it comes to the characterization of the protagonists and their relationships, confirming its appropriateness to model the intertwined storylines constituting the plots., Comment: arXiv admin note: substantial text overlap with arXiv:1602.07811