OpenRaiser/Intern-Atlas huggingface dataset:
Bayesian Neighbourhood Component Analysis
Venue: arXiv cs.CV 2016
Year: 2016

Learning a good distance metric in feature space potentially improves the performance of the KNN classifier and is useful in many real-world applications. Many metric learning algorithms are however based on the point estimation of a quadratic optimization problem, which is time-consuming, susceptible to overfitting, and lack a natural mechanism to reason with parameter uncertainty, an important property useful especially when the training set is small and/or noisy. To deal with these issues, we present a novel Bayesian metric learning method, called Bayesian NCA, based on the well-known Neighbourhood Component Analysis method, in which the metric posterior is characterized by the local label consistency constraints of observations, encoded with a similarity graph instead of independent pairwise constraints. For efficient Bayesian optimization, we explore the variational lower bound over the log-likelihood of the original NCA objective. Experiments on several publicly available datasets demonstrate that the proposed method is able to learn robust metric measures from small size dataset and/or from challenging training set with labels contaminated by errors. The proposed method is also shown to outperform a previous pairwise constrained Bayesian metric learning method.
The (1+1) Elitist Black-Box Complexity of LeadingOnes
Venue: arXiv cs.NE 2016
Year: 2016

One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the $Ω(n \log n)$ lower bound for unary unbiased algorithms on functions with a unique global optimum [Lehre/Witt, GECCO 2010], which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, almost no non-trivial bounds are known for other restricted models. Proving such bounds therefore remains to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of \textsc{LeadingOnes} and prove that its (1+1) elitist black-box complexity is $Ω(n^2)$, a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of \textsc{LeadingOnes} is thus considerably larger than its unrestricted one, which is known to be of order $n\log\log n$ [Afshani et al., 2013].
A Hybrid Classification Algorithm to Classify Engineering Students' Problems and Perks
Venue: arXiv cs.CY 2016
Year: 2016

The social networking sites have brought a new horizon for expressing views and opinions of individuals. Moreover, they provide medium to students to share their sentiments including struggles and joy during the learning process. Such informal information has a great venue for decision making. The large and growing scale of information needs automatic classification techniques. Sentiment analysis is one of the automated techniques to classify large data. The existing predictive sentiment analysis techniques are highly used to classify reviews on E-commerce sites to provide business intelligence. However, they are not much useful to draw decisions in education system since they classify the sentiments into merely three preset categories: positive, negative and neutral. Moreover, classifying the students sentiments into positive or negative category does not provide deeper insight into their problems and perks. In this paper, we propose a novel Hybrid Classification Algorithm to classify engineering students sentiments. Unlike traditional predictive sentiment analysis techniques, the proposed algorithm makes sentiment analysis process descriptive. Moreover, it classifies engineering students perks in addition to problems into several categories to help future students and education system in decision making.
An extensible formal semantics for UML activity diagrams
Venue: arXiv cs.LO 2016
Year: 2016

This paper presents an operational semantics for UML activity diagrams. The purpose of this semantics is three-fold: to give a robust basis for verifying model correctness; to help validate model transformations; and to provide a well-formed basis for assessing whether a proposed extension/interpretation of the modeling language is consistent with the standard. The challenges of a general formal framework for UML models include the semi-formality of the semantics specification, the extensibility of the language, and (sometimes deliberate, sometimes accidental) under-specification of model behavior in the standard. Our approach is based on structural operational semantics, which can be extended according to domain-specific needs. The presented semantics has been implemented and tested.
How deep is knowledge tracing?
Venue: arXiv cs.AI 2016
Year: 2016

In theoretical cognitive science, there is a tension between highly structured models whose parameters have a direct psychological interpretation and highly complex, general-purpose models whose parameters and representations are difficult to interpret. The former typically provide more insight into cognition but the latter often perform better. This tension has recently surfaced in the realm of educational data mining, where a deep learning approach to predicting students' performance as they work through a series of exercises---termed deep knowledge tracing or DKT---has demonstrated a stunning performance advantage over the mainstay of the field, Bayesian knowledge tracing or BKT. In this article, we attempt to understand the basis for DKT's advantage by considering the sources of statistical regularity in the data that DKT can leverage but which BKT cannot. We hypothesize four forms of regularity that BKT fails to exploit: recency effects, the contextualized trial sequence, inter-skill similarity, and individual variation in ability. We demonstrate that when BKT is extended to allow it more flexibility in modeling statistical regularities---using extensions previously proposed in the literature---BKT achieves a level of performance indistinguishable from that of DKT. We argue that while DKT is a powerful, useful, general-purpose framework for modeling student learning, its gains do not come from the discovery of novel representations---the fundamental advantage of deep learning. To answer the question posed in our title, knowledge tracing may be a domain that does not require `depth'; shallow models like BKT can perform just as well and offer us greater interpretability and explanatory power.
One-class classifiers based on entropic spanning graphs
Venue: arXiv cs.LG 2016
Year: 2016

One-class classifiers offer valuable tools to assess the presence of outliers in data. In this paper, we propose a design methodology for one-class classifiers based on entropic spanning graphs. Our approach takes into account the possibility to process also non-numeric data by means of an embedding procedure. The spanning graph is learned on the embedded input data and the outcoming partition of vertices defines the classifier. The final partition is derived by exploiting a criterion based on mutual information minimization. Here, we compute the mutual information by using a convenient formulation provided in terms of the $α$-Jensen difference. Once training is completed, in order to associate a confidence level with the classifier decision, a graph-based fuzzy model is constructed. The fuzzification process is based only on topological information of the vertices of the entropic spanning graph. As such, the proposed one-class classifier is suitable also for data characterized by complex geometric structures. We provide experiments on well-known benchmarks containing both feature vectors and labeled graphs. In addition, we apply the method to the protein solubility recognition problem by considering several representations for the input samples. Experimental results demonstrate the effectiveness and versatility of the proposed method with respect to other state-of-the-art approaches.
Optimal Design of Compact Receive Array in Industrial Wireless Sensor Networks
Venue: arXiv cs.IT 2016
Year: 2016

With the development of wireless communication, industrial wireless sensor networks (IWSNs) plays an important role in monitoring and control systems. In this paper, we extend the application of IWSNs into High Frequency Surface-Wave Radar (HFSWR) system. The traditional antenna is replaced by mobile IWSNs. In combination of the application precondition of super-directivity in HF band and circular topology of IWSNs, a super-directivity synthesis method is presented for designing super-directivity array. In this method, the dominance of external noise is ensured by constraining the Ratio of External to Internal Noise (REIN) of the array, and the desired side lobe level is achieved by implementing linear constraint. By using this method, the highest directivity will be achieved in certain conditions. Using the designed super directive circular array as sub-arrays, the compact receive antenna array is constructed, the purpose of miniaturization is achieved. Simulation verifies that the proposed method is correct and effective, the validity of the proposed method has been proved.
Wirelessly Powered Backscatter Communication Networks: Modeling, Coverage and Capacity
Venue: arXiv cs.IT 2016
Year: 2016

Future Internet-of-Things (IoT) will connect billions of small computing devices embedded in the environment and support their device-to-device (D2D) communication. Powering this massive number of embedded devices is a key challenge of designing IoT since batteries increase the devices' form factors and their recharging/replacement is difficult. To tackle this challenge, we propose a novel network architecture that integrates wireless power transfer and backscatter communication, called wirelessly powered backscatter communication (WP-BC) networks. In this architecture, power beacons (PBs) are deployed for wirelessly powering devices; their ad-hoc communication relies on backscattering and modulating incident continuous waves from PBs, which consumes orders-of-magnitude less power than traditional radios. Thereby, the dense deployment of low-complexity PBs with high transmission power can power a large-scale IoT. In this paper, a WP-BC network is modeled as a random Poisson cluster process in the horizontal plane where PBs are Poisson distributed and active ad-hoc pairs of backscatter communication nodes with fixed separation distances form random clusters centered at PBs. Furthermore, by harvesting energy from and backscattering radio frequency (RF) waves transmitted by PBs, the transmission power of each node depends on the distance from the associated PB. Applying stochastic geometry, the network coverage probability and transmission capacity are derived and optimized as functions of the backscatter duty cycle and reflection coefficient as well as the PB density. The effects of the parameters on network performance are characterized.
A Left-Looking Selected Inversion Algorithm and Task Parallelism on Shared Memory Systems
Venue: arXiv cs.MS 2016
Year: 2016

Given a sparse matrix $A$, the selected inversion algorithm is an efficient method for computing certain selected elements of $A^{-1}$. These selected elements correspond to all or some nonzero elements of the LU factors of $A$. In many ways, the type of matrix updates performed in the selected inversion algorithm is similar to that performed in the LU factorization, although the sequence of operation is different. In the context of LU factorization, it is known that the left-looking and right-looking algorithms exhibit different memory access and data communication patterns, and hence different behavior on shared memory and distributed memory parallel machines. Corresponding to right-looking and left-looking LU factorization, selected inversion algorithm can be organized as a left-looking and a right-looking algorithm. The parallel right-looking version of the algorithm has been developed in [1]. The sequence of operations performed in this version of the selected inversion algorithm is similar to those performed in a left-looking LU factorization algorithm. In this paper, we describe the left-looking variant of the selected inversion algorithm, and based on task parallel method, present an efficient implementation of the algorithm for shared memory machines. We demonstrate that with the task scheduling features provided by OpenMP 4.0, the left-looking selected inversion algorithm can scale well both on the Intel Haswell multicore architecture and on the Intel Knights Corner (KNC) manycore architecture. Compared to the right-looking selected inversion algorithm, the left-looking formulation facilitates pipelining of work along different branches of the elimination tree, and can be a promising candidate for future development of massively parallel selected inversion algorithms on heterogeneous architecture.
Joint Data Purchasing and Data Placement in a Geo-Distributed Data Market
Venue: arXiv cs.DC 2016
Year: 2016

This paper studies two design tasks faced by a geo-distributed cloud data market: which data to purchase (data purchasing) and where to place/replicate the data for delivery (data placement). We show that the joint problem of data purchasing and data placement within a cloud data market can be viewed as a facility location problem, and is thus NP-hard. However, we give a provably optimal algorithm for the case of a data market made up of a single data center, and then generalize the structure from the single data center setting in order to develop a near-optimal, polynomial-time algorithm for a geo-distributed data market. The resulting design, Datum, decomposes the joint purchasing and placement problem into two subproblems, one for data purchasing and one for data placement, using a transformation of the underlying bandwidth costs. We show, via a case study, that Datum is near-optimal (within 1.6%) in practical settings.
Vehicular Communications for 5G Cooperative Small Cell Networks
Venue: arXiv cs.NI 2016
Year: 2016

The cooperative transmission is an effective approach for vehicular communications to improve the wireless transmission capacity and reliability in the fifth generation (5G) small cell networks. Based on distances between the vehicle and cooperative small cell BSs, the cooperative probability and the coverage probability have been derived for 5G cooperative small cell networks where small cell base stations (BSs) follow Poisson point process distributions. Furthermore, the vehicular handoff rate and the vehicular overhead ratio have been proposed to evaluate the vehicular mobility performance in 5G cooperative small cell networks. To balance the vehicular communication capacity and the vehicular handoff ratio, an optimal vehicular overhead ratio can be achieved by adjusting the cooperative threshold of 5G cooperative small cell networks.
Private Web Search with an Expected Constant Round
Venue: arXiv cs.CR 2016
Year: 2016

Web searching is becoming an essential activity because it is often the most effective and convenient way of finding information. However, a Web search can be a threat to the privacy of the searcher because the queries may reveal sensitive information about the searcher. Private Web search (PWS) solutions allow users to find information on the Internet while preserving their privacy. Here, privacy means maintaining the confidentiality of the identity of the communicating users. According to their underlying technology, existing PWS solutions can be divided into three types: proxy-based solutions, obfuscation-based solutions, and cryptography-based solutions. Of these, cryptography-based PWS (CB-PWS) systems are particularly interesting because they provide strong privacy guarantees in the cryptographic sense. In this paper, we present a round-efficient CB-PWS protocol that preserves computational efficiency compared to other known CB-PWS systems. Assuming a broadcast channel, our protocol is a \emph{four-round} cryptographic scheme that requires $O(n)$ communication complexity. However, if only point-to-point interaction is available, with the users emulating the broadcast channel, our protocol requires an expected $O(1)$-round complexity and the same computation and communication overhead. Further analyzing the efficiency of our protocol shows that our proposal requires only $3n$ modular exponentiations for $n$ users. To evaluate the security of our protocol, we demonstrate that our construction is secure in terms of a semi-honest model. We then discuss how to enhance its security to render it secure in the presence of malicious adversaries. We provide a specific protocol for managing users' groups, which is also an advantage over existing systems.
Coverage Analysis of Heterogeneous Cellular Networks in Urban Areas
Venue: arXiv cs.NI 2016
Year: 2016

In this article, a network model incorporating both line-of-sight (LOS) and non-line-of-sight (NLOS) transmissions is proposed to investigate impacts of blockages in urban areas on heterogeneous network coverage performance. Results show that co-existence of NLOS and LOS transmissions has a significant impact on network performance. We find in urban areas, that deploying more BSs in different tiers is better than merely deploying all BSs in the same tier in terms of coverage probability.
Optical Fiber MIMO Channel Model and its Analysis
Venue: arXiv cs.IT 2016
Year: 2016

Technology is moving towards space division multiplexing in optical fiber to keep up the trend in rate increase over time and to avoid an imminent capacity crunch. Thus, it is of paramount interest to estimate the potential gains of this approach. As more spatial channels are being packed into a single fiber, the increased crosstalk necessitates the use of MIMO to guarantee reliable operation. In this paper, we exploit the analogy between an optical fiber and a model from mesoscopic physics - a chaotic cavity - to obtain a novel channel model for the optical fiber. The model captures both random distributed crosstalk and modedependent loss, which are described within the framework of scattering theory. Using tools from replica theory and random matrix theory, we derive the capacity of the fiber optical MIMO channel model.
Distributed Technology-Sustained Pervasive Applications
Venue: arXiv cs.CY 2016
Year: 2016

Technology-sustained pervasive games, contrary to technology-supported pervasive games, can be understood as computer games interfacing with the physical world. Pervasive games are known to make use of 'non-standard input devices' and with the rise of the Internet of Things (IoT), pervasive applications can be expected to move beyond games. This dissertation is requirements- and development-focused Design Science research for distributed technology-sustained pervasive applications, incorporating knowledge from the domains of Distributed Computing, Mixed Reality, Context-Aware Computing, Geographical Information Systems and IoT. Computer video games have existed for decades, with a reusable game engine to drive them. If pervasive games can be understood as computer games interfacing with the physical world, can computer game engines be used to stage pervasive games? Considering the use of non-standard input devices in pervasive games and the rise of IoT, how will this affect the architectures supporting the broader set of pervasive applications? The use of a game engine can be found in some existing pervasive game projects, but general research into how the domain of pervasive games overlaps with that of video games is lacking. When an engine is used, a discussion of, what type of engine is most suitable and what properties are being fulfilled by the engine, is often not part of the discourse. This dissertation uses multiple iterations of the method framework for Design Science for the design and development of three software system architectures. In the face of IoT, the problem of extending pervasive games into a fourth software architecture, accommodating a broader set of pervasive applications, is explicated. The requirements, for technology-sustained pervasive games, are verified through the design, development and demonstration of the three software system architectures. The ...
Statistics of RGBD Images
Venue: arXiv cs.CV 2016
Year: 2016

Cameras that can measure the depth of each pixel in addition to its color have become easily available and are used in many consumer products worldwide. Often the depth channel is captured at lower quality compared to the RGB channels and different algorithms have been proposed to improve the quality of the D channel given the RGB channels. Typically these approaches work by assuming that edges in RGB are correlated with edges in D. In this paper we approach this problem from the standpoint of natural image statistics. We obtain examples of high quality RGBD images from a computer graphics generated movie (MPI-Sintel) and we use these examples to compare different probabilistic generative models of RGBD image patches. We then use the generative models together with a degradation model and obtain a Bayes Least Squares (BLS) estimator of the D channel given the RGB channels. Our results show that learned generative models outperform the state-of-the-art in improving the quality of depth channels given the color channels in natural images even when training is performed on artificially generated images.
Kernel-based Sensor Fusion with Application to Audio-Visual Voice Activity Detection
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we address the problem of multiple view data fusion in the presence of noise and interferences. Recent studies have approached this problem using kernel methods, by relying particularly on a product of kernels constructed separately for each view. From a graph theory point of view, we analyze this fusion approach in a discrete setting. More specifically, based on a statistical model for the connectivity between data points, we propose an algorithm for the selection of the kernel bandwidth, a parameter, which, as we show, has important implications on the robustness of this fusion approach to interferences. Then, we consider the fusion of audio-visual speech signals measured by a single microphone and by a video camera pointed to the face of the speaker. Specifically, we address the task of voice activity detection, i.e., the detection of speech and non-speech segments, in the presence of structured interferences such as keyboard taps and office noise. We propose an algorithm for voice activity detection based on the audio-visual signal. Simulation results show that the proposed algorithm outperforms competing fusion and voice activity detection approaches. In addition, we demonstrate that a proper selection of the kernel bandwidth indeed leads to improved performance.
Three-Weight Ternary Linear Codes from a Family of Monomials
Venue: arXiv cs.IT 2016
Year: 2016

Based on a generic construction, two classes of ternary three-weight linear codes are obtained from a family of power functions, including some APN power functions. The weight distributions of these linear codes are determined through studying the properties of some exponential sum related to the proposed power functions.