OpenRaiser/Intern-Atlas huggingface dataset:
Studying Collective Human Decision Making and Creativity with Evolutionary Computation
Venue: arXiv cs.NE 2014
Year: 2014

We report a summary of our interdisciplinary research project "Evolutionary Perspective on Collective Decision Making" that was conducted through close collaboration between computational, organizational and social scientists at Binghamton University. We redefined collective human decision making and creativity as evolution of ecologies of ideas, where populations of ideas evolve via continual applications of evolutionary operators such as reproduction, recombination, mutation, selection, and migration of ideas, each conducted by participating humans. Based on this evolutionary perspective, we generated hypotheses about collective human decision making using agent-based computer simulations. The hypotheses were then tested through several experiments with real human subjects. Throughout this project, we utilized evolutionary computation (EC) in non-traditional ways---(1) as a theoretical framework for reinterpreting the dynamics of idea generation and selection, (2) as a computational simulation model of collective human decision making processes, and (3) as a research tool for collecting high-resolution experimental data of actual collaborative design and decision making from human subjects. We believe our work demonstrates untapped potential of EC for interdisciplinary research involving human and social dynamics.
Further heuristics for $k$-means: The merge-and-split heuristic and the $(k,l)$-means
Venue: arXiv cs.LG 2014
Year: 2014

Finding the optimal $k$-means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the $k$-means objective. We first show how to extend Lloyd's batched relocation heuristic and Hartigan's single-point relocation heuristic to take into account empty-cluster and single-point cluster events, respectively. Those events tend to increasingly occur when $k$ or $d$ increases, or when performing several restarts. First, we show that those special events are a blessing because they allow to partially re-seed some cluster centers while further minimizing the $k$-means objective function. Second, we describe a novel heuristic, merge-and-split $k$-means, that consists in merging two clusters and splitting this merged cluster again with two new centers provided it improves the $k$-means objective. This novel heuristic can improve Hartigan's $k$-means when it has converged to a local minimum. We show empirically that this merge-and-split $k$-means improves over the Hartigan's heuristic which is the {\em de facto} method of choice. Finally, we propose the $(k,l)$-means objective that generalizes the $k$-means objective by associating the data points to their $l$ closest cluster centers, and show how to either directly convert or iteratively relax the $(k,l)$-means into a $k$-means in order to reach better local minima.
Big Models: From Beijing to the whole China
Venue: arXiv cs.OH 2014
Year: 2014

This paper propose the concept of big model as a novel research paradigm for regional and urban studies. Big models are fine-scale regional/urban simulation models for a large geographical area, and they overcome the trade-off between simulated scale and spatial unit by tackling both of them at the same time enabled by emerging big/open data, increasing computation power and matured regional/urban modeling methods. The concept, characteristics, and potential applications of big models have been elaborated. We addresse several case studies to illustrate the progress of research and utilization on big models, including mapping urban areas for all Chinese cities, performing parcel-level urban simulation, and several ongoing research projects. Most of these applications can be adopted across the country, and all of them are focusing on a fine-scale level, such as a parcel, a block, or a township (sub-district), which is not the same with the existing studies using conventional models that are only suitable for a certain single or two cities or regions, or for a larger area but have to significantly sacrifice the data resolution. It is expected that big models will mark a promising new era for the urban and regional study in the age of big data.
Information Centric Networking in the IoT: Experiments with NDN in the Wild
Venue: arXiv cs.NI 2014
Year: 2014

This paper explores the feasibility, advantages, and challenges of an ICN-based approach in the Internet of Things. We report on the first NDN experiments in a life-size IoT deployment, spread over tens of rooms on several floors of a building. Based on the insights gained with these experiments, the paper analyses the shortcomings of CCN applied to IoT. Several interoperable CCN enhancements are then proposed and evaluated. We significantly decreased control traffic (i.e., interest messages) and leverage data path and caching to match IoT requirements in terms of energy and bandwidth constraints. Our optimizations increase content availability in case of IoT nodes with intermittent activity. This paper also provides the first experimental comparison of CCN with the common IoT standards 6LoWPAN/RPL/UDP.
Tupleware: Redefining Modern Analytics
Venue: arXiv cs.DB 2014
Year: 2014

There is a fundamental discrepancy between the targeted and actual users of current analytics frameworks. Most systems are designed for the data and infrastructure of the Googles and Facebooks of the world---petabytes of data distributed across large cloud deployments consisting of thousands of cheap commodity machines. Yet, the vast majority of users operate clusters ranging from a few to a few dozen nodes, analyze relatively small datasets of up to a few terabytes, and perform primarily compute-intensive operations. Targeting these users fundamentally changes the way we should build analytics systems. This paper describes the design of Tupleware, a new system specifically aimed at the challenges faced by the typical user. Tupleware's architecture brings together ideas from the database, compiler, and programming languages communities to create a powerful end-to-end solution for data analysis. We propose novel techniques that consider the data, computations, and hardware together to achieve maximum performance on a case-by-case basis. Our experimental evaluation quantifies the impact of our novel techniques and shows orders of magnitude performance improvement over alternative systems.
Parametric LTL on Markov Chains
Venue: arXiv cs.LO 2014
Year: 2014

This paper is concerned with the verification of finite Markov chains against parametrized LTL (pLTL) formulas. In pLTL, the until-modality is equipped with a bound that contains variables; e.g., $\Diamond_{\le x}\ φ$ asserts that $φ$ holds within $x$ time steps, where $x$ is a variable on natural numbers. The central problem studied in this paper is to determine the set of parameter valuations $V_{\prec p} (φ)$ for which the probability to satisfy pLTL-formula $φ$ in a Markov chain meets a given threshold $\prec p$, where $\prec$ is a comparison on reals and $p$ a probability. As for pLTL determining the emptiness of $V_{> 0}(φ)$ is undecidable, we consider several logic fragments. We consider parametric reachability properties, a sub-logic of pLTL restricted to next and $\Diamond_{\le x}$, parametric Büchi properties and finally, a maximal subclass of pLTL for which emptiness of $V_{> 0}(φ)$ is decidable.
A factorization criterion for acyclic directed mixed graphs
Venue: arXiv cs.AI 2014
Year: 2014

Acyclic directed mixed graphs, also known as semi-Markov models represent the conditional independence structure induced on an observed margin by a DAG model with latent variables. In this paper we present a factorization criterion for these models that is equivalent to the global Markov property given by (the natural extension of) d-separation.
The architecture of innovation: Tracking face-to-face interactions with ubicomp technologies
Venue: arXiv cs.CY 2014
Year: 2014

The layouts of the buildings we live in shape our everyday lives. In office environments, building spaces affect employees' communication, which is crucial for productivity and innovation. However, accurate measurement of how spatial layouts affect interactions is a major challenge and traditional techniques may not give an objective view.We measure the impact of building spaces on social interactions using wearable sensing devices. We study a single organization that moved between two different buildings, affording a unique opportunity to examine how space alone can affect interactions. The analysis is based on two large scale deployments of wireless sensing technologies: short-range, lightweight RFID tags capable of detecting face-to-face interactions. We analyze the traces to study the impact of the building change on social behavior, which represents a first example of using ubiquitous sensing technology to study how the physical design of two workplaces combines with organizational structure to shape contact patterns.
Low-Complexity Variable Forgetting Factor Constrained Constant Modulus RLS Algorithm for Adaptive Beamforming
Venue: arXiv cs.OH 2014
Year: 2014

In this paper, a recursive least squares (RLS) based blind adaptive beamforming algorithm that features a new variable forgetting factor (VFF) mechanism is presented. The beamformer is designed according to the constrained constant modulus (CCM) criterion, and the proposed adaptive algorithm operates in the generalized sidelobe canceler (GSC) structure. A detailed study of its operating properties is carried out, including a convexity analysis and a mean squared error (MSE) analysis of its steady-state behavior. The results of numerical experiments demonstrate that the proposed VFF mechanism achieves a superior learning and tracking performance compared to other VFF mechanisms.
Low-Latency Successive-Cancellation List Decoders for Polar Codes with Multi-bit Decision
Venue: arXiv cs.IT 2014
Year: 2014

Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check (LDPC) or turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long latency bottleneck. In this paper, we propose a multi-bit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 bits together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from (3n-2) to (2n-2) clock cycles without any performance loss. Then, we extend the idea of 2-bit-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2K bits simultaneously. This general approach, referred as 2K-bit reformulated SCL (2Kb-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2K-2-2 cycles. Furthermore, based on the proposed algorithms, VLSI architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 times and 2.77 times increase in coded throughput with list size 2, and 2.11 times and 3.23 times increase in coded throughput with list size 4, respectively.
3D planar patch extraction from stereo using probabilistic region growing
Venue: arXiv cs.CV 2014
Year: 2014

This article presents a novel 3D planar patch extraction method using a probabilistic region growing algorithm. Our method works by simultaneously initiating multiple planar patches from seed points, the latter determined by an intensity-based 2D segmentation algorithm in the stereo-pair images. The patches are grown incrementally and in parallel as 3D scene points are considered for membership, using a probabilistic distance likelihood measure. In addition, we have incorporated prior information based on the noise model in the 2D images and the scene configuration but also include the intensity information resulting from the initial segmentation. This method works well across many different data-sets, involving real and synthetic examples of both regularly and non-regularly sampled data, and is fast enough that may be used for robot navigation tasks of path detection and obstacle avoidance.
On a new formulation of nonlocal image filters involving the relative rearrangement
Venue: arXiv cs.CV 2014
Year: 2014

Nonlocal filters are simple and powerful techniques for image denoising. In this paper we study the reformulation of a broad class of nonlocal filters in terms of two functional rearrangements: the decreasing and the relative rearrangements. Independently of the dimension of the image, we reformulate these filters as integral operators defined in a one-dimensional space corresponding to the level sets measures. We prove the equivalency between the original and the rearranged versions of the filters and propose a discretization in terms of constant-wise interpolators, which we prove to be convergent to the solution of the continuous setting. For some particular cases, this new formulation allows us to perform a detailed analysis of the filtering properties. Among others, we prove that the filtered image is a contrast change of the original image, and that the filtering procedure behaves asymptotically as a shock filter combined with a border diffusive term, responsible for the staircaising effect and the loss of contrast.
Asymptotic Stability and Decay Rates of Homogeneous Positive Systems With Bounded and Unbounded Delays
Venue: arXiv cs.SY 2014
Year: 2014

There are several results on the stability of nonlinear positive systems in the presence of time delays. However, most of them assume that the delays are constant. This paper considers time-varying, possibly unbounded, delays and establishes asymptotic stability and bounds the decay rate of a significant class of nonlinear positive systems which includes positive linear systems as a special case. Specifically, we present a necessary and sufficient condition for delay-independent stability of continuous-time positive systems whose vector fields are cooperative and homogeneous. We show that global asymptotic stability of such systems is independent of the magnitude and variation of the time delays. For various classes of time delays, we are able to derive explicit expressions that quantify the decay rates of positive systems. We also provide the corresponding counterparts for discrete-time positive systems whose vector fields are non-decreasing and homogeneous.
Near-Optimal Virtual Machine Packing Based on Resource Requirement of Service Demands Using Pattern Clustering
Venue: arXiv cs.DC 2014
Year: 2014

Upon the expansion of Cloud Computing and the positive outlook of organizations with regard to the movements towards using cloud computing and their expanding utilization of such valuable processing method, as well as the solutions provided by the cloud infrastructure providers with regard to the reduction of the costs of processing resources, the problem of organizing resources in a cloud environment gained a high importance. One of the major preoccupations of the minds of cloud infrastructure clients is their lack of knowledge on the quantity of their required processing resources in different periods of time. The managers and technicians are trying to make the most use of scalability and the flexibility of the resources in cloud computing. The main challenge is with calculating the amount of the required processing resources per moment with regard to the quantity of incoming requests of the service. Through deduction of the accurate amount of these items, one can have an accurate estimation of the requests per moment. This paper aims at introducing a model for automatic scaling of the cloud resources that would reduce the cost of renting the resources for the clients of cloud infrastructure. Thus, first we start with a thorough explanation of the proposal and the major components of the model. Then through calculating the incomings of the model through clustering and introducing the way that each of these components work in different phases,...
A framework for improving the performance of verification algorithms with a low false positive rate requirement and limited training data
Venue: arXiv cs.CV 2014
Year: 2014

In this paper we address the problem of matching patterns in the so-called verification setting in which a novel, query pattern is verified against a single training pattern: the decision sought is whether the two match (i.e. belong to the same class) or not. Unlike previous work which has universally focused on the development of more discriminative distance functions between patterns, here we consider the equally important and pervasive task of selecting a distance threshold which fits a particular operational requirement - specifically, the target false positive rate (FPR). First, we argue on theoretical grounds that a data-driven approach is inherently ill-conditioned when the desired FPR is low, because by the very nature of the challenge only a small portion of training data affects or is affected by the desired threshold. This leads us to propose a general, statistical model-based method instead. Our approach is based on the interpretation of an inter-pattern distance as implicitly defining a pattern embedding which approximately distributes patterns according to an isotropic multi-variate normal distribution in some space. This interpretation is then used to show that the distribution of training inter-pattern distances is the non-central chi2 distribution, differently parameterized for each class. Thus, to make the class-specific threshold choice we propose a novel analysis-by-synthesis iterative algorithm which estimates the three free parameters of the model (for each class) using task-specific constraints. The validity of the premises of our work and the effectiveness of the proposed method are demonstrated by applying the method to the task of set-based face verification on a large database of pseudo-random head motion videos.
Using Apriori with WEKA for Frequent Pattern Mining
Venue: arXiv cs.DB 2014
Year: 2014

Knowledge exploration from the large set of data,generated as a result of the various data processing activities due to data mining only. Frequent Pattern Mining is a very important undertaking in data mining. Apriori approach applied to generate frequent item set generally espouse candidate generation and pruning techniques for the satisfaction of the desired objective. This paper shows how the different approaches achieve the objective of frequent mining along with the complexities required to perform the job. This paper demonstrates the use of WEKA tool for association rule mining using Apriori algorithm.
Performance evaluation on the basis of Bit error rate for different order of Modulation and different length of Subchannels in ofdm system
Venue: arXiv cs.IT 2014
Year: 2014

Today, we have required to accommodate a large number of users under a single base station. This can be possible only if we have some flexibility over the spectrum. Previously we have lots of multiplexing methods to accommodate large number of signals in time and frequency domain. But now we have required to accommodate a large number of users in the same bandwidth, without any fading over the received signal. So, orthogonality can be maintained over the frequency response. This technology is now more popular in the mobile communication domain, called Orthogonal Frequency Division Multiplexing (OFDM). Actually user data can be converted into the parallel form and then they are modulated using digital modulation techniques. Finally, they have followed by OFDM Modulator and cyclic prefix can be inserted into the OFDM symbols. Here, I have worked on the measurement of Bit error rate for different modulation techniques in OFDM technology. It has been considered that subchannel size is not constant. According to that I have concluded the overall idea regarding the performance under OFDM technology.
Jabalin: a Comprehensive Computational Model of Modern Standard Arabic Verbal Morphology Based on Traditional Arabic Prosody
Venue: arXiv cs.CL 2014
Year: 2014

The computational handling of Modern Standard Arabic is a challenge in the field of natural language processing due to its highly rich morphology. However, several authors have pointed out that the Arabic morphological system is in fact extremely regular. The existing Arabic morphological analyzers have exploited this regularity to variable extent, yet we believe there is still some scope for improvement. Taking inspiration in traditional Arabic prosody, we have designed and implemented a compact and simple morphological system which in our opinion takes further advantage of the regularities encountered in the Arabic morphological system. The output of the system is a large-scale lexicon of inflected forms that has subsequently been used to create an Online Interface for a morphological analyzer of Arabic verbs. The Jabalin Online Interface is available at http://elvira.lllf.uam.es/jabalin/, hosted at the LLI-UAM lab. The generation system is also available under a GNU GPL 3 license.
Fusion Based Holistic Road Scene Understanding
Venue: arXiv cs.CV 2014
Year: 2014

This paper addresses the problem of holistic road scene understanding based on the integration of visual and range data. To achieve the grand goal, we propose an approach that jointly tackles object-level image segmentation and semantic region labeling within a conditional random field (CRF) framework. Specifically, we first generate semantic object hypotheses by clustering 3D points, learning their prior appearance models, and using a deep learning method for reasoning their semantic categories. The learned priors, together with spatial and geometric contexts, are incorporated in CRF. With this formulation, visual and range data are fused thoroughly, and moreover, the coupled segmentation and semantic labeling problem can be inferred via Graph Cuts. Our approach is validated on the challenging KITTI dataset that contains diverse complicated road scenarios. Both quantitative and qualitative evaluations demonstrate its effectiveness.
Crowdsourcing for Participatory Democracies: Efficient Elicitation of Social Choice Functions
Venue: arXiv cs.MA 2014
Year: 2014

We present theoretical and empirical results demonstrating the usefulness of voting rules for participatory democracies. We first give algorithms which efficiently elicit ε-approximations to two prominent voting rules: the Borda rule and the Condorcet winner. This result circumvents previous prohibitive lower bounds and is surprisingly strong: even if the number of ideas is as large as the number of participants, each participant will only have to make a logarithmic number of comparisons, an exponential improvement over the linear number of comparisons previously needed. We demonstrate the approach in an experiment in Finland's recent off-road traffic law reform, observing that the total number of comparisons needed to achieve a fixed εapproximation is linear in the number of ideas and that the constant is not large. Finally, we note a few other experimental observations which support the use of voting rules for aggregation. First, we observe that rating, one of the common alternatives to ranking, manifested effects of bias in our data. Second, we show that very few of the topics lacked a Condorcet winner, one of the prominent negative results in voting. Finally, we show data hinting at a potential future direction: the use of partial rankings as opposed to pairwise comparisons to further decrease the elicitation time.