OpenRaiser/Intern-Atlas huggingface dataset:
Semantic descriptions of 24 evaluational adjectives, for application in sentiment analysis
Venue: arXiv cs.CL 2016
Year: 2016

We apply the Natural Semantic Metalanguage (NSM) approach (Goddard and Wierzbicka 2014) to the lexical-semantic analysis of English evaluational adjectives and compare the results with the picture developed in the Appraisal Framework (Martin and White 2005). The analysis is corpus-assisted, with examples mainly drawn from film and book reviews, and supported by collocational and statistical information from WordBanks Online. We propose NSM explications for 24 evaluational adjectives, arguing that they fall into five groups, each of which corresponds to a distinct semantic template. The groups can be sketched as follows: "First-person thought-plus-affect", e.g. wonderful; "Experiential", e.g. entertaining; "Experiential with bodily reaction", e.g. gripping; "Lasting impact", e.g. memorable; "Cognitive evaluation", e.g. complex, excellent. These groupings and semantic templates are compared with the classifications in the Appraisal Framework's system of Appreciation. In addition, we are particularly interested in sentiment analysis, the automatic identification of evaluation and subjectivity in text. We discuss the relevance of the two frameworks for sentiment analysis and other language technology applications.
Transfer Learning for Endoscopic Image Classification
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we propose a method for transfer learning of endoscopic images. For transferring between features obtained from images taken by different (old and new) endoscopes, we extend the Max-Margin Domain Transfer (MMDT) proposed by Hoffman et al. in order to use L2 distance constraints as regularization, called Max-Margin Domain Transfer with L2 Distance Constraints (MMDTL2). Furthermore, we develop the dual formulation of the optimization problem in order to reduce the computation cost. Experimental results demonstrate that the proposed MMDTL2 outperforms MMDT for real data sets taken by different endoscopes.
Completeness for a First-order Abstract Separation Logic
Venue: arXiv cs.LO 2016
Year: 2016

Existing work on theorem proving for the assertion language of separation logic (SL) either focuses on abstract semantics which are not readily available in most applications of program verification, or on concrete models for which completeness is not possible. An important element in concrete SL is the points-to predicate which denotes a singleton heap. SL with the points-to predicate has been shown to be non-recursively enumerable. In this paper, we develop a first-order SL, called FOASL, with an abstracted version of the points-to predicate. We prove that FOASL is sound and complete with respect to an abstract semantics, of which the standard SL semantics is an instance. We also show that some reasoning principles involving the points-to predicate can be approximated as FOASL theories, thus allowing our logic to be used for reasoning about concrete program verification problems. We give some example theories that are sound with respect to different variants of separation logics from the literature, including those that are incompatible with Reynolds's semantics. In the experiment we demonstrate our FOASL based theorem prover which is able to handle a large fragment of separation logic with heap semantics as well as non-standard semantics.
Quasi-Perfect Lee Codes from Quadratic Curves over Finite Fields
Venue: arXiv cs.IT 2016
Year: 2016

Golomb and Welch conjectured in 1970 that there only exist perfect Lee codes for radius $t=1$ or dimension $n=1, 2$. It is admitted that the existence and the construction of quasi-perfect Lee codes have to be studied since they are the best alternative to the perfect codes. In this paper we firstly highlight the relationships between subset sums, Cayley graphs, and Lee linear codes and present some results. Next, we present a new constructive method for constructing quasi-perfect Lee codes. Our approach uses subsets derived from some quadratic curves over finite fields (in odd characteristic) to derive two classes of $2$-quasi-perfect Lee codes are given over the space $\mathbb{Z}_p^n$ for $n=\frac{p^k+1}{2}$ $(\text{with} ~p\equiv 1, -5 \mod 12 \text{and} k \text{is any integer}, \text{or} p\equiv -1, 5 \mod 12 \text{and} k \text{is an even integer})$ and $n=\frac{p^k-1}{2}$ $(\text{with}p\equiv -1, 5 \mod 12, k \text{is an odd integer} \text{and} p^k>12)$, where $p$ is an odd prime. Our codes encompass the quasi-perfect Lee codes constructed recently by Camarero and Martínez. Furthermore, we solve a conjecture proposed by Camarero and Martínez (in "quasi-perfect Lee codes of radius $2$ and arbitrarily large dimension", IEEE Trans. Inf. Theory, vol. 62, no. 3, 2016) by proving that the related Cayley graphs are Ramanujan or almost Ramanujan. The Lee codes presented in this paper have applications to constrained and partial-response channels, in flash memories and decision diagrams.
On the Correctness of Inverted Index Based Public-Key Searchable Encryption Scheme for Multi-time Search
Venue: arXiv cs.CR 2016
Year: 2016

In this short note we argue that the state-of-art inverted index based public key searchable encryption scheme proposed by Wang et al may not be completely correct by giving a counterexample.
Additive Stabilizers for Unstable Graphs
Venue: arXiv cs.DM 2016
Year: 2016

Stabilization of graphs has received substantial attention in recent years due to its connection to game theory. Stable graphs are exactly the graphs inducing a matching game with non-empty core. They are also the graphs that induce a network bargaining game with a balanced solution. A graph with weighted edges is called stable if the maximum weight of an integral matching equals the cost of a minimum fractional weighted vertex cover. If a graph is not stable, it can be stabilized in different ways. Recent papers have considered the deletion or addition of edges and vertices in order to stabilize a graph. In this work, we focus on a fine-grained stabilization strategy, namely stabilization of graphs by fractionally increasing edge weights. We show the following results for stabilization by minimum weight increase in edge weights (min additive stabilizer): (i) Any approximation algorithm for min additive stabilizer that achieves a factor of $O(|V|^{1/24-ε})$ for $ε>0$ would lead to improvements in the approximability of densest-$k$-subgraph. (ii) Min additive stabilizer has no $o(\log{|V|})$ approximation unless NP=P. Results (i) and (ii) together provide the first super-constant hardness results for any graph stabilization problem. On the algorithmic side, we present (iii) an algorithm to solve min additive stabilizer in factor-critical graphs exactly in poly-time, (iv) an algorithm to solve min additive stabilizer in arbitrary-graphs exactly in time exponential in the size of the Tutte set, and (v) a poly-time algorithm with approximation factor at most $\sqrt{|V|}$ for a super-class of the instances generated in our hardness proofs.
In the Saddle: Chasing Fast and Repeatable Features
Venue: arXiv cs.CV 2016
Year: 2016

A novel similarity-covariant feature detector that extracts points whose neighbourhoods, when treated as a 3D intensity surface, have a saddle-like intensity profile. The saddle condition is verified efficiently by intensity comparisons on two concentric rings that must have exactly two dark-to-bright and two bright-to-dark transitions satisfying certain geometric constraints. Experiments show that the Saddle features are general, evenly spread and appearing in high density in a range of images. The Saddle detector is among the fastest proposed. In comparison with detector with similar speed, the Saddle features show superior matching performance on number of challenging datasets.
A short review and primer on electrodermal activity in human computer interaction applications
Venue: arXiv cs.HC 2016
Year: 2016

The application of psychophysiology in human-computer interaction is a growing field with significant potential for future smart personalised systems. Working in this emerging field requires comprehension of an array of physiological signals and analysis techniques. One of the most widely used signals is electrodermal activity, or EDA, also known as galvanic skin response or GSR. This signal is commonly used as a proxy for physiological arousal, but recent advances of interpretation and analysis suggest that traditional approaches should be revised. We present a short review on the application of EDA in human-computer interaction. This paper aims to serve as a primer for the novice, enabling rapid familiarisation with the latest core concepts. We put special emphasis on everyday human-computer interface applications to distinguish from the more common clinical or sports uses of psychophysiology. This paper is an extract from a comprehensive review of the entire field of ambulatory psychophysiology, including 12 similar chapters, plus application guidelines and systematic review. Thus any citation should be made using the following reference: B. Cowley, M. Filetti, K. Lukander, J. Torniainen, A. Henelius, L. Ahonen, O. Barral, I. Kosunen, T. Valtonen, M. Huotilainen, N. Ravaja, G. Jacucci. The Psychophysiology Primer: a guide to methods and a broad review with a focus on human-computer interaction. Foundations and Trends in Human-Computer Interaction, vol. 9, no. 3-4, pp. 150--307, 2016.
The Sharing Economy for the Smart Grid
Venue: arXiv cs.SY 2016
Year: 2016

The sharing economy has disrupted housing and transportation sectors. Homeowners can rent out their property when they are away on vacation, car owners can offer ride sharing services. These sharing economy business models are based on monetizing under-utilized infrastructure. They are enabled by peer-to-peer platforms that match eager sellers with willing buyers. Are there compelling sharing economy opportunities in the electricity sector? What products or services can be shared in tomorrow's Smart Grid? We begin by exploring sharing economy opportunities in the electricity sector, and discuss regulatory and technical obstacles to these opportunities. We then study the specific problem of a collection of firms sharing their electricity storage. We characterize equilibrium prices for shared storage in a spot market. We formulate storage investment decisions of the firms as a non-convex non-cooperative game. We show that under a mild alignment condition, a Nash equilibrium exists, it is unique, and it supports the social welfare. We discuss technology platforms necessary for the physical exchange of power, and market platforms necessary to trade electricity storage. We close with synthetic examples to illustrate our ideas.
Incremental Minimax Optimization based Fuzzy Clustering for Large Multi-view Data
Venue: arXiv cs.AI 2016
Year: 2016

Incremental clustering approaches have been proposed for handling large data when given data set is too large to be stored. The key idea of these approaches is to find representatives to represent each cluster in each data chunk and final data analysis is carried out based on those identified representatives from all the chunks. However, most of the incremental approaches are used for single view data. As large multi-view data generated from multiple sources becomes prevalent nowadays, there is a need for incremental clustering approaches to handle both large and multi-view data. In this paper we propose a new incremental clustering approach called incremental minimax optimization based fuzzy clustering (IminimaxFCM) to handle large multi-view data. In IminimaxFCM, representatives with multiple views are identified to represent each cluster by integrating multiple complementary views using minimax optimization. The detailed problem formulation, updating rules derivation, and the in-depth analysis of the proposed IminimaxFCM are provided. Experimental studies on several real world multi-view data sets have been conducted. We observed that IminimaxFCM outperforms related incremental fuzzy clustering in terms of clustering accuracy, demonstrating the great potential of IminimaxFCM for large multi-view data analysis.
A Novel Term_Class Relevance Measure for Text Categorization
Venue: arXiv cs.IR 2016
Year: 2016

In this paper, we introduce a new measure called Term_Class relevance to compute the relevancy of a term in classifying a document into a particular class. The proposed measure estimates the degree of relevance of a given term, in placing an unlabeled document to be a member of a known class, as a product of Class_Term weight and Class_Term density; where the Class_Term weight is the ratio of the number of documents of the class containing the term to the total number of documents containing the term and the Class_Term density is the relative density of occurrence of the term in the class to the total occurrence of the term in the entire population. Unlike the other existing term weighting schemes such as TF-IDF and its variants, the proposed relevance measure takes into account the degree of relative participation of the term across all documents of the class to the entire population. To demonstrate the significance of the proposed measure experimentation has been conducted on the 20 Newsgroups dataset. Further, the superiority of the novel measure is brought out through a comparative analysis.
A new kind of parallelism and its programming in the Explicitly Many-Processor Approach
Venue: arXiv cs.DC 2016
Year: 2016

The processor accelerators are effective because they are working not (completely) on principles of stored program computers. They use some kind of parallelism, and it is rather hard to program them effectively: a parallel architecture by means of (and thinking in) sequential programming. The recently introduced EMPA architecture uses a new kind of parallelism, which offers the potential of reaching higher degree of parallelism, and also provides extra possibilities and challenges. It not only provides synchronization and inherent parallelization, but also takes over some duties typically offered by the OS, and even opens the till now closed machine instructions for the end-user. A toolchain for EMPA architecture with Y86 cores has been prepared, including an assembler and a cycle-accurate simulator. The assembler is equipped with some meta-instructions, which allow to use all advanced possibilities of the EMPA architecture, and at the same time provide a (nearly) conventional-style programming. The cycle accurate simulator is able to execute the EMPA-aware object code, and is a good tool for developing algorithms for EMPA
On Simulated Annealing Dedicated to Maximin Latin Hypercube Designs
Venue: arXiv cs.AI 2016
Year: 2016

The goal of our research was to enhance local search heuristics used to construct Latin Hypercube Designs. First, we introduce the \textit{1D-move} perturbation to improve the space exploration performed by these algorithms. Second, we propose a new evaluation function $ψ_{p,σ}$ specifically targeting the Maximin criterion. Exhaustive series of experiments with Simulated Annealing, which we used as a typically well-behaving local search heuristics, confirm that our goal was reached as the result we obtained surpasses the best scores reported in the literature. Furthermore, the $ψ_{p,σ}$ function seems very promising for a wide spectrum of optimization problems through the Maximin criterion.
Reduction of Self-heating effect in LDMOS devices
Venue: arXiv cs.ET 2016
Year: 2016

Isotopic purification of group IV elements leads to substantial increase in thermal conductivity due to reduced scattering of the phonons. Based on this concept, a simulation study is used to demonstrate the reduction of at least 25 oC in LDMOS average temperature.
Type Inference for Static Compilation of JavaScript (Extended Version)
Venue: arXiv cs.PL 2016
Year: 2016

We present a type system and inference algorithm for a rich subset of JavaScript equipped with objects, structural subtyping, prototype inheritance, and first-class methods. The type system supports abstract and recursive objects, and is expressive enough to accommodate several standard benchmarks with only minor workarounds. The invariants enforced by the types enable an ahead-of-time compiler to carry out optimizations typically beyond the reach of static compilers for dynamic languages. Unlike previous inference techniques for prototype inheritance, our algorithm uses a combination of lower and upper bound propagation to infer types and discover type errors in all code, including uninvoked functions. The inference is expressed in a simple constraint language, designed to leverage off-the-shelf fixed point solvers. We prove soundness for both the type system and inference algorithm. An experimental evaluation showed that the inference is powerful, handling the aforementioned benchmarks with no manual type annotation, and that the inferred types enable effective static compilation.
Cloud Radio Access Networks: Uplink Channel Estimation and Downlink Precoding
Venue: arXiv cs.IT 2016
Year: 2016

The gains afforded by cloud radio access network (C-RAN) in terms of savings in capital and operating expenses, flexibility, interference management and network densification rely on the presence of high-capacity low-latency fronthaul connectivity between remote radio heads (RRHs) and baseband unit (BBU). In light of the non-uniform and limited availability of fiber optics cables, the bandwidth constraints on the fronthaul network call, on the one hand, for the development of advanced baseband compression strategies and, on the other hand, for a closer investigation of the optimal functional split between RRHs and BBU. In this chapter, after a brief introduction to signal processing challenges in C-RAN, this optimal function split is studied at the physical (PHY) layer as it pertains to two key baseband signal processing steps, namely channel estimation in the uplink and channel encoding/ linear precoding in the downlink. Joint optimization of baseband fronthaul compression and of baseband signal processing is tackled under different PHY functional splits, whereby uplink channel estimation and downlink channel encoding/ linear precoding are carried out either at the RRHs or at the BBU. The analysis, based on information-theoretical arguments, and numerical results yields insight into the configurations of network architecture and fronthaul capacities in which different functional splits are advantageous. The treatment also emphasizes the versatility of deterministic and stochastic successive convex approximation strategies for the optimization of C-RANs.
Tracing technological development trajectories: A genetic knowledge persistence-based main path approach
Venue: arXiv cs.CY 2016
Year: 2016

The aim of this paper is to propose a new method to identify main paths in a technological domain using patent citations. Previous approaches for using main path analysis have greatly improved our understanding of actual technological trajectories but nonetheless have some limitations. They have high potential to miss some dominant patents from the identified main paths; nonetheless, the high network complexity of their main paths makes qualitative tracing of trajectories problematic. The proposed method searches backward and forward paths from the high-persistence patents which are identified based on a standard genetic knowledge persistence algorithm. We tested the new method by applying it to the desalination and the solar photovoltaic domains and compared the results to output from the same domains using a prior method. The empirical results show that the proposed method overcomes the aforementioned drawbacks defining main paths that are almost 10x less complex while containing more of the relevant important knowledge than the main path networks defined by the existing method.
Applying Topological Persistence in Convolutional Neural Network for Music Audio Signals
Venue: arXiv cs.NE 2016
Year: 2016

Recent years have witnessed an increased interest in the application of persistent homology, a topological tool for data analysis, to machine learning problems. Persistent homology is known for its ability to numerically characterize the shapes of spaces induced by features or functions. On the other hand, deep neural networks have been shown effective in various tasks. To our best knowledge, however, existing neural network models seldom exploit shape information. In this paper, we investigate a way to use persistent homology in the framework of deep neural networks. Specifically, we propose to embed the so-called "persistence landscape," a rather new topological summary for data, into a convolutional neural network (CNN) for dealing with audio signals. Our evaluation on automatic music tagging, a multi-label classification task, shows that the resulting persistent convolutional neural network (PCNN) model can perform significantly better than state-of-the-art models in prediction accuracy. We also discuss the intuition behind the design of the proposed model, and offer insights into the features that it learns.
Topological aggregation, the twin paradox and the no show paradox
Venue: arXiv cs.GT 2016
Year: 2016

Consider the framework of topological aggregation introduced by Chichilnisky (1980). We prove that in this framework the Twin Paradox and the No Show Paradox cannot be avoided. Anonymity and unanimity are not needed to obtain these results.
#P- and $\oplus$P- completeness of counting roots of a sparse polynomial
Venue: arXiv cs.CC 2016
Year: 2016

We improve and simplify the result of the part 4 of "Counting curves and their projections" (Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski) by showing that counting roots of a sparse polynomial over $\mathbb{F}_{2^n}$ is #P- and $\oplus$P-complete under deterministic reductions.
Graphic TSP in cubic graphs
Venue: arXiv cs.DM 2016
Year: 2016

We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.