OpenRaiser/Intern-Atlas huggingface dataset:
Supporting Mobile Multimodal Interaction with a Rule-Based Framework
Venue: arXiv cs.HC 2014
Year: 2014

Multimodality can make (especially mobile) device interaction more efficient. Sensors and communication capabilities of modern smartphones and tablets lay the technical basis for its implementation. Still, mobile platforms do not make multimodal interaction support trivial. Building multimodal applications requires various APIs with different paradigms, high-level interpretation of contextual data, and a method for fusing individual inputs and outputs. To reduce this effort, we created a framework that simplifies and accelerates the creation of multimodal applications for prototyping and research. It provides an abstraction of information representations in different modalities, unifies access to implicit and explicit information, and wires together the logic behind context-sensitive modality switches. In the paper, we present the structure and features of our framework, and validate it by four implemented demonstrations of different complexity.
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Venue: arXiv cs.CC 2014
Year: 2014

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT($\cdot$) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation $R$ such that SAT($R$) can be solved at least as fast as any other NP-hard SAT($\cdot$) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (MaxOnes($Γ$)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP($Δ$)). With the help of these languages we relate MaxOnes and VCSP to the exponential time hypothesis in several different ways.
Convolutional Kernel Networks
Venue: arXiv cs.CV 2014
Year: 2014

An important goal in visual recognition is to devise image representations that are invariant to particular transformations. In this paper, we address this goal with a new type of convolutional neural network (CNN) whose invariance is encoded by a reproducing kernel. Unlike traditional approaches where neural networks are learned either to represent data or for solving a classification task, our network learns to approximate the kernel feature map on training data. Such an approach enjoys several benefits over classical ones. First, by teaching CNNs to be invariant, we obtain simple network architectures that achieve a similar accuracy to more complex ones, while being easy to train and robust to overfitting. Second, we bridge a gap between the neural network literature and kernels, which are natural tools to model invariance. We evaluate our methodology on visual recognition tasks where CNNs have proven to perform well, e.g., digit recognition with the MNIST dataset, and the more challenging CIFAR-10 and STL-10 datasets, where our accuracy is competitive with the state of the art.
The Degrees-of-Freedom of Multi-way Device-to-Device Communications is Limited by 2
Venue: arXiv cs.IT 2014
Year: 2014

A 3-user device-to-device (D2D) communications scenario is studied where each user wants to send and receive a message from each other user. This scenario resembles a 3-way communication channel. The capacity of this channel is unknown in general. In this paper, a sum-capacity upper bound that characterizes the degrees-of-freedom of the channel is derived by using genie-aided arguments. It is further shown that the derived upper bound is achievable within a gap of 2 bits, thus leading to an approximate sum-capacity characterization for the 3-way channel. As a by-product, interesting analogies between multi-way communications and multi-way relay communications are concluded.
Are Style Guides Controlled Languages? The Case of Koenig & Bauer AG
Venue: arXiv cs.CL 2014
Year: 2014

Controlled natural languages for industrial application are often regarded as a response to the challenges of translation and multilingual communication. This paper presents a quite different approach taken by Koenig & Bauer AG, where the main goal was the improvement of the authoring process for technical documentation. Most importantly, this paper explores the notion of a controlled language and demonstrates how style guides can emerge from non-linguistic considerations. Moreover, it shows the transition from loose language recommendations into precise and prescriptive rules and investigates whether such rules can be regarded as a full-fledged controlled language.
Session Types for Broadcasting
Venue: arXiv cs.PL 2014
Year: 2014

Up to now session types have been used under the assumptions of point to point communication, to ensure the linearity of session endpoints, and reliable communication, to ensure send/receive duality. In this paper we define a session type theory for broadcast communication semantics that by definition do not assume point to point and reliable communication. Our session framework lies on top of the parametric framework of broadcasting psi-calculi, giving insights on developing session types within a parametric framework. Our session type theory enjoys the properties of soundness and safety. We further believe that the solutions proposed will eventually provide a deeper understanding of how session types principles should be applied in the general case of communication semantics.
An $H_{n/2}$ Upper Bound on the Price of Stability of Undirected Network Design Games
Venue: arXiv cs.GT 2014
Year: 2014

In the network design game with $n$ players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. We study the price of stability of the game, i.e., the ratio of the social costs of a best Nash equilibrium (with respect to the social cost) and of an optimal play. It has been shown that the price of stability of any network design game is at most $H_n$, the $n$-th harmonic number. This bound is tight for directed graphs. For undirected graphs, the situation is dramatically different, and tight bounds are not known. It has only recently been shown that the price of stability is at most $H_n \left(1-\frac{1}{Θ(n^4)} \right)$, while the worst-case known example has price of stability around 2.25. In this paper we improve the upper bound considerably by showing that the price of stability is at most $H_{n/2} + ε$ for any $ε$ starting from some suitable $n \geq n(ε)$.
Analysis of networking characteristics of different personality types
Venue: arXiv cs.SI 2014
Year: 2014

The MBTI personality test and a personal facebook network were used in order to gain some insights on the relationship of social network centrality and path length measures and different personality types. Although the personality classification data were scarce, there were some intuitive quantitative results supporting anecdotal statements, based on empirical observations, about the expected social behavior of personality types.
Evaluation of Machine Learning Techniques for Green Energy Prediction
Venue: arXiv cs.LG 2014
Year: 2014

We evaluate the following Machine Learning techniques for Green Energy (Wind, Solar) Prediction: Bayesian Inference, Neural Networks, Support Vector Machines, Clustering techniques (PCA). Our objective is to predict green energy using weather forecasts, predict deviations from forecast green energy, find correlation amongst different weather parameters and green energy availability, recover lost or missing energy (/ weather) data. We use historical weather data and weather forecasts for the same.
Modelling, Visualising and Summarising Documents with a Single Convolutional Neural Network
Venue: arXiv cs.CL 2014
Year: 2014

Capturing the compositional process which maps the meaning of words to that of documents is a central challenge for researchers in Natural Language Processing and Information Retrieval. We introduce a model that is able to represent the meaning of documents by embedding them in a low dimensional vector space, while preserving distinctions of word and sentence order crucial for capturing nuanced semantics. Our model is based on an extended Dynamic Convolution Neural Network, which learns convolution filters at both the sentence and document level, hierarchically learning to capture and compose low level lexical features into high level semantic concepts. We demonstrate the effectiveness of this model on a range of document modelling tasks, achieving strong results with no feature engineering and with a more compact model. Inspired by recent advances in visualising deep convolution networks for computer vision, we present a novel visualisation technique for our document networks which not only provides insight into their learning process, but also can be interpreted to produce a compelling automatic summarisation system for texts.
Eclipse Hashing: Alexandrov Compactification and Hashing with Hyperspheres for Fast Similarity Search
Venue: arXiv cs.IR 2014
Year: 2014

The similarity searches that use high-dimensional feature vectors consisting of a vast amount of data have a wide range of application. One way of conducting a fast similarity search is to transform the feature vectors into binary vectors and perform the similarity search by using the Hamming distance. Such a transformation is a hashing method, and the choice of hashing function is important. Hashing methods using hyperplanes or hyperspheres are proposed. One study reported here is inspired by Spherical LSH, and we use hypersperes to hash the feature vectors. Our method, called Eclipse-hashing, performs a compactification of R^n by using the inverse stereographic projection, which is a kind of Alexandrov compactification. By using Eclipse-hashing, one can obtain the hypersphere-hash function without explicitly using hyperspheres. Hence, the number of nonlinear operations is reduced and the processing time of hashing becomes shorter. Furthermore, we also show that as a result of improving the approximation accuracy, Eclipse-hashing is more accurate than hyperplane-hashing.
The Laplacian K-modes algorithm for clustering
Venue: arXiv cs.LG 2014
Year: 2014

In addition to finding meaningful clusters, centroid-based clustering algorithms such as K-means or mean-shift should ideally find centroids that are valid patterns in the input space, representative of data in their cluster. This is challenging with data having a nonconvex or manifold structure, as with images or text. We introduce a new algorithm, Laplacian K-modes, which naturally combines three powerful ideas in clustering: the explicit use of assignment variables (as in K-means); the estimation of cluster centroids which are modes of each cluster's density estimate (as in mean-shift); and the regularizing effect of the graph Laplacian, which encourages similar assignments for nearby points (as in spectral clustering). The optimization algorithm alternates an assignment step, which is a convex quadratic program, and a mean-shift step, which separates for each cluster centroid. The algorithm finds meaningful density estimates for each cluster, even with challenging problems where the clusters have manifold structure, are highly nonconvex or in high dimension. It also provides centroids that are valid patterns, truly representative of their cluster (unlike K-means), and an out-of-sample mapping that predicts soft assignments for a new point.
Translation Of Telugu-Marathi and Vice-Versa using Rule Based Machine Translation
Venue: arXiv cs.CL 2014
Year: 2014

In todays digital world automated Machine Translation of one language to another has covered a long way to achieve different kinds of success stories. Whereas Babel Fish supports a good number of foreign languages and only Hindi from Indian languages, the Google Translator takes care of about 10 Indian languages. Though most of the Automated Machine Translation Systems are doing well but handling Indian languages needs a major care while handling the local proverbs/ idioms. Most of the Machine Translation system follows the direct translation approach while translating one Indian language to other. Our research at KMIT R&D Lab found that handling the local proverbs/idioms is not given enough attention by the earlier research work. This paper focuses on two of the majorly spoken Indian languages Marathi and Telugu, and translation between them. Handling proverbs and idioms of both the languages have been given a special care, and the research outcome shows a significant achievement in this direction.
Handling non-compositionality in multilingual CNLs
Venue: arXiv cs.CL 2014
Year: 2014

In this paper, we describe methods for handling multilingual non-compositional constructions in the framework of GF. We specifically look at methods to detect and extract non-compositional phrases from parallel texts and propose methods to handle such constructions in GF grammars. We expect that the methods to handle non-compositional constructions will enrich CNLs by providing more flexibility in the design of controlled languages. We look at two specific use cases of non-compositional constructions: a general-purpose method to detect and extract multilingual multiword expressions and a procedure to identify nominal compounds in German. We evaluate our procedure for multiword expressions by performing a qualitative analysis of the results. For the experiments on nominal compounds, we incorporate the detected compounds in a full SMT pipeline and evaluate the impact of our method in machine translation process.
Crypto-Book: Bootstrapping Privacy Preserving Online Identities from Social Networks
Venue: arXiv cs.CR 2014
Year: 2014

Social networking sites supporting federated identities offer a convenient and increasingly popular mechanism for cross-site authentication. Unfortunately, they also exacerbate many privacy and tracking risks. We propose Crypto-Book, an anonymizing layer enabling cross-site authentication while reducing these risks. Crypto-Book relies on a set of independently managed servers that collectively assign each social network identity a public/private keypair. Only an identity's owner learns all the private key shares, and can therefore construct the private key, while all participants can obtain any user's public key, even if the corresponding private key has yet to be retrieved. Having obtained an appropriate key set, a user can then leverage anonymous authentication techniques such as linkable ring signatures to log into third-party web sites while preserving privacy. We have implemented a prototype of Crypto-Book and demonstrate its use with three applications: a Wiki system, an anonymous group communication system, and a whistleblower submission system. Our results show that for anonymity sets of size 100, Crypto-Book login takes 0.56s for signature generation by the client, 0.38s for signature verification on the server, and requires 5.6KB of communication bandwidth.
An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
Venue: arXiv cs.DS 2014
Year: 2014

In the $k$-median problem, given a set of locations, the goal is to select a subset of at most $k$ centers so as to minimize the total cost of connecting each location to its nearest center. We study the uniform hard capacitated version of the $k$-median problem, in which each selected center can only serve a limited number of locations. Inspired by the algorithm of Charikar, Guha, Tardos and Shmoys, we give a $(6+10α)$-approximation algorithm for this problem with increasing the capacities by a factor of $2+\frac{2}α, α\geq 4$, which improves the previous best $(32 l^2+28 l+7)$-approximation algorithm proposed by Byrka, Fleszar, Rybicki and Spoerhase violating the capacities by factor $2+\frac{3}{l-1}, l\in \{2,3,4,\dots\}$.
A Generalized Markov-Chain Modelling Approach to $(1,λ)$-ES Linear Optimization: Technical Report
Venue: arXiv cs.NA 2014
Year: 2014

Several recent publications investigated Markov-chain modelling of linear optimization by a $(1,λ)$-ES, considering both unconstrained and linearly constrained optimization, and both constant and varying step size. All of them assume normality of the involved random steps, and while this is consistent with a black-box scenario, information on the function to be optimized (e.g. separability) may be exploited by the use of another distribution. The objective of our contribution is to complement previous studies realized with normal steps, and to give sufficient conditions on the distribution of the random steps for the success of a constant step-size $(1,λ)$-ES on the simple problem of a linear function with a linear constraint. The decomposition of a multidimensional distribution into its marginals and the copula combining them is applied to the new distributional assumptions, particular attention being paid to distributions with Archimedean copulas.
Comments on "A model-based design methodology for the development of mechatronic systems"
Venue: arXiv cs.SE 2014
Year: 2014

In the paper by G. Barbieri et al. (Mechatronics (2014), http://dx.doi.org/10.1016/j.mechatronics. 2013.12.004), a design methodology, based on the W life cycle process model, is presented and SysML is proposed as a tool to support the whole development process. In this letter, we discuss the presented approach, we point out technical errors and raise additional issues that might help in making the proposed approach applicable.
Analysis and Study of Incremental DBSCAN Clustering Algorithm
Venue: arXiv cs.DB 2014
Year: 2014

This paper describes the incremental behaviours of Density based clustering. It specially focuses on the Density Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm and its incremental approach.DBSCAN relies on a density based notion of clusters.It discovers clusters of arbitrary shapes in spatial databases with noise.In incremental approach, the DBSCAN algorithm is applied to a dynamic database where the data may be frequently updated. After insertions or deletions to the dynamic database, the clustering discovered by DBSCAN has to be updated. And we measure the new cluster by directly compute the new data entering into the existing clusters instead of rerunning the algorithm.It finally discovers new updated clusters and outliers as well.Thus it describes at what percent of delta change in the original database the actual and incremental DBSCAN algorithms behave like same.DBSCAN is widely used in those situations where large multidimensional databases are maintained such as Data Warehouse.
Weather Forecasting using Incremental K-means Clustering
Venue: arXiv cs.CY 2014
Year: 2014

Clustering is a powerful tool which has been used in several forecasting works, such as time series forecasting, real time storm detection, flood forecasting and so on. In this paper, a generic methodology for weather forecasting is proposed by the help of incremental K-means clustering algorithm. Weather forecasting plays an important role in day to day applications.Weather forecasting of this paper is done based on the incremental air pollution database of west Bengal in the years of 2009 and 2010. This paper generally uses typical K-means clustering on the main air pollution database and a list of weather category will be developed based on the maximum mean values of the clusters.Now when the new data are coming, the incremental K-means is used to group those data into those clusters whose weather category has been already defined. Thus it builds up a strategy to predict the weather of the upcoming data of the upcoming days. This forecasting database is totally based on the weather of west Bengal and this forecasting methodology is developed to mitigating the impacts of air pollutions and launch focused modeling computations for prediction and forecasts of weather events. Here accuracy of this approach is also measured.
Mass Classification Method in Mammogram Using Fuzzy K-Nearest Neighbour Equality
Venue: arXiv cs.CV 2014
Year: 2014

Mass classification of objects is an important area of research and application in a variety of fields. In this paper, we present an efficient computer aided mass classification method in digitized mammograms using Fuzzy K-Nearest Neighbor Equality, which performs benign or malignant classification on region of interest that contains mass. One of the major mammographic characteristics for mass classification is texture. Fuzzy K-Nearest Neighbor Equality exploits this important factor to classify the mass into benign or malignant. The statistical textural features used in characterizing the masses are Haralick and Run length features. The main aim of the method is to increase the effectiveness and efficiency of the classification process in an objective manner to reduce the numbers of false positive of malignancies. In this paper proposes a novel Fuzzy K-Nearest Neighbor Equality algorithm for classifying the marked regions into benign and malignant and 94.46 sensitivity,96.81 specificity and 96.52 accuracy is achieved that is very much promising compare to the radiologists' accuracy.
Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
Venue: arXiv cs.IT 2014
Year: 2014

Principal component analysis (PCA) aims at estimating the direction of maximal variability of a high-dimensional dataset. A natural question is: does this task become easier, and estimation more accurate, when we exploit additional knowledge on the principal vector? We study the case in which the principal vector is known to lie in the positive orthant. Similar constraints arise in a number of applications, ranging from analysis of gene expression data to spike sorting in neural signal processing. In the unconstrained case, the estimation performances of PCA has been precisely characterized using random matrix theory, under a statistical model known as the `spiked model.' It is known that the estimation error undergoes a phase transition as the signal-to-noise ratio crosses a certain threshold. Unfortunately, tools from random matrix theory have no bearing on the constrained problem. Despite this challenge, we develop an analogous characterization in the constrained case, within a one-spike model. In particular: $(i)$~We prove that the estimation error undergoes a similar phase transition, albeit at a different threshold in signal-to-noise ratio that we determine exactly; $(ii)$~We prove that --unlike in the unconstrained case-- estimation error depends on the spike vector, and characterize the least favorable vectors; $(iii)$~We show that a non-negative principal component can be approximately computed --under the spiked model-- in nearly linear time. This despite the fact that the problem is non-convex and, in general, NP-hard to solve exactly.