OpenRaiser/Intern-Atlas huggingface dataset:
Personal+Context navigation: combining AR and shared displays in network path-following
Venue: arXiv cs.HC 2020
Year: 2020

Shared displays are well suited to public viewing and collaboration, however they lack personal space to view private information and act without disturbing others. Combining them with Augmented Reality (AR) headsets allows interaction without altering the context on the shared display. We study a set of such interaction techniques in the context of network navigation, in particular path following, an important network analysis task. Applications abound, for example planning private trips on a network map shown on a public display.The proposed techniques allow for hands-free interaction, rendering visual aids inside the headset, in order to help the viewer maintain a connection between the AR cursor and the network that is only shown on the shared display. In two experiments on path following, we found that adding persistent connections between the AR cursor and the network on the shared display works well for high precision tasks, but more transient connections work best for lower precision tasks. More broadly, we show that combining personal AR interaction with shared displays is feasible for network navigation.
Accelerated Convergence for Counterfactual Learning to Rank
Venue: arXiv cs.LG 2020
Year: 2020

Counterfactual Learning to Rank (LTR) algorithms learn a ranking model from logged user interactions, often collected using a production system. Employing such an offline learning approach has many benefits compared to an online one, but it is challenging as user feedback often contains high levels of bias. Unbiased LTR uses Inverse Propensity Scoring (IPS) to enable unbiased learning from logged user interactions. One of the major difficulties in applying Stochastic Gradient Descent (SGD) approaches to counterfactual learning problems is the large variance introduced by the propensity weights. In this paper we show that the convergence rate of SGD approaches with IPS-weighted gradients suffers from the large variance introduced by the IPS weights: convergence is slow, especially when there are large IPS weights. To overcome this limitation, we propose a novel learning algorithm, called CounterSample, that has provably better convergence than standard IPS-weighted gradient descent methods. We prove that CounterSample converges faster and complement our theoretical findings with empirical results by performing extensive experimentation in a number of biased LTR scenarios -- across optimizers, batch sizes, and different degrees of position bias.
Latch-Based Logic Locking
Venue: arXiv cs.CR 2020
Year: 2020

Globalization of IC manufacturing has led to increased security concerns, notably IP theft. Several logic locking techniques have been developed for protecting designs, but they typically display very large overhead, and are generally susceptible to deciphering attacks. In this paper, we propose latch-based logic locking, which manipulates both the flow of data and logic in the design. This method converts an interconnected subset of existing flip-flops to pairs of latches with programmable phase. In tandem, decoy latches and logic are added, inhibiting an attacker from determining the actual design functionality. To validate this technique, we developed and verified a locking insertion flow, analyzed PPA and ATPG overhead on benchmark circuits and industry cores, extended existing attacks to account for the technique, and taped out a demonstration chip. Importantly, we show that the design overhead with this approach is significantly less than with previous logic locking schemes, while resisting model checker-based, oracle-driven attacks. With minimal delay overhead, large numbers of decoy latches can be added, cheaply increasing attack resistance.
Primitive Sets of Words
Venue: arXiv cs.FL 2020
Year: 2020

Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X \subseteq F^*$. We say that a submonoid $M$ generated by $k$ elements of $A^*$ is {\em $k$-maximal} if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X \subseteq A^*$ {\em primitive} if it is the basis of a $|X|$-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, $\{w\}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X \subseteq Y^*$. We therefore call $Y$ a {\em primitive root} of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. To obtain this result, we prove that the intersection of two $2$-maximal submonoids is either the empty word or a submonoid generated by one single primitive word. For a single word $w$, we say that the set $\{x,y\}$ is a {\em bi-root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and $\{x,y\}$ is a primitive set. We prove that every primitive word $w$ has at most one bi-root $\{x,y\}$ such that $|x|+|y|<\sqrt{|w|}$. That is, the bi-root of a word is unique provided the word is sufficiently long with respect to the size (sum of lengths) of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $θ$ is defined on $A^*$. In this setting, the notions of $θ$-power, $θ$-primitive and $θ$-root are defined, and it is shown that any word has a unique $θ$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $θ$-primitive if and only if $\{w, θ(w)\}$ is a primitive set.
How to Learn from Others: Transfer Machine Learning with Additive Regression Models to Improve Sales Forecasting
Venue: arXiv cs.LG 2020
Year: 2020

In a variety of business situations, the introduction or improvement of machine learning approaches is impaired as these cannot draw on existing analytical models. However, in many cases similar problems may have already been solved elsewhere-but the accumulated analytical knowledge cannot be tapped to solve a new problem, e.g., because of privacy barriers. For the particular purpose of sales forecasting for similar entities, we propose a transfer machine learning approach based on additive regression models that lets new entities benefit from models of existing entities. We evaluate the approach on a rich, multi-year dataset of multiple restaurant branches. We differentiate the options to simply transfer models from one branch to another ("zero shot") or to transfer and adapt them. We analyze feasibility and performance against several forecasting benchmarks. The results show the potential of the approach to exploit the collectively available analytical knowledge. Thus, we contribute an approach that is generalizable beyond sales forecasting and the specific use case in particular. In addition, we demonstrate its feasibility for a typical use case as well as the potential for improving forecasting quality. These results should inform academia, as they help to leverage knowledge across various entities, and have immediate practical application in industry.
Revisiting Role of Autoencoders in Adversarial Settings
Venue: arXiv cs.CV 2020
Year: 2020

To combat against adversarial attacks, autoencoder structure is widely used to perform denoising which is regarded as gradient masking. In this paper, we revisit the role of autoencoders in adversarial settings. Through the comprehensive experimental results and analysis, this paper presents the inherent property of adversarial robustness in the autoencoders. We also found that autoencoders may use robust features that cause inherent adversarial robustness. We believe that our discovery of the adversarial robustness of the autoencoders can provide clues to the future research and applications for adversarial defense.
The Frankfurt Latin Lexicon: From Morphological Expansion and Word Embeddings to SemioGraphs
Venue: arXiv cs.CL 2020
Year: 2020

In this article we present the Frankfurt Latin Lexicon (FLL), a lexical resource for Medieval Latin that is used both for the lemmatization of Latin texts and for the post-editing of lemmatizations. We describe recent advances in the development of lemmatizers and test them against the Capitularies corpus (comprising Frankish royal edicts, mid-6th to mid-9th century), a corpus created as a reference for processing Medieval Latin. We also consider the post-correction of lemmatizations using a limited crowdsourcing process aimed at continuous review and updating of the FLL. Starting from the texts resulting from this lemmatization process, we describe the extension of the FLL by means of word embeddings, whose interactive traversing by means of SemioGraphs completes the digital enhanced hermeneutic circle. In this way, the article argues for a more comprehensive understanding of lemmatization, encompassing classical machine learning as well as intellectual post-corrections and, in particular, human computation in the form of interpretation processes based on graph representations of the underlying lexical resources.
Complexity Analysis Of Next-Generation VVC Encoding and Decoding
Venue: arXiv cs.MM 2020
Year: 2020

While the next generation video compression standard, Versatile Video Coding (VVC), provides a superior compression efficiency, its computational complexity dramatically increases. This paper thoroughly analyzes this complexity for both encoder and decoder of VVC Test Model 6, by quantifying the complexity break-down for each coding tool and measuring the complexity and memory requirements for VVC encoding/decoding. These extensive analyses are performed for six video sequences of 720p, 1080p, and 2160p, under Low-Delay (LD), Random-Access (RA), and All-Intra (AI) conditions (a total of 320 encoding/decoding). Results indicate that the VVC encoder and decoder are 5x and 1.5x more complex compared to HEVC in LD, and 31x and 1.8x in AI, respectively. Detailed analysis of coding tools reveals that in LD on average, motion estimation tools with 53%, transformation and quantization with 22%, and entropy coding with 7% dominate the encoding complexity. In decoding, loop filters with 30%, motion compensation with 20%, and entropy decoding with 16%, are the most complex modules. Moreover, the required memory bandwidth for VVC encoding/decoding are measured through memory profiling, which are 30x and 3x of HEVC. The reported results and insights are a guide for future research and implementations of energy-efficient VVC encoder/decoder.
Can Shallow Neural Networks Beat the Curse of Dimensionality? A mean field training perspective
Venue: arXiv cs.LG 2020
Year: 2020

We prove that the gradient descent training of a two-layer neural network on empirical or population risk may not decrease population risk at an order faster than $t^{-4/(d-2)}$ under mean field scaling. Thus gradient descent training for fitting reasonably smooth, but truly high-dimensional data may be subject to the curse of dimensionality. We present numerical evidence that gradient descent training with general Lipschitz target functions becomes slower and slower as the dimension increases, but converges at approximately the same rate in all dimensions when the target function lies in the natural function space for two-layer ReLU networks.
Sharp Second-Order Pointwise Asymptotics for Lossless Compression with Side Information
Venue: arXiv cs.IT 2020
Year: 2020

The problem of determining the best achievable performance of arbitrary lossless compression algorithms is examined, when correlated side information is available at both the encoder and decoder. For arbitrary source-side information pairs, the conditional information density is shown to provide a sharp asymptotic lower bound for the description lengths achieved by an arbitrary sequence of compressors. This implies that, for ergodic source-side information pairs, the conditional entropy rate is the best achievable asymptotic lower bound to the rate, not just in expectation but with probability one. Under appropriate mixing conditions, a central limit theorem and a law of the iterated logarithm are proved, describing the inevitable fluctuations of the second-order asymptotically best possible rate. An idealised version of Lempel-Ziv coding with side information is shown to be universally first- and second-order asymptotically optimal, under the same conditions. These results are in part based on a new almost-sure invariance principle for the conditional information density, which may be of independent interest.
A General Framework for Computing the Nucleolus Via Dynamic Programming
Venue: arXiv cs.GT 2020
Year: 2020

This paper defines a general class of cooperative games for which the nucleolus is efficiently computable. This class includes new members for which the complexity of computing their nucleolus was not previously known. We show that when the minimum excess coalition problem of a cooperative game can be formulated as a hypergraph dynamic program its nucleolus is efficiently computable. This gives a general technique for designing efficient algorithms for computing the nucleolus of a cooperative game. This technique is inspired by a recent result of Pashkovich (2018) on weighted voting games. However our technique significantly extends beyond the capabilities of previous work. We demonstrate this by applying it to give an algorithm for computing the nucleolus of b-matching games in polynomial time on graphs of bounded treewidth.
Stack up your chips: Betting on 3D integration to augment Moore's Law scaling
Venue: arXiv cs.AR 2020
Year: 2020

3D integration, i.e., stacking of integrated circuit layers using parallel or sequential processing is gaining rapid industry adoption with the slowdown of Moore's law scaling. 3D stacking promises potential gains in performance, power and cost but the actual magnitude of gains varies depending on end-application, technology choices and design. In this talk, we will discuss some key challenges associated with 3D design and how design-for-3D will require us to break traditional silos of micro-architecture, circuit/physical design and manufacturing technology to work across abstractions to enable the gains promised by 3D technologies.
Unsupervised Domain Adaptation in Semantic Segmentation: a Review
Venue: arXiv cs.CV 2020
Year: 2020

The aim of this paper is to give an overview of the recent advancements in the Unsupervised Domain Adaptation (UDA) of deep networks for semantic segmentation. This task is attracting a wide interest, since semantic segmentation models require a huge amount of labeled data and the lack of data fitting specific requirements is the main limitation in the deployment of these techniques. This problem has been recently explored and has rapidly grown with a large number of ad-hoc approaches. This motivates us to build a comprehensive overview of the proposed methodologies and to provide a clear categorization. In this paper, we start by introducing the problem, its formulation and the various scenarios that can be considered. Then, we introduce the different levels at which adaptation strategies may be applied: namely, at the input (image) level, at the internal features representation and at the output level. Furthermore, we present a detailed overview of the literature in the field, dividing previous methods based on the following (non mutually exclusive) categories: adversarial learning, generative-based, analysis of the classifier discrepancies, self-teaching, entropy minimization, curriculum learning and multi-task learning. Novel research directions are also briefly introduced to give a hint of interesting open problems in the field. Finally, a comparison of the performance of the various methods in the widely used autonomous driving scenario is presented.
Solving a steady-state PDE using spiking networks and neuromorphic hardware
Venue: arXiv cs.NE 2020
Year: 2020

The widely parallel, spiking neural networks of neuromorphic processors can enable computationally powerful formulations. While recent interest has focused on primarily machine learning tasks, the space of appropriate applications is wide and continually expanding. Here, we leverage the parallel and event-driven structure to solve a steady state heat equation using a random walk method. The random walk can be executed fully within a spiking neural network using stochastic neuron behavior, and we provide results from both IBM TrueNorth and Intel Loihi implementations. Additionally, we position this algorithm as a potential scalable benchmark for neuromorphic systems.
Team Neuro at SemEval-2020 Task 8: Multi-Modal Fine Grain Emotion Classification of Memes using Multitask Learning
Venue: arXiv cs.CV 2020
Year: 2020

In this article, we describe the system that we used for the memotion analysis challenge, which is Task 8 of SemEval-2020. This challenge had three subtasks where affect based sentiment classification of the memes was required along with intensities. The system we proposed combines the three tasks into a single one by representing it as multi-label hierarchical classification problem.Here,Multi-Task learning or Joint learning Procedure is used to train our model.We have used dual channels to extract text and image based features from separate Deep Neural Network Backbone and aggregate them to create task specific features. These task specific aggregated feature vectors ware then passed on to smaller networks with dense layers, each one assigned for predicting one type of fine grain sentiment label. Our Proposed method show the superiority of this system in few tasks to other best models from the challenge.
When Dictionary Learning Meets Deep Learning: Deep Dictionary Learning and Coding Network for Image Recognition with Limited Data
Venue: arXiv cs.CV 2020
Year: 2020

We present a new Deep Dictionary Learning and Coding Network (DDLCN) for image recognition tasks with limited data. The proposed DDLCN has most of the standard deep learning layers (e.g., input/output, pooling, fully connected, etc.), but the fundamental convolutional layers are replaced by our proposed compound dictionary learning and coding layers. The dictionary learning learns an over-complete dictionary for input training data. At the deep coding layer, a locality constraint is added to guarantee that the activated dictionary bases are close to each other. Then the activated dictionary atoms are assembled and passed to the compound dictionary learning and coding layers. In this way, the activated atoms in the first layer can be represented by the deeper atoms in the second dictionary. Intuitively, the second dictionary is designed to learn the fine-grained components shared among the input dictionary atoms, thus a more informative and discriminative low-level representation of the dictionary atoms can be obtained. We empirically compare DDLCN with several leading dictionary learning methods and deep learning models. Experimental results on five popular datasets show that DDLCN achieves competitive results compared with state-of-the-art methods when the training data is limited. Code is available at https://github.com/Ha0Tang/DDLCN.
Multi-Source Deep Domain Adaptation with Weak Supervision for Time-Series Sensor Data
Venue: arXiv cs.LG 2020
Year: 2020

Domain adaptation (DA) offers a valuable means to reuse data and models for new problem domains. However, robust techniques have not yet been considered for time series data with varying amounts of data availability. In this paper, we make three main contributions to fill this gap. First, we propose a novel Convolutional deep Domain Adaptation model for Time Series data (CoDATS) that significantly improves accuracy and training time over state-of-the-art DA strategies on real-world sensor data benchmarks. By utilizing data from multiple source domains, we increase the usefulness of CoDATS to further improve accuracy over prior single-source methods, particularly on complex time series datasets that have high variability between domains. Second, we propose a novel Domain Adaptation with Weak Supervision (DA-WS) method by utilizing weak supervision in the form of target-domain label distributions, which may be easier to collect than additional data labels. Third, we perform comprehensive experiments on diverse real-world datasets to evaluate the effectiveness of our domain adaptation and weak supervision methods. Results show that CoDATS for single-source DA significantly improves over the state-of-the-art methods, and we achieve additional improvements in accuracy using data from multiple source domains and weakly supervised signals. Code is available at: https://github.com/floft/codats
Modeling Stakeholder-centric Value Chain of Data to Understand Data Exchange Ecosystem
Venue: arXiv cs.CY 2020
Year: 2020

In recent years, the expectation that new businesses and economic value can be created by combining/exchanging data from different fields has risen. However, value creation by data exchange involves not only data, but also technologies and a variety of stakeholders that are integrated and in competition with one another. This makes the data exchange ecosystem a challenging subject to study. In this paper, we propose a model describing the stakeholder-centric value chain (SVC) of data by focusing on the relationships among stakeholders in data businesses and discussing creative ways to use them. The SVC model enables the analysis and understanding of the structural characteristics of the data exchange ecosystem. We identified stakeholders who carry potential risk, those who play central roles in the ecosystem, and the distribution of profit among them using business models collected by the SVC.
Secure and Differentially Private Bayesian Learning on Distributed Data
Venue: arXiv cs.CR 2020
Year: 2020

Data integration and sharing maximally enhance the potential for novel and meaningful discoveries. However, it is a non-trivial task as integrating data from multiple sources can put sensitive information of study participants at risk. To address the privacy concern, we present a distributed Bayesian learning approach via Preconditioned Stochastic Gradient Langevin Dynamics with RMSprop, which combines differential privacy and homomorphic encryption in a harmonious manner while protecting private information. We applied the proposed secure and privacy-preserving distributed Bayesian learning approach to logistic regression and survival analysis on distributed data, and demonstrated its feasibility in terms of prediction accuracy and time complexity, compared to the centralized approach.
Feature selection for gesture recognition in Internet-of-Things for healthcare
Venue: arXiv cs.CV 2020
Year: 2020

Internet of Things is rapidly spreading across several fields, including healthcare, posing relevant questions related to communication capabilities, energy efficiency and sensors unobtrusiveness. Particularly, in the context of recognition of gestures, e.g., grasping of different objects, brain and muscular activity could be simultaneously recorded via EEG and EMG, respectively, and analyzed to identify the gesture that is being accomplished, and the quality of its performance. This paper proposes a new algorithm that aims (i) to robustly extract the most relevant features to classify different grasping tasks, and (ii) to retain the natural meaning of the selected features. This, in turn, gives the opportunity to simplify the recording setup to minimize the data traffic over the communication network, including Internet, and provide physiologically significant features for medical interpretation. The algorithm robustness is ensured both by consensus clustering as a feature selection strategy, and by nested cross-validation scheme to evaluate its classification performance.