OpenRaiser/Intern-Atlas huggingface dataset:
Duluth at SemEval-2017 Task 6: Language Models in Humor Detection
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the Duluth system that participated in SemEval-2017 Task 6 #HashtagWars: Learning a Sense of Humor. The system participated in Subtasks A and B using N-gram language models, ranking highly in the task evaluation. This paper discusses the results of our system in the development and evaluation stages and from two post-evaluation runs.
Sparse Hierachical Extrapolated Parametric Methods for Cortical Data Analysis
Venue: arXiv cs.CV 2017
Year: 2017

Many neuroimaging studies focus on the cortex, in order to benefit from better signal to noise ratios and reduced computational burden. Cortical data are usually projected onto a reference mesh, where subsequent analyses are carried out. Several multiscale approaches have been proposed for analyzing these surface data, such as spherical harmonics and graph wavelets. As far as we know, however, the hierarchical structure of the template icosahedral meshes used by most neuroimaging software has never been exploited for cortical data factorization. In this paper, we demonstrate how the structure of the ubiquitous icosahedral meshes can be exploited by data factorization methods such as sparse dictionary learning, and we assess the optimization speed-up offered by extrapolation methods in this context. By testing different sparsity-inducing norms, extrapolation methods, and factorization schemes, we compare the performances of eleven methods for analyzing four datasets: two structural and two functional MRI datasets obtained by processing the data publicly available for the hundred unrelated subjects of the Human Connectome Project. Our results demonstrate that, depending on the level of details requested, a speedup of several orders of magnitudes can be obtained.
An expressive completeness theorem for coalgebraic modal mu-calculi
Venue: arXiv cs.LO 2017
Year: 2017

Generalizing standard monadic second-order logic for Kripke models, we introduce monadic second-order logic interpreted over coalgebras for an arbitrary set functor. We then consider invariance under behavioral equivalence of MSO-formulas. More specifically, we investigate whether the coalgebraic mu-calculus is the bisimulation-invariant fragment of the monadic second-order language for a given functor. Using automatatheoretic techniques and building on recent results by the third author, we show that in order to provide such a characterization result it suffices to find what we call an adequate uniform construction for the coalgebraic type functor. As direct applications of this result we obtain a partly new proof of the Janin-Walukiewicz Theorem for the modal mu-calculus, avoiding the use of syntactic normal forms, and bisimulation invariance results for the bag functor (graded modal logic) and all exponential polynomial functors (including the "game functor"). As a more involved application, involving additional non-trivial ideas, we also derive a characterization theorem for the monotone modal mu-calculus, with respect to a natural monadic second-order language for monotone neighborhood models.
Action Understanding with Multiple Classes of Actors
Venue: arXiv cs.CV 2017
Year: 2017

Despite the rapid progress, existing works on action understanding focus strictly on one type of action agent, which we call actor---a human adult, ignoring the diversity of actions performed by other actors. To overcome this narrow viewpoint, our paper marks the first effort in the computer vision community to jointly consider algorithmic understanding of various types of actors undergoing various actions. To begin with, we collect a large annotated Actor-Action Dataset (A2D) that consists of 3782 short videos and 31 temporally untrimmed long videos. We formulate the general actor-action understanding problem and instantiate it at various granularities: video-level single- and multiple-label actor-action recognition, and pixel-level actor-action segmentation. We propose and examine a comprehensive set of graphical models that consider the various types of interplay among actors and actions. Our findings have led us to conclusive evidence that the joint modeling of actor and action improves performance over modeling each of them independently, and further improvement can be obtained by considering the multi-scale natural in video understanding. Hence, our paper concludes the argument of the value of explicit consideration of various actors in comprehensive action understanding and provides a dataset and a benchmark for later works exploring this new problem.
The computational complexity of the initial value problem for the three body problem
Venue: arXiv cs.CC 2017
Year: 2017

The paper is concerned with the computational complexity of the initial value problem (IVP) for a system of ordinary dynamical equations. Formal problem statement is given, containing a Turing machine with an oracle for getting the initial values as real numbers. It is proven that the computational complexity of the IVP for the three body problem is not bounded by a polynomial. The proof is based on the analysis of oscillatory solutions of the Sitnikov problem that have complex dynamical behavior. These solutions contradict the existence of an algorithm that solves the IVP in polynomial time.
Spectral-Efficient Analog Precoding for Generalized Spatial Modulation Aided MmWave MIMO
Venue: arXiv cs.IT 2017
Year: 2017

Generalized spatial modulation (GenSM) aided millimeter wave (mmWave) multiple-input multiple-output (MIMO) has recently received substantial academic attention. However, due to the insufficient exploitation of the transmitter's knowledge of the channel state information (CSI), the achievable rates of state-of-the-art GenSM-aided mmWave MIMO systems are far from being optimal. Against this background, a novel analog precoding scheme is proposed in this paper to improve the spectral efficiency (SE) of conventional GenSM-aided mmWave MIMOs. More specifically, we firstly manage to lower-bound the achievable SE of GenSM-aided mmWave MIMO with a closed-form expression. Secondly, by exploiting this lower bound as a cost function, a low-complexity iterative algorithm is proposed to design the analog precoder for SE maximization. Finally, numerical simulations are conducted to substantiate the superior performance of the proposed design with respect to state-of-the-art GenSM-aided mmWave MIMO schemes.
Fuel-Efficient En Route Formation of Truck Platoons
Venue: arXiv cs.SY 2017
Year: 2017

The problem of how to coordinate a large fleet of trucks with given itinerary to enable fuel-efficient platooning is considered. Platooning is a promising technology that enables trucks to save significant amounts of fuel by driving close together and thus reducing air drag. A setting is considered in which each truck in a fleet is provided with a start location, a destination, a departure time, and an arrival deadline from a higher planning level. Fuel-efficient plans should be computed. The plans consist of routes and speed profiles that allow trucks to arrive by their arrival deadlines. Hereby, trucks can meet on common parts of their routes and form platoons, resulting in decreased fuel consumption. We formulate a combinatorial optimization problem that combines plans involving only two vehicles. We show that this problem is hard to solve for large problem instances. Hence a heuristic algorithm is proposed. The resulting plans are further optimized using convex optimization techniques. The method is evaluated with Monte Carlo simulations in a realistic setting. We demonstrate that the proposed algorithm can compute plans for thousands of trucks and that significant fuel savings can be achieved.
Multi-antenna Wireless Legitimate Surveillance Systems: Design and Performance Analysis
Venue: arXiv cs.IT 2017
Year: 2017

To improve national security, government agencies have long been committed to enforcing powerful surveillance measures on suspicious individuals or communications. In this paper, we consider a wireless legitimate surveillance system, where a full-duplex multi-antenna legitimate monitor aims to eavesdrop on a dubious communication link between a suspicious pair via proactive jamming. Assuming that the legitimate monitor can successfully overhear the suspicious information only when its achievable data rate is no smaller than that of the suspicious receiver, the key objective is to maximize the eavesdropping non-outage probability by joint design of the jamming power, receive and transmit beamformers at the legitimate monitor. Depending on the number of receive/transmit antennas implemented, i.e., single-input single-output, single-input multiple-output, multiple-input single-output and multiple-input multiple-output (MIMO), four different scenarios are investigated. For each scenario, the optimal jamming power is derived in closed-form and efficient algorithms are obtained for the optimal transmit/receive beamforming vectors. Moreover, low-complexity suboptimal beamforming schemes are proposed for the MIMO case. Our analytical findings demonstrate that by exploiting multiple antennas at the legitimate monitor, the eavesdropping non-outage probability can be significantly improved compared to the single antenna case. In addition, the proposed suboptimal transmit zero-forcing scheme yields similar performance as the optimal scheme.
A Constructive Framework for Galois Connections
Venue: arXiv cs.PL 2017
Year: 2017

Abstract interpretation-based static analyses rely on abstract domains of program properties, such as intervals or congruences for integer variables. Galois connections (GCs) between posets provide the most widespread and useful formal tool for mathematically specifying abstract domains. Recently, Darais and Van Horn [2016] put forward a notion of constructive Galois connection for unordered sets (rather than posets), which allows to define abstract domains in a so-called mechanized and calculational proof style and therefore enables the use of proof assistants like Coq and Agda for automatically extracting verified algorithms of static analysis. We show here that constructive GCs are isomorphic, in a precise and comprehensive meaning including sound abstract functions, to so-called partitioning GCs--an already known class of GCs which allows to cast standard set partitions as an abstract domain. Darais and Van Horn [2016] also provide a notion of constructive GC for posets, which we prove to be isomorphic to plain GCs and therefore lose their constructive attribute. Drawing on these findings, we put forward and advocate the use of purely partitioning GCs, a novel class of constructive abstract domains for a mechanized approach to abstract interpretation. We show that this class of abstract domains allows us to represent a set partition with more flexibility while retaining a constructive approach to Galois connections.
Logically Isolated, Actually Unpredictable? Measuring Hypervisor Performance in Multi-Tenant SDNs
Venue: arXiv cs.NI 2017
Year: 2017

Ideally, by enabling multi-tenancy, network virtualization allows to improve resource utilization, while providing performance isolation: although the underlying resources are shared, the virtual network appears as a dedicated network to the tenant. However, providing such an illusion is challenging in practice, and over the last years, many expedient approaches have been proposed to provide performance isolation in virtual networks, by enforcing bandwidth reservations. We in this paper study another source for overheads and unpredictable performance in virtual networks: the hypervisor. The hypervisor is a critical component in multi-tenant environments, but its overhead and influence on performance are hardly understood today. In particular, we focus on OpenFlow-based virtualized Software Defined Networks (vSDNs). Network virtualization is considered a killer application for SDNs: a vSDN allows each tenant to flexibly manage its network from a logically centralized perspective, via a simple API. For the purpose of our study, we developed a new benchmarking tool for OpenFlow control and data planes, enabling high and consistent OpenFlow message rates. Using our tool, we identify and measure controllable and uncontrollable effects on performance and overhead, including the hypervisor technology, the number of tenants as well as the tenant type, as well as the type of OpenFlow messages.
Not All Dialogues are Created Equal: Instance Weighting for Neural Conversational Models
Venue: arXiv cs.CL 2017
Year: 2017

Neural conversational models require substantial amounts of dialogue data for their parameter estimation and are therefore usually learned on large corpora such as chat forums or movie subtitles. These corpora are, however, often challenging to work with, notably due to their frequent lack of turn segmentation and the presence of multiple references external to the dialogue itself. This paper shows that these challenges can be mitigated by adding a weighting model into the architecture. The weighting model, which is itself estimated from dialogue data, associates each training example to a numerical weight that reflects its intrinsic quality for dialogue modelling. At training time, these sample weights are included into the empirical loss to be minimised. Evaluation results on retrieval-based models trained on movie and TV subtitles demonstrate that the inclusion of such a weighting model improves the model performance on unsupervised metrics.
Classic Sliding Mode Control From First Principles
Venue: arXiv cs.SY 2017
Year: 2017

This is an intuitive introduction to classic sliding mode control that shows how the associated assumptions and condition for its use arise in the context of a derivation of the method. It derives a controller that obviates the need for the assumption of any sign for the control input vector, answers why it is said that it deals only with matched disturbances and why a system that it may apply to 'must' be linear in the control signal. Additionally, it may be viewed as an example of how a control design method might be developed, adding to its pedagogical usefulness.
Kanban + X: Leveraging Kanban for Focused Improvements
Venue: arXiv cs.SE 2017
Year: 2017

Agile Development is used for many problems, often with different priorities and challenges. However, generalized engineering methodologies often overlook the particularities of a project. To solve this problem, we have looked at ways engineers have modified development methodologies for a particular focus, and created a generalized framework for leveraging Kanban towards focused improvements. The result is a parallel iterative board that tracks and visualizes progress towards a focus, which we have applied to security, sustainability, and high performance as examples. Through use of this system, software projects can be more focused and directed towards their goals.
Entropy of Independent Experiments, Revisited
Venue: arXiv cs.IT 2017
Year: 2017

The weak law of large numbers implies that, under mild assumptions on the source, the Renyi entropy per produced symbol converges (in probability) towards the Shannon entropy rate. This paper quantifies the speed of this convergence for sources with independent (but not iid) outputs, generalizing and improving the result of Holenstein and Renner (IEEE Trans. Inform. Theory, 2011). (a) we characterize sources with \emph{slowest convergence} (for given entropy): their outputs are mixtures of a uniform distribution and a unit mass. (b) based on the above characterization, we establish faster convergences in \emph{high-entropy} regimes. We discuss how these improved bounds may be used to better quantify security of outputs of random number generators. In turn, the characterization of "worst" distributions can be used to derive sharp "extremal" inequalities between Renyi and Shannon entropy. The main technique is \emph{non-convex programming}, used to characterize distributions of possibly large exponential moments under certain entropy.
Weighted finite impulse response filter for chromatic dispersion equalization in coherent optical fiber communication systems
Venue: arXiv cs.IT 2017
Year: 2017

Time-domain chromatic dispersion (CD) equalization using finite impulse response (FIR) filter is now a common approach for coherent optical fiber communication systems. The complex weights of FIR filter taps are calculated from a truncated impulse response of the CD transfer function, and the modulus of the complex weights is constant. In our work, we take the limited bandwidth of a single channel signal into account and propose weighted FIR filters to improve the performance of CD equalization. A raised cosine FIR filter and a Gaussian FIR filter are investigated in our work. The optimization of raised cosine FIR filter and Gaussian FIR filter are made in terms of the EVM of QPSK, 16QAM and 32QAM coherent detection signal. The results demonstrate that the optimized parameters of the weighted filters are independent of the modulation format, symbol rate and the length of transmission fiber. With the optimized weighted FIR filters, the EVM of CD equalization signal is decreased significantly. The principle of weighted FIR filter can also be extended to other symmetric functions as weighted functions.
Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary
Venue: arXiv cs.AI 2017
Year: 2017

Current domain-independent, classical planners require symbolic models of the problem domain and instance as input, resulting in a knowledge acquisition bottleneck. Meanwhile, although deep learning has achieved significant success in many fields, the knowledge is encoded in a subsymbolic representation which is incompatible with symbolic systems such as planners. We propose LatPlan, an unsupervised architecture combining deep learning and classical planning. Given only an unlabeled set of image pairs showing a subset of transitions allowed in the environment (training inputs), and a pair of images representing the initial and the goal states (planning inputs), LatPlan finds a plan to the goal state in a symbolic latent space and returns a visualized plan execution. The contribution of this paper is twofold: (1) State Autoencoder, which finds a propositional state representation of the environment using a Variational Autoencoder. It generates a discrete latent vector from the images, based on which a PDDL model can be constructed and then solved by an off-the-shelf planner. (2) Action Autoencoder / Discriminator, a neural architecture which jointly finds the action symbols and the implicit action models (preconditions/effects), and provides a successor function for the implicit graph search. We evaluate LatPlan using image-based versions of 3 planning domains: 8-puzzle, Towers of Hanoi and LightsOut.
Learning with Changing Features
Venue: arXiv cs.LG 2017
Year: 2017

In this paper we study the setting where features are added or change interpretation over time, which has applications in multiple domains such as retail, manufacturing, finance. In particular, we propose an approach to provably determine the time instant from which the new/changed features start becoming relevant with respect to an output variable in an agnostic (supervised) learning setting. We also suggest an efficient version of our approach which has the same asymptotic performance. Moreover, our theory also applies when we have more than one such change point. Independent post analysis of a change point identified by our method for a large retailer revealed that it corresponded in time with certain unflattering news stories about a brand that resulted in the change in customer behavior. We also applied our method to data from an advanced manufacturing plant identifying the time instant from which downstream features became relevant. To the best of our knowledge this is the first work that formally studies change point detection in a distribution independent agnostic setting, where the change point is based on the changing relationship between input and output.
Defense semantics of argumentation: encoding reasons for accepting arguments
Venue: arXiv cs.AI 2017
Year: 2017

In this paper we show how the defense relation among abstract arguments can be used to encode the reasons for accepting arguments. After introducing a novel notion of defenses and defense graphs, we propose a defense semantics together with a new notion of defense equivalence of argument graphs, and compare defense equivalence with standard equivalence and strong equivalence, respectively. Then, based on defense semantics, we define two kinds of reasons for accepting arguments, i.e., direct reasons and root reasons, and a notion of root equivalence of argument graphs. Finally, we show how the notion of root equivalence can be used in argumentation summarization.
A Note on Properties of Discrete Composition Operators
Venue: arXiv cs.CG 2017
Year: 2017

We derive properties and a characterization of discrete composition matrices which are useful in the field of numerical computation of shape correspondences.
Deriving Quests from Open World Mechanics
Venue: arXiv cs.MM 2017
Year: 2017

Open world games present players with more freedom than games with linear progression structures. However, without clearly-defined objectives, they often leave players without a sense of purpose. Most of the time, quests and objectives are hand-authored and overlaid atop an open world's mechanics. But what if they could be generated organically from the gameplay itself? The goal of our project was to develop a model of the mechanics in Minecraft that could be used to determine the ideal placement of objectives in an open world setting. We formalized the game logic of Minecraft in terms of logical rules that can be manipulated in two ways: they may be executed to generate graphs representative of the player experience when playing an open world game with little developer direction; and they may be statically analyzed to determine dependency orderings, feedback loops, and bottlenecks. These analyses may then be used to place achievements on gameplay actions algorithmically.
Deep Learning in the Automotive Industry: Applications and Tools
Venue: arXiv cs.LG 2017
Year: 2017

Deep Learning refers to a set of machine learning techniques that utilize neural networks with many hidden layers for tasks, such as image classification, speech recognition, language understanding. Deep learning has been proven to be very effective in these domains and is pervasively used by many Internet services. In this paper, we describe different automotive uses cases for deep learning in particular in the domain of computer vision. We surveys the current state-of-the-art in libraries, tools and infrastructures (e.\,g.\ GPUs and clouds) for implementing, training and deploying deep neural networks. We particularly focus on convolutional neural networks and computer vision use cases, such as the visual inspection process in manufacturing plants and the analysis of social media data. To train neural networks, curated and labeled datasets are essential. In particular, both the availability and scope of such datasets is typically very limited. A main contribution of this paper is the creation of an automotive dataset, that allows us to learn and automatically recognize different vehicle properties. We describe an end-to-end deep learning application utilizing a mobile app for data collection and process support, and an Amazon-based cloud backend for storage and training. For training we evaluate the use of cloud and on-premises infrastructures (including multiple GPUs) in conjunction with different neural network architectures and frameworks. We assess both the training times as well as the accuracy of the classifier. Finally, we demonstrate the effectiveness of the trained classifier in a real world setting during manufacturing process.