OpenRaiser/Intern-Atlas huggingface dataset:
The Complexity of Interactively Learning a Stable Matching by Trial and Error
Venue: arXiv cs.GT 2020
Year: 2020

In a stable matching setting, we consider a query model that allows for an interactive learning algorithm to make precisely one type of query: proposing a matching, the response to which is either that the proposed matching is stable, or a blocking pair (chosen adversarially) indicating that this matching is unstable. For one-to-one matching markets, our main result is an essentially tight upper bound of $O(n^2\log n)$ on the deterministic query complexity of interactively learning a stable matching in this coarse query model, along with an efficient randomized algorithm that achieves this query complexity with high probability. For many-to-many matching markets in which participants have responsive preferences, we first give an interactive learning algorithm whose query complexity and running time are polynomial in the size of the market if the maximum quota of each agent is bounded; our main result for many-to-many markets is that the deterministic query complexity can be made polynomial (more specifically, $O(n^3 \log n)$) in the size of the market even for arbitrary (e.g., linear in the market size) quotas.
Spatial Concept-Based Navigation with Human Speech Instructions via Probabilistic Inference on Bayesian Generative Model
Venue: arXiv cs.RO 2020
Year: 2020

Robots are required to not only learn spatial concepts autonomously but also utilize such knowledge for various tasks in a domestic environment. Spatial concept represents a multimodal place category acquired from the robot's spatial experience including vision, speech-language, and self-position. The aim of this study is to enable a mobile robot to perform navigational tasks with human speech instructions, such as `Go to the kitchen', via probabilistic inference on a Bayesian generative model using spatial concepts. Specifically, path planning was formalized as the maximization of probabilistic distribution on the path-trajectory under speech instruction, based on a control-as-inference framework. Furthermore, we described the relationship between probabilistic inference based on the Bayesian generative model and control problem including reinforcement learning. We demonstrated path planning based on human instruction using acquired spatial concepts to verify the usefulness of the proposed approach in the simulator and in real environments. Experimentally, places instructed by the user's speech commands showed high probability values, and the trajectory toward the target place was correctly estimated. Our approach, based on probabilistic inference concerning decision-making, can lead to further improvement in robot autonomy.
ResiliNet: Failure-Resilient Inference in Distributed Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Federated Learning aims to train distributed deep models without sharing the raw data with the centralized server. Similarly, in distributed inference of neural networks, by partitioning the network and distributing it across several physical nodes, activations and gradients are exchanged between physical nodes, rather than raw data. Nevertheless, when a neural network is partitioned and distributed among physical nodes, failure of physical nodes causes the failure of the neural units that are placed on those nodes, which results in a significant performance drop. Current approaches focus on resiliency of training in distributed neural networks. However, resiliency of inference in distributed neural networks is less explored. We introduce ResiliNet, a scheme for making inference in distributed neural networks resilient to physical node failures. ResiliNet combines two concepts to provide resiliency: skip hyperconnection, a concept for skipping nodes in distributed neural networks similar to skip connection in resnets, and a novel technique called failout, which is introduced in this paper. Failout simulates physical node failure conditions during training using dropout, and is specifically designed to improve the resiliency of distributed neural networks. The results of the experiments and ablation studies using three datasets confirm the ability of ResiliNet to provide inference resiliency for distributed neural networks.
Assessing the Memory Ability of Recurrent Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

It is known that Recurrent Neural Networks (RNNs) can remember, in their hidden layers, part of the semantic information expressed by a sequence (e.g., a sentence) that is being processed. Different types of recurrent units have been designed to enable RNNs to remember information over longer time spans. However, the memory abilities of different recurrent units are still theoretically and empirically unclear, thus limiting the development of more effective and explainable RNNs. To tackle the problem, in this paper, we identify and analyze the internal and external factors that affect the memory ability of RNNs, and propose a Semantic Euclidean Space to represent the semantics expressed by a sequence. Based on the Semantic Euclidean Space, a series of evaluation indicators are defined to measure the memory abilities of different recurrent units and analyze their limitations. These evaluation indicators also provide a useful guidance to select suitable sequence lengths for different RNNs during training.
The didactic potential of virtual information educational environment as a tool of geography students training
Venue: arXiv cs.CY 2020
Year: 2020

The article clarifies the concept of "virtual information educational environment" (VIEE) and examines the researchers' views on its meaning exposed in the scientific literature. The article determines the didactic potential of the virtual information educational environment for the geography students training based on the analysis of the authors' experience of blended learning by means of the Google Classroom. It also specifies the features (immersion, interactivity, and dynamism, sense of presence, continuity, and causality). The authors highlighted the advantages of virtual information educational environment implementation, such as: increase of the efficiency of the educational process by intensifying the process of cognition and interpersonal interactive communication; continuous access to multimedia content both in Google Classroom and beyond; saving student time due to the absence of necessity to work out the training material "manually"; availability of virtual pages of the virtual class; individualization of the educational process; formation of informational culture of the geography students ; and more productive learning of the educational material at the expense of IT educational facilities. Among the disadvantages the article mentions low level of computerization, insignificant quantity and low quality of software products, underestimation of the role of VIEE in the professional training of geography students, and the lack of economic stimuli, etc.
Design of SEC-DED and SEC-DED-DAEC Codes of different lengths
Venue: arXiv cs.AR 2020
Year: 2020

Reliability is an important requirement for both communication and storage systems. Due to continuous scale down of technology multiple adjacent bits error probability increases. The data may be corrupted due soft errors. Error correction codes are used to detect and correct the errors. In this paper, design of single error correction-double error detection (SEC-DED) and single error correction-double error detection-double adjacent error correction (SEC-DED-DAEC) codes of different data lengths have been proposed. Proposed SEC-DED and SEC-DED-DAEC codes require lower delay and power compared to existing coding schemes. Area complexity in terms of logic gates of proposed and existing codes have been presented. ASIC-based synthesis results show a notable reduction compared to existing SEC-DED codes. All the codec architectures are synthesized on ASIC platform. Performances of different SEC-DED-DAEC codes are tabulated in terms of area, power and delay.
An Efficient Secure Dynamic Skyline Query Model
Venue: arXiv cs.DB 2020
Year: 2020

It is now cost-effective to outsource large dataset and perform query over the cloud. However, in this scenario, there exist serious security and privacy issues that sensitive information contained in the dataset can be leaked. The most effective way to address that is to encrypt the data before outsourcing. Nevertheless, it remains a grand challenge to process queries in ciphertext efficiently. In this work, we shall focus on solving one representative query task, namely dynamic skyline query, in a secure manner over the cloud. However, it is difficult to be performed on encrypted data as its dynamic domination criteria require both subtraction and comparison, which cannot be directly supported by a single encryption scheme efficiently. To this end, we present a novel framework called SCALE. It works by transforming traditional dynamic skyline domination into pure comparisons. The whole process can be completed in single-round interaction between user and the cloud. We theoretically prove that the outsourced database, query requests, and returned results are all kept secret under our model. Moreover, we also present an efficient strategy for dynamic insertion and deletion of stored records. Empirical study over a series of datasets demonstrates that our framework improves the efficiency of query processing by nearly three orders of magnitude compared to the state-of-the-art.
Hierarchical Transformer Network for Utterance-level Emotion Recognition
Venue: arXiv cs.CL 2020
Year: 2020

While there have been significant advances in de-tecting emotions in text, in the field of utter-ance-level emotion recognition (ULER), there are still many problems to be solved. In this paper, we address some challenges in ULER in dialog sys-tems. (1) The same utterance can deliver different emotions when it is in different contexts or from different speakers. (2) Long-range contextual in-formation is hard to effectively capture. (3) Unlike the traditional text classification problem, this task is supported by a limited number of datasets, among which most contain inadequate conversa-tions or speech. To address these problems, we propose a hierarchical transformer framework (apart from the description of other studies, the "transformer" in this paper usually refers to the encoder part of the transformer) with a lower-level transformer to model the word-level input and an upper-level transformer to capture the context of utterance-level embeddings. We use a pretrained language model bidirectional encoder representa-tions from transformers (BERT) as the lower-level transformer, which is equivalent to introducing external data into the model and solve the problem of data shortage to some extent. In addition, we add speaker embeddings to the model for the first time, which enables our model to capture the in-teraction between speakers. Experiments on three dialog emotion datasets, Friends, EmotionPush, and EmoryNLP, demonstrate that our proposed hierarchical transformer network models achieve 1.98%, 2.83%, and 3.94% improvement, respec-tively, over the state-of-the-art methods on each dataset in terms of macro-F1.
Presence in VR experiences -- an empirical cost-benefit-analysis
Venue: arXiv cs.HC 2020
Year: 2020

Virtual reality (VR) is on the edge of getting a mainstream platform for gaming, education and product design. The feeling of being present in the virtual world is influenced by many factors and even more intriguing a single negative influence can destroy the illusion that was created with a lot of effort by other measures. Therefore, it is crucial to have a balance between the influencing factors, know the importance of the factors and have a good estimation of how much effort it takes to bring each factor to a certain level of fidelity. This paper collects influencing factors discussed in literature, analyses the immersion of current off-the-shelf VR-solutions and presents results from an empirical study on efforts and benefits from certain aspects influencing presence in VR experiences. It turns out, that sometimes delivering high fidelity is easier to achieve than medium fidelity and for other aspects it is worthwhile investing more effort to achieve higher fidelity to improve presence a lot.
Text Classification with Lexicon from PreAttention Mechanism
Venue: arXiv cs.CL 2020
Year: 2020

A comprehensive and high-quality lexicon plays a crucial role in traditional text classification approaches. And it improves the utilization of the linguistic knowledge. Although it is helpful for the task, the lexicon has got little attention in recent neural network models. Firstly, getting a high-quality lexicon is not easy. We lack an effective automated lexicon extraction method, and most lexicons are hand crafted, which is very inefficient for big data. What's more, there is no an effective way to use a lexicon in a neural network. To address those limitations, we propose a Pre-Attention mechanism for text classification in this paper, which can learn attention of different words according to their effects in the classification tasks. The words with different attention can form a domain lexicon. Experiments on three benchmark text classification tasks show that our models get competitive result comparing with the state-of-the-art methods. We get 90.5% accuracy on Stanford Large Movie Review dataset, 82.3% on Subjectivity dataset, 93.7% on Movie Reviews. And compared with the text classification model without Pre-Attention mechanism, those with Pre-Attention mechanism improve by 0.9%-2.4% accuracy, which proves the validity of the Pre-Attention mechanism. In addition, the Pre-Attention mechanism performs well followed by different types of neural networks (e.g., convolutional neural networks and Long Short-Term Memory networks). For the same dataset, when we use Pre-Attention mechanism to get attention value followed by different neural networks, those words with high attention values have a high degree of coincidence, which proves the versatility and portability of the Pre-Attention mechanism. we can get stable lexicons by attention values, which is an inspiring method of information extraction.
ADMM-based Decoder for Binary Linear Codes Aided by Deep Learning
Venue: arXiv cs.IT 2020
Year: 2020

Inspired by the recent advances in deep learning (DL), this work presents a deep neural network aided decoding algorithm for binary linear codes. Based on the concept of deep unfolding, we design a decoding network by unfolding the alternating direction method of multipliers (ADMM)-penalized decoder. In addition, we propose two improved versions of the proposed network. The first one transforms the penalty parameter into a set of iteration-dependent ones, and the second one adopts a specially designed penalty function, which is based on a piecewise linear function with adjustable slopes. Numerical results show that the resulting DL-aided decoders outperform the original ADMM-penalized decoder for various low density parity check (LDPC) codes with similar computational complexity.
Building large k-cores from sparse graphs
Venue: arXiv cs.DS 2020
Year: 2020

A popular model to measure network stability is the $k$-core, that is the maximal induced subgraph in which every vertex has degree at least $k$. For example, $k$-cores are commonly used to model the unraveling phenomena in social networks. In this model, users having less than $k$ connections within the network leave it, so the remaining users form exactly the $k$-core. In this paper we study the question whether it is possible to make the network more robust by spending only a limited amount of resources on new connections. A mathematical model for the $k$-core construction problem is the following Edge $k$-Core optimization problem. We are given a graph $G$ and integers $k$, $b$ and $p$. The task is to ensure that the $k$-core of $G$ has at least $p$ vertices by adding at most $b$ edges. The previous studies on Edge $k$-Core demonstrate that the problem is computationally challenging. In particular, it is NP-hard when $k=3$, W[1]-hard being parameterized by $k+b+p$ (Chitnis and Talmon, 2018), and APX-hard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the $k$-core has to be constructed from a sparse graph with some additional structural properties. Our results are 1) When the input graph is a forest, Edge $k$-Core is solvable in polynomial time; 2) Edge $k$-Core is fixed-parameter tractable (FPT) being parameterized by the minimum size of a vertex cover in the input graph. On the other hand, with such parameterization, the problem does not admit a polynomial kernel subject to a widely-believed assumption from complexity theory; 3) Edge $k$-Core is FPT parameterized by $\mathrm{tw}+k$. This improves upon a result of Chitnis and Talmon by not requiring $b$ to be small. Each of our algorithms is built upon a new graph-theoretical result interesting in its own.
Topology Optimization with Accessibility Constraint for Multi-Axis Machining
Venue: arXiv cs.CE 2020
Year: 2020

In this paper, we present a topology optimization (TO) framework to enable automated design of mechanical components while ensuring the result can be manufactured using multi-axis machining. Although TO improves the part's performance, the as-designed model is often geometrically too complex to be machined and the as-manufactured model can significantly vary due to machining constraints that are not accounted for during TO. In other words, many of the optimized design features cannot be accessed by a machine tool without colliding with the part (or fixtures). The subsequent post-processing to make the part machinable with the given setup requires trial-and-error without guarantees on preserving the optimized performance. Our proposed approach is based on the well-established accessibility analysis formulation using convolutions in configuration space that is extensively used in spatial planning and robotics. We define an 'inaccessibility measure field' (IMF) over the design domain to identify non-manufacturable features and quantify their contribution to non-manufacturability. The IMF is used to penalize the sensitivity field of performance objectives and constraints to prevent formation of inaccessible regions. Unlike existing discrete formulations, our IMF provides a continuous spatial field that is desirable for TO convergence. Our approach applies to arbitrary geometric complexity of the part, tools, and fixtures, and is highly parallelizable on multi-core architecture. We demonstrate the effectiveness of our framework on benchmark and realistic examples in 2D and 3D. We also show that it is possible to directly construct manufacturing plans for the optimized designs based on the accessibility information.
Neural arbitrary style transfer for portrait images using the attention mechanism
Venue: arXiv cs.CV 2020
Year: 2020

Arbitrary style transfer is the task of synthesis of an image that has never been seen before, using two given images: content image and style image. The content image forms the structure, the basic geometric lines and shapes of the resulting image, while the style image sets the color and texture of the result. The word "arbitrary" in this context means the absence of any one pre-learned style. So, for example, convolutional neural networks capable of transferring a new style only after training or retraining on a new amount of data are not con-sidered to solve such a problem, while networks based on the attention mech-anism that are capable of performing such a transformation without retraining - yes. An original image can be, for example, a photograph, and a style image can be a painting of a famous artist. The resulting image in this case will be the scene depicted in the original photograph, made in the stylie of this picture. Recent arbitrary style transfer algorithms make it possible to achieve good re-sults in this task, however, in processing portrait images of people, the result of such algorithms is either unacceptable due to excessive distortion of facial features, or weakly expressed, not bearing the characteristic features of a style image. In this paper, we consider an approach to solving this problem using the combined architecture of deep neural networks with a attention mechanism that transfers style based on the contents of a particular image segment: with a clear predominance of style over the form for the background part of the im-age, and with the prevalence of content over the form in the image part con-taining directly the image of a person.
Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs
Venue: arXiv cs.FL 2020
Year: 2020

We show the surprising result that the cutpoint isolation problem is decidable for Probabilistic Finite Automata (PFA) where input words are taken from a letter-bounded context-free language. A context-free language $\mathcal{L}$ is letter-bounded when $\mathcal{L} \subseteq a_1^*a_2^* \cdots a_\ell^*$ for some finite $\ell > 0$ where each letter is distinct. A cutpoint is isolated when it cannot be approached arbitrarily closely. The decidability of this problem is in marked contrast to the situation for the (strict) emptiness problem for PFA which is undecidable under the even more severe restrictions of PFA with polynomial ambiguity, commutative matrices and input over a letter-bounded language as well as to the injectivity problem which is undecidable for PFA over letter-bounded languages. We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous. We also show that the problem is at least NP-hard and use our decision procedure to solve several related problems.
Representations for the largest Extension of a closure system
Venue: arXiv cs.DM 2020
Year: 2020

We consider extension of a closure system on a finite set S as a closure system on the same set S containing the given one as a sublattice. A closure system can be represented in different ways, e.g. by an implicational base or by the set of its meet-irreducible elements. When a closure system is described by an implicational base, we provide a characterization of the implicational base for the largest extension. We also show that the largest extension can be handled by a small modification of the implicational base of the input closure system. This answers a question asked in [12]. Second, we are interested in computing the largest extension when the closure system is given by the set of all its meet-irreducible elements. We give an incremental polynomial time algorithm to compute the largest extension of a closure system, and left open if the number of meet-irreducible elements grows exponentially.
Deep Neural Networks for the Correction of Mie Scattering in Fourier-Transformed Infrared Spectra of Biological Samples
Venue: arXiv cs.LG 2020
Year: 2020

Infrared spectra obtained from cell or tissue specimen have commonly been observed to involve a significant degree of (resonant) Mie scattering, which often overshadows biochemically relevant spectral information by a non-linear, non-additive spectral component in Fourier transformed infrared (FTIR) spectroscopic measurements. Correspondingly, many successful machine learning approaches for FTIR spectra have relied on preprocessing procedures that computationally remove the scattering components from an infrared spectrum. We propose an approach to approximate this complex preprocessing function using deep neural networks. As we demonstrate, the resulting model is not just several orders of magnitudes faster, which is important for real-time clinical applications, but also generalizes strongly across different tissue types. Furthermore, our proposed method overcomes the trade-off between computation time and the corrected spectrum being biased towards an artificial reference spectrum.