OpenRaiser/Intern-Atlas huggingface dataset:
The Complexity of the Path-following Solutions of Two-dimensional Sperner/Brouwer Functions
Venue: arXiv cs.CC 2015
Year: 2015

There are a number of results saying that for certain "path-following" algorithms that solve PPAD-complete problems, the solution obtained by the algorithm is PSPACE-complete to compute. We conjecture that these results are special cases of a much more general principle, that all such algorithms compute PSPACE-complete solutions. Such a general result might shed new light on the complexity class PPAD. In this paper we present a new PSPACE-completeness result for an interesting challenge instance for this conjecture. Chen and Deng~\cite{CD} showed that it is PPAD-complete to find a trichromatic triangle in a concisely-represented Sperner triangulation. The proof of Sperner's lemma --- that such a solution always exists --- identifies one solution in particular, that is found via a natural "path-following" approach. Here we show that it is PSPACE-complete to compute this specific solution, together with a similar result for the computation of the path-following solution of two-dimensional discrete Brouwer functions.
Parsing Natural Language Sentences by Semi-supervised Methods
Venue: arXiv cs.CL 2015
Year: 2015

We present our work on semi-supervised parsing of natural language sentences, focusing on multi-source crosslingual transfer of delexicalized dependency parsers. We first evaluate the influence of treebank annotation styles on parsing performance, focusing on adposition attachment style. Then, we present KLcpos3, an empirical language similarity measure, designed and tuned for source parser weighting in multi-source delexicalized parser transfer. And finally, we introduce a novel resource combination method, based on interpolation of trained parser models.
LightPanel: Active Mobile Platform for Dense 3D Modelling
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we introduce a novel platform for dense 3D modelling. This platform is an active image acquisition setup assisted with a set of light sources and a distance sensor. The hardware setup is designed for being mounted on a mobile robot which is remotely driven to create accurate dense 3D models from out-of-reach objects. For this reason, the object is actively illuminated by the imaging setup and Photometric Stereo is used to recover the dense 3D model. The proposed image acquisition setup, called LightPanel, is described from design to calibration and discusses the practical challenges of using Photometric Stereo under uncontrolled lighting conditions.
A Tensor-Based Dictionary Learning Approach to Tomographic Image Reconstruction
Venue: arXiv cs.CV 2015
Year: 2015

We consider tomographic reconstruction using priors in the form of a dictionary learned from training images. The reconstruction has two stages: first we construct a tensor dictionary prior from our training data, and then we pose the reconstruction problem in terms of recovering the expansion coefficients in that dictionary. Our approach differs from past approaches in that a) we use a third-order tensor representation for our images and b) we recast the reconstruction problem using the tensor formulation. The dictionary learning problem is presented as a non-negative tensor factorization problem with sparsity constraints. The reconstruction problem is formulated in a convex optimization framework by looking for a solution with a sparse representation in the tensor dictionary. Numerical results show that our tensor formulation leads to very sparse representations of both the training images and the reconstructions due to the ability of representing repeated features compactly in the dictionary.
Efficient Ranking and Selection in Parallel Computing Environments
Venue: arXiv cs.DC 2015
Year: 2015

The goal of ranking and selection (R&S) procedures is to identify the best stochastic system from among a finite set of competing alternatives. Such procedures require constructing estimates of each system's performance, which can be obtained simultaneously by running multiple independent replications on a parallel computing platform. However, nontrivial statistical and implementation issues arise when designing R&S procedures for a parallel computing environment. Thus we propose several design principles for parallel R&S procedures that preserve statistical validity and maximize core utilization, especially when large numbers of alternatives or cores are involved. These principles are followed closely by our parallel Good Selection Procedure (GSP), which, under the assumption of normally distributed output, (i) guarantees to select a system in the indifference zone with high probability, (ii) runs efficiently on up to 1,024 parallel cores, and (iii) in an example uses smaller sample sizes compared to existing parallel procedures, particularly for large problems (over $10^6$ alternatives). In our computational study we discuss two methods for implementing GSP on parallel computers, namely the Message-Passing Interface (MPI) and Hadoop MapReduce and show that the latter provides good protection against core failures at the expense of a significant drop in utilization due to periodic unavoidable synchronization.
Depth Perception in Autostereograms: 1/f-Noise is Best
Venue: arXiv cs.CV 2015
Year: 2015

An autostereogram is a single image that encodes depth information that pops out when looking at it. The trick is achieved by replicating a vertical strip that sets a basic two-dimensional pattern with disparity shifts that encode a three-dimensional scene. It is of interest to explore the dependency between the ease of perceiving depth in autostereograms and the choice of the basic pattern used for generating them. In this work we confirm a theory proposed by Bruckstein et al. to explain the process of autostereographic depth perception, providing a measure for the ease of "locking into" the depth profile, based on the spectral properties of the basic pattern used. We report the results of three sets of psychophysical experiments using autostereograms generated from two-dimensional random noise patterns having power spectra of the form $1/f^β$. The experiments were designed to test the ability of human subjects to identify smooth, low resolution surfaces, as well as detail, in the form of higher resolution objects in the depth profile, and to determine limits in identifying small objects as a function of their size. In accordance with the theory, we discover a significant advantage of the $1/f$ noise pattern (pink noise) for fast depth lock-in and fine detail detection, showing that such patterns are optimal choices for autostereogram design. Validating the theoretical model predictions strengthens its underlying assumptions, and contributes to a better understanding of the visual system's binocular disparity mechanisms.
A review of landmark articles in the field of co-evolutionary computing
Venue: arXiv cs.NE 2015
Year: 2015

Coevolution is a powerful tool in evolutionary computing that mitigates some of its endemic problems, namely stagnation in local optima and lack of convergence in high dimensionality problems. Since its inception in 1990, there are multiple articles that have contributed greatly to the development and improvement of the coevolutionary techniques. In this report we review some of those landmark articles dwelving in the techniques they propose and how they fit to conform robust evolutionary algorithms
Interference-Nulling Time-Reversal Beamforming for mm-Wave Massive MIMO in Multi-User Frequency-Selective Indoor Channels
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave (mm-wave) and massive MIMO have been proposed for next generation wireless systems. However, there are many open problems for the implementation of those technologies. In particular, beamforming is necessary in mm-wave systems in order to counter high propagation losses. However, conventional beamsteering is not always appropriate in rich scattering multipath channels with frequency selective fading, such as those found in indoor environments. In this context, time-reversal (TR) is considered a promising beamforming technique for such mm-wave massive MIMO systems. In this paper, we analyze a baseband TR beamforming system for mm-wave multi-user massive MIMO. We verify that, as the number of antennas increases, TR yields good equalization and interference mitigation properties, but inter-user interference (IUI) remains a main impairment. Thus, we propose a novel technique called interference-nulling TR (INTR) to minimize IUI. We evaluate numerically the performance of INTR and compare it with conventional TR and equalized TR beamforming. We use a 60 GHz MIMO channel model with spatial correlation based on the IEEE 802.11ad SISO NLoS model. We demonstrate that INTR outperforms conventional TR with respect to average BER per user and achievable sum rate under diverse conditions, providing both diversity and multiplexing gains simultaneously.
SNA-based reasoning for multiagent team composition
Venue: arXiv cs.MA 2015
Year: 2015

The social network analysis (SNA), branch of complex systems can be used in the construction of multiagent systems. This paper proposes a study of how social network analysis can assist in modeling multiagent systems, while addressing similarities and differences between the two theories. We built a prototype of multi-agent systems for resolution of tasks through the formation of teams of agents that are formed on the basis of the social network established between agents. Agents make use of performance indicators to assess when should change their social network to maximize the participation in teams
Robust High Quality Image Guided Depth Upsampling
Venue: arXiv cs.CV 2015
Year: 2015

Time-of-Flight (ToF) depth sensing camera is able to obtain depth maps at a high frame rate. However, its low resolution and sensitivity to the noise are always a concern. A popular solution is upsampling the obtained noisy low resolution depth map with the guidance of the companion high resolution color image. However, due to the constrains in the existing upsampling models, the high resolution depth map obtained in such way may suffer from either texture copy artifacts or blur of depth discontinuity. In this paper, a novel optimization framework is proposed with the brand new data term and smoothness term. The comprehensive experiments using both synthetic data and real data show that the proposed method well tackles the problem of texture copy artifacts and blur of depth discontinuity. It also demonstrates sufficient robustness to the noise. Moreover, a data driven scheme is proposed to adaptively estimate the parameter in the upsampling optimization framework. The encouraging performance is maintained even in the case of large upsampling e.g. $8\times$ and $16\times$.
A Discriminative Representation of Convolutional Features for Indoor Scene Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Indoor scene recognition is a multi-faceted and challenging problem due to the diverse intra-class variations and the confusing inter-class similarities. This paper presents a novel approach which exploits rich mid-level convolutional features to categorize indoor scenes. Traditionally used convolutional features preserve the global spatial structure, which is a desirable property for general object recognition. However, we argue that this structuredness is not much helpful when we have large variations in scene layouts, e.g., in indoor scenes. We propose to transform the structured convolutional activations to another highly discriminative feature space. The representation in the transformed space not only incorporates the discriminative aspects of the target dataset, but it also encodes the features in terms of the general object categories that are present in indoor scenes. To this end, we introduce a new large-scale dataset of 1300 object categories which are commonly present in indoor scenes. Our proposed approach achieves a significant performance boost over previous state of the art approaches on five major scene classification datasets.
Defending Grey Attacks by Exploiting Wavelet Analysis in Collaborative Filtering Recommender Systems
Venue: arXiv cs.IR 2015
Year: 2015

"Shilling" attacks or "profile injection" attacks have always major challenges in collaborative filtering recommender systems (CFRSs). Many efforts have been devoted to improve collaborative filtering techniques which can eliminate the "shilling" attacks. However, most of them focused on detecting push attack or nuke attack which is rated with the highest score or lowest score on the target items. Few pay attention to grey attack when a target item is rated with a lower or higher score than the average score, which shows a more hidden rating behavior than push or nuke attack. In this paper, we present a novel detection method to make recommender systems resistant to such attacks. To characterize grey ratings, we exploit rating deviation of item to discriminate between grey attack profiles and genuine profiles. In addition, we also employ novelty and popularity of item to construct rating series. Since it is difficult to discriminate between the rating series of attacker and genuine users, we incorporate into discrete wavelet transform (DWT) to amplify these differences based on the rating series of rating deviation, novelty and popularity, respectively. Finally, we respectively extract features from rating series of rating deviation-based, novelty-based and popularity-based by using amplitude domain analysis method and combine all clustered results as our detection results. We conduct a list of experiments on both the Book-Crossing and HetRec-2011 datasets in diverse attack models. Experimental results were included to validate the effectiveness of our approach in comparison with the benchmarked methods.
Software development practices in academia: a case study comparison
Venue: arXiv cs.SE 2015
Year: 2015

Academic software development practices often differ from those of commercial development settings, yet only limited research has been conducted on assessing software development practises in academia. Here we present a case study of software development practices in four open-source scientific codes over a period of nine years, characterizing the evolution of their respective development teams, their scientific productivity, and the adoption (or discontinuation) of specific software engineering practises as the team size changes. We show that the transient nature of the development team results in the adoption of different development strategies. We relate measures of publication output to accumulated numbers of developers and find that for the projects considered the time-scale for returns on expended development effort is approximately three years. We discuss the implications of our findings for evaluating the performance of research software development, and in general any computationally oriented scientific project.
MRF-ZOOM: A Fast Dictionary Searching Algorithm for Magnetic Resonance Fingerprinting
Venue: arXiv cs.DS 2015
Year: 2015

Magnetic resonance fingerprinting (MRF) is a new technique for simultaneously quantifying multiple MR parameters using one temporally resolved MR scan. But its brute-force dictionary generating and searching (DGS) process causes a huge disk space demand and computational burden, prohibiting it from a practical multiple slice high-definition imaging. The purpose of this paper was to provide a fast and space efficient DGS algorithm for MRF. Based on an empirical analysis of properties of the distance function of the acquired MRF signal and the pre-defined MRF dictionary entries, we proposed a parameter separable MRF DGS method, which breaks the multiplicative computation complexity into an additive one and enabling a resolution scalable multi-resolution DGS process, which was dubbed as MRF ZOOM. The evaluation results showed that MRF ZOOM was hundreds or thousands of times faster than the original brute-force DGS method. The acceleration was even higher when considering the time difference for generating the dictionary. Using a high precision quantification, MRF can find the right parameter values for a 64x64 imaging slice in 117 secs. Our data also showed that spatial constraints can be used to further speed up MRF ZOOM.
Hybrid Algorithm for Multi-Objective Optimization by Greedy Hypervolume Maximization
Venue: arXiv cs.NE 2015
Year: 2015

This paper introduces a high-performance hybrid algorithm, called Hybrid Hypervolume Maximization Algorithm (H2MA), for multi-objective optimization that alternates between exploring the decision space and exploiting the already obtained non-dominated solutions. The proposal is centered on maximizing the hypervolume indicator, thus converting the multi-objective problem into a single-objective one. The exploitation employs gradient-based methods, but considering a single candidate efficient solution at a time, to overcome limitations associated with population-based approaches and also to allow an easy control of the number of solutions provided. There is an interchange between two steps. The first step is a deterministic local exploration, endowed with an automatic procedure to detect stagnation. When stagnation is detected, the search is switched to a second step characterized by a stochastic global exploration using an evolutionary algorithm. Using five ZDT benchmarks with 30 variables, the performance of the new algorithm is compared to state-of-the-art algorithms for multi-objective optimization, more specifically NSGA-II, SPEA2, and SMS-EMOA. The solutions found by the H2MA guide to higher hypervolume and smaller distance to the true Pareto frontier with significantly less function evaluations, even when the gradient is estimated numerically. Furthermore, although only continuous decision spaces have been considered here, discrete decision spaces could also have been treated, replacing gradient-based search by hill-climbing. Finally, a thorough explanation is provided to support the expressive gain in performance that was achieved.
Mobile Cloud Forensics: An Analysis of Seven Popular Android Apps
Venue: arXiv cs.CY 2015
Year: 2015

Using the evidence collection and analysis methodology for Android devices proposed by Martini, Do and Choo, we examined and analyzed seven popular Android cloud-based apps. Firstly, we analyzed each app in order to see what information could be obtained from their private app storage and SD card directories. We collated the information and used it to aid our investigation of each app database files and AccountManager data. To complete our understanding of the forensic artefacts stored by apps we analyzed, we performed further analysis on the apps to determine if the user authentication credentials could be collected for each app based on the information gained in the initial analysis stages. The contributions of this research include a detailed description of artefacts, which are of general forensic interest, for each app analyzed.
An intrinsic Cramér-Rao bound on Lie groups
Venue: arXiv cs.SY 2015
Year: 2015

In his 2005 paper, S.T. Smith proposed an intrinsic Cramér-Rao bound on the variance of estimators of a parameter defined on a Riemannian manifold. In the present technical note, we consider the special case where the parameter lives in a Lie group. In this case, by choosing, e.g., the right invariant metric, parallel transport becomes very simple, which allows a more straightforward and natural derivation of the bound in terms of Lie bracket, albeit for a slightly different definition of the estimation error. For bi-invariant metrics, the Lie group exponential map we use to define the estimation error, and the Riemannian exponential map used by S.T. Smith coincide, and we prove in this case that both results are identical indeed.
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices
Venue: arXiv cs.DS 2015
Year: 2015

A simultaneous embedding (with fixed edges) of two graphs $G^1$ and $G^2$ with common graph $G=G^1 \cap G^2$ is a pair of planar drawings of $G^1$ and $G^2$ that coincide on $G$. It is an open question whether there is a polynomial-time algorithm that decides whether two graphs admit a simultaneous embedding (problem SEFE). In this paper, we present two results. First, a set of three linear-time preprocessing algorithms that remove certain substructures from a given SEFE instance, producing a set of equivalent SEFE instances without such substructures. The structures we can remove are (1) cutvertices of the union graph $G^\cup = G^1 \cup G^2$, (2) most separating pairs of $G^\cup$, and (3) connected components of $G$ that are biconnected but not a cycle. Second, we give an $O(n^3)$-time algorithm solving SEFE for instances with the following restriction. Let $u$ be a pole of a P-node $μ$ in the SPQR-tree of a block of $G^1$ or $G^2$. Then at most three virtual edges of $μ$ may contain common edges incident to $u$. All algorithms extend to the sunflower case, i.e., to the case of more than three graphs pairwise intersecting in the same common graph.
A Neural Conversational Model
Venue: arXiv cs.CL 2015
Year: 2015

Conversational modeling is an important task in natural language understanding and machine intelligence. Although previous approaches exist, they are often restricted to specific domains (e.g., booking an airline ticket) and require hand-crafted rules. In this paper, we present a simple approach for this task which uses the recently proposed sequence to sequence framework. Our model converses by predicting the next sentence given the previous sentence or sentences in a conversation. The strength of our model is that it can be trained end-to-end and thus requires much fewer hand-crafted rules. We find that this straightforward model can generate simple conversations given a large conversational training dataset. Our preliminary results suggest that, despite optimizing the wrong objective function, the model is able to converse well. It is able extract knowledge from both a domain specific dataset, and from a large, noisy, and general domain dataset of movie subtitles. On a domain-specific IT helpdesk dataset, the model can find a solution to a technical problem via conversations. On a noisy open-domain movie transcript dataset, the model can perform simple forms of common sense reasoning. As expected, we also find that the lack of consistency is a common failure mode of our model.
Cognitive Wireless Powered Network: Spectrum Sharing Models and Throughput Maximization
Venue: arXiv cs.IT 2015
Year: 2015

The recent advance in radio-frequency (RF) wireless energy transfer (WET) has motivated the study of wireless powered communication network (WPCN), in which distributed wireless devices are powered via dedicated WET by the hybrid access-point (H-AP) in the downlink (DL) for uplink (UL) wireless information transmission (WIT). In this paper, by exploiting the cognitive radio (CR) technique, we study a new type of CR enabled secondary WPCN, called cognitive WPCN, under spectrum sharing with the primary wireless communication system. In particular, we consider a cognitive WPCN, consisting of one single H-AP with constant power supply and distributed users, shares the same spectrum for its DL WET and UL WIT with an existing primary communication link, where the WPCN's WET/WIT and the primary link's WIT may interfere with each other. Under this new setup, we propose two coexisting models for spectrum sharing of the two systems, namely underlay and overlay based cognitive WPCNs, depending on different types of knowledge on the primary user transmission available at the cognitive WPCN. For each model, we maximize the sum-throughput of the cognitive WPCN by optimizing its transmission under different constraints applied to protect the primary user transmission. Analysis and simulation results are provided to compare the sum-throughput of the cognitive WPCN versus the achievable rate of the primary user in two coexisting models. It is shown that the overlay based cognitive WPCN outperforms the underlay based counterpart, thanks to its fully cooperative WET/WIT design with the primary WIT, while it also requires higher complexity for implementation.