OpenRaiser/Intern-Atlas huggingface dataset:
The maximum number of faces of the Minkowski sum of three convex polytopes
Venue: arXiv cs.CG 2012
Year: 2012

We derive tight expressions for the maximum number of $k$-faces, $0\le k\le d-1$, of the Minkowski sum, $P_1+P_2+P_3$, of three $d$-dimensional convex polytopes $P_1$, $P_2$ and $P_3$, as a function of the number of vertices of the polytopes, for any $d\ge 2$. Expressing the Minkowski sum of the three polytopes as a section of their Cayley polytope $\mathcal{C}$, the problem of counting the number of $k$-faces of $P_1+P_2+P_3$, reduces to counting the number of $(k+2)$-faces of the subset of $\mathcal{C}$ comprising of the faces that contain at least one vertex from each $P_i$. In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of $r$ $d$-polytopes, where $r\ge d$. For $d\ge 4$, the maximum values are attained when $P_1$, $P_2$ and $P_3$ are $d$-polytopes, whose vertex sets are chosen appropriately from three distinct $d$-dimensional moment-like curves.
The Interplay Between Stability and Regret in Online Learning
Venue: arXiv cs.LG 2012
Year: 2012

This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given stability, bounded forward regret is equivalent to bounded regret. We also show that the existence of an algorithm with bounded regret implies the existence of a stable algorithm with bounded regret and bounded forward regret. The equivalence results apply to general, possibly non-convex problems. To the best of our knowledge, our analysis provides the first general connection between stability and regret in the online setting that is not restricted to a particular class of algorithms. Our stability-regret connection provides a simple recipe for analyzing regret incurred by any online learning algorithm. Using our framework, we analyze several existing online learning algorithms as well as the "approximate" versions of algorithms like RDA that solve an optimization problem at each iteration. Our proofs are simpler than existing analysis for the respective algorithms, show a clear trade-off between stability and forward regret, and provide tighter regret bounds in some cases. Furthermore, using our recipe, we analyze "approximate" versions of several algorithms such as follow-the-regularized-leader (FTRL) that requires solving an optimization problem at each step.
Automatic Function Annotations for Hoare Logic
Venue: arXiv cs.LO 2012
Year: 2012

In systems verification we are often concerned with multiple, inter-dependent properties that a program must satisfy. To prove that a program satisfies a given property, the correctness of intermediate states of the program must be characterized. However, this intermediate reasoning is not always phrased such that it can be easily re-used in the proofs of subsequent properties. We introduce a function annotation logic that extends Hoare logic in two important ways: (1) when proving that a function satisfies a Hoare triple, intermediate reasoning is automatically stored as function annotations, and (2) these function annotations can be exploited in future Hoare logic proofs. This reduces duplication of reasoning between the proofs of different properties, whilst serving as a drop-in replacement for traditional Hoare logic to avoid the costly process of proof refactoring. We explain how this was implemented in Isabelle/HOL and applied to an experimental branch of the seL4 microkernel to significantly reduce the size and complexity of existing proofs.
Chiefly Symmetric: Results on the Scalability of Probabilistic Model Checking for Operating-System Code
Venue: arXiv cs.LO 2012
Year: 2012

Reliability in terms of functional properties from the safety-liveness spectrum is an indispensable requirement of low-level operating-system (OS) code. However, with evermore complex and thus less predictable hardware, quantitative and probabilistic guarantees become more and more important. Probabilistic model checking is one technique to automatically obtain these guarantees. First experiences with the automated quantitative analysis of low-level operating-system code confirm the expectation that the naive probabilistic model checking approach rapidly reaches its limits when increasing the numbers of processes. This paper reports on our work-in-progress to tackle the state explosion problem for low-level OS-code caused by the exponential blow-up of the model size when the number of processes grows. We studied the symmetry reduction approach and carried out our experiments with a simple test-and-test-and-set lock case study as a representative example for a wide range of protocols with natural inter-process dependencies and long-run properties. We quickly see a state-space explosion for scenarios where inter-process dependencies are insignificant. However, once inter-process dependencies dominate the picture models with hundred and more processes can be constructed and analysed.
Metamodel Instance Generation: A systematic literature review
Venue: arXiv cs.SE 2012
Year: 2012

Modelling and thus metamodelling have become increasingly important in Software Engineering through the use of Model Driven Engineering. In this paper we present a systematic literature review of instance generation techniques for metamodels, i.e. the process of automatically generating models from a given metamodel. We start by presenting a set of research questions that our review is intended to answer. We then identify the main topics that are related to metamodel instance generation techniques, and use these to initiate our literature search. This search resulted in the identification of 34 key papers in the area, and each of these is reviewed here and discussed in detail. The outcome is that we are able to identify a knowledge gap in this field, and we offer suggestions as to some potential directions for future research.
Generalized Distributed Compressive Sensing
Venue: arXiv cs.IT 2012
Year: 2012

Distributed Compressive Sensing (DCS) improves the signal recovery performance of multi signal ensembles by exploiting both intra- and inter-signal correlation and sparsity structure. However, the existing DCS was proposed for a very limited ensemble of signals that has single common information \cite{Baron:2009vd}. In this paper, we propose a generalized DCS (GDCS) which can improve sparse signal detection performance given arbitrary types of common information which are classified into not just full common information but also a variety of partial common information. The theoretical bound on the required number of measurements using the GDCS is obtained. Unfortunately, the GDCS may require much a priori-knowledge on various inter common information of ensemble of signals to enhance the performance over the existing DCS. To deal with this problem, we propose a novel algorithm that can search for the correlation structure among the signals, with which the proposed GDCS improves detection performance even without a priori-knowledge on correlation structure for the case of arbitrarily correlated multi signal ensembles.
Estimation of Bandlimited Signals in Additive Gaussian Noise: a "Precision Indifference" Principle
Venue: arXiv cs.IT 2012
Year: 2012

The sampling, quantization, and estimation of a bounded dynamic-range bandlimited signal affected by additive independent Gaussian noise is studied in this work. For bandlimited signals, the distortion due to additive independent Gaussian noise can be reduced by oversampling (statistical diversity). The pointwise expected mean-squared error is used as a distortion metric for signal estimate in this work. Two extreme scenarios of quantizer precision are considered: (i) infinite precision (real scalars); and (ii) one-bit quantization (sign information). If $N$ is the oversampling ratio with respect to the Nyquist rate, then the optimal law for distortion is $O(1/N)$. We show that a distortion of $O(1/N)$ can be achieved irrespective of the quantizer precision by considering the above-mentioned two extreme scenarios of quantization. Thus, a quantization precision indifference principle is discovered, where the reconstruction distortion law, up to a proportionality constant, is unaffected by quantizer's accuracy.
Some results on the Weiss-Weinstein bound for conditional and unconditional signal models in array processing
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, the Weiss-Weinstein bound is analyzed in the context of sources localization with a planar array of sensors. Both conditional and unconditional source signal models are studied. First, some results are given in the multiple sources context without specifying the structure of the steering matrix and of the noise covariance matrix. Moreover, the case of an uniform or Gaussian prior are analyzed. Second, these results are applied to the particular case of a single source for two kinds of array geometries: a non-uniform linear array (elevation only) and an arbitrary planar (azimuth and elevation) array.
Nonlinear Dynamic Field Embedding: On Hyperspectral Scene Visualization
Venue: arXiv cs.CV 2012
Year: 2012

Graph embedding techniques are useful to characterize spectral signature relations for hyperspectral images. However, such images consists of disjoint classes due to spatial details that are often ignored by existing graph computing tools. Robust parameter estimation is a challenge for kernel functions that compute such graphs. Finding a corresponding high quality coordinate system to map signature relations remains an open research question. We answer positively on these challenges by first proposing a kernel function of spatial and spectral information in computing neighborhood graphs. Secondly, the study exploits the force field interpretation from mechanics and devise a unifying nonlinear graph embedding framework. The generalized framework leads to novel unsupervised multidimensional artificial field embedding techniques that rely on the simple additive assumption of pair-dependent attraction and repulsion functions. The formulations capture long range and short range distance related effects often associated with living organisms and help to establish algorithmic properties that mimic mutual behavior for the purpose of dimensionality reduction. The main benefits from the proposed models includes the ability to preserve the local topology of data and produce quality visualizations i.e. maintaining disjoint meaningful neighborhoods. As part of evaluation, visualization, gradient field trajectories, and semisupervised classification experiments are conducted for image scenes acquired by multiple sensors at various spatial resolutions over different types of objects. The results demonstrate the superiority of the proposed embedding framework over various widely used methods.
The Power of Choice for Random Satisfiability
Venue: arXiv cs.CC 2012
Year: 2012

We consider Achlioptas processes for k-SAT formulas. We create a semi-random formula with n variables and m clauses, where each clause is a choice, made on-line, between two or more uniformly random clauses. Our goal is to delay the satisfiability/unsatisfiability transition, keeping the formula satisfiable up to densities m/n beyond the satisfiability threshold alpha_k for random k-SAT. We show that three choices suffice to raise the threshold for any k >= 3, and that two choices suffice for all 3 <= k <= 25. We also show that two choices suffice to lower the threshold for all k >= 3, making the formula unsatisfiable at a density below alpha_k.
WiGig and IEEE 802.11ad - For multi-gigabyte-per-second WPAN and WLAN
Venue: arXiv cs.NI 2012
Year: 2012

The Wireless Gigabit Alliance (WiGig) and IEEE 802.11ad are developing a multigigabit wireless personal and local area network (WPAN/WLAN) specification in the 60 GHz millimeter wave band. Chipset manufacturers, original equipment manufacturers (OEMs), and telecom companies are also assisting in this development. 60 GHz millimeter wave transmission will scale the speed of WLANs and WPANs to 6.75 Gbit/s over distances less than 10 meters. This technology is the first of its kind and will eliminate the need for cable around personal computers, docking stations, and other consumer electronic devices. High-definition multimedia interface (HDMI), display port, USB 3.0, and peripheral component interconnect express (PCIe) 3.0 cables will all be eliminated. Fast downloads and uploads, wireless sync, and multi-gigabit-per-second WLANs will be possible over shorter distances. 60 GHz millimeter wave supports fast session transfer (FST) protocol, which makes it backward compatible with 5 GHz or 2.4 GHz WLAN so that end users experience the same range as in today's WLANs. IEEE 802.11ad specifies the physical (PHY) sublayer and medium access control (MAC) sublayer of the protocol stack. The MAC protocol is based on time-division multiple access (TDMA), and the PHY layer uses single carrier (SC) and orthogonal frequency division multiplexing (OFDM) to simultaneously enable low-power, high-performance applications.
Emergence of Self-Organized Amoeboid Movement in a Multi-Agent Approximation of Physarum polycephalum
Venue: arXiv cs.MA 2012
Year: 2012

The giant single-celled slime mould Physarum polycephalum exhibits complex morphological adaptation and amoeboid movement as it forages for food and may be seen as a minimal example of complex robotic behaviour. Swarm computation has previously been used to explore how spatiotemporal complexity can emerge from, and be distributed within, simple component parts and their interactions. Using a particle based swarm approach we explore the question of how to generate collective amoeboid movement from simple non-oscillatory component parts in a model of P. polycephalum. The model collective behaves as a cohesive and deformable virtual material, approximating the local coupling within the plasmodium matrix. The collective generates de-novo and complex oscillatory patterns from simple local interactions. The origin of this motor behaviour is distributed within the collective rendering is morphologically adaptive, amenable to external influence, and robust to simulated environmental insult. We show how to gain external influence over the collective movement by simulated chemo-attraction (pulling towards nutrient stimuli) and simulated light irradiation hazards (pushing from stimuli). The amorphous and distributed properties of the collective are demonstrated by cleaving it into two independent entities and fusing two separate entities to form a single device, thus enabling it to traverse narrow, separate or tortuous paths. We conclude by summarising the contribution of the model to swarm based robotics and soft-bodied modular robotics and discuss the future potential of such material approaches to the field.
Viewpoint Invariant Object Detector
Venue: arXiv cs.CV 2012
Year: 2012

Object Detection is the task of identifying the existence of an object class instance and locating it within an image. Difficulties in handling high intra-class variations constitute major obstacles to achieving high performance on standard benchmark datasets (scale, viewpoint, lighting conditions and orientation variations provide good examples). Suggested model aims at providing more robustness to detecting objects suffering severe distortion due to < 60° viewpoint changes. In addition, several model computational bottlenecks have been resolved leading to a significant increase in the model performance (speed and space) without compromising the resulting accuracy. Finally, we produced two illustrative applications showing the potential of the object detection technology being deployed in real life applications; namely content-based image search and content-based video search.
Artificial Neural Network Fuzzy Inference System (ANFIS) For Brain Tumor Detection
Venue: arXiv cs.CV 2012
Year: 2012

Detection and segmentation of Brain tumor is very important because it provides anatomical information of normal and abnormal tissues which helps in treatment planning and patient follow-up. There are number of techniques for image segmentation. Proposed research work uses ANFIS (Artificial Neural Network Fuzzy Inference System) for image classification and then compares the results with FCM (Fuzzy C means) and K-NN (K-nearest neighbor). ANFIS includes benefits of both ANN and the fuzzy logic systems. A comprehensive feature set and fuzzy rules are selected to classify an abnormal image to the corresponding tumor type. Experimental results illustrate promising results in terms of classification accuracy. A comparative analysis is performed with the FCM and K-NN to show the superior nature of ANFIS systems.
Challenges in Kurdish Text Processing
Venue: arXiv cs.IR 2012
Year: 2012

Despite having a large number of speakers, the Kurdish language is among the less-resourced languages. In this work we highlight the challenges and problems in providing the required tools and techniques for processing texts written in Kurdish. From a high-level perspective, the main challenges are: the inherent diversity of the language, standardization and segmentation issues, and the lack of language resources.
Cumulative Step-size Adaptation on Linear Functions
Venue: arXiv cs.LG 2012
Year: 2012

The CSA-ES is an Evolution Strategy with Cumulative Step size Adaptation, where the step size is adapted measuring the length of a so-called cumulative path. The cumulative path is a combination of the previous steps realized by the algorithm, where the importance of each step decreases with time. This article studies the CSA-ES on composites of strictly increasing functions with affine linear functions through the investigation of its underlying Markov chains. Rigorous results on the change and the variation of the step size are derived with and without cumulation. The step-size diverges geometrically fast in most cases. Furthermore, the influence of the cumulation parameter is studied.
Follow Whom? Chinese Users Have Different Choice
Venue: arXiv cs.SI 2012
Year: 2012

Sina Weibo, which was launched in 2009, is the most popular Chinese micro-blogging service. It has been reported that Sina Weibo has more than 400 million registered users by the end of the third quarter in 2012. Sina Weibo and Twitter have a lot in common, however, in terms of the following preference, Sina Weibo users, most of whom are Chinese, behave differently compared with those of Twitter. This work is based on a data set of Sina Weibo which contains 80.8 million users' profiles and 7.2 billion relations and a large data set of Twitter. Firstly some basic features of Sina Weibo and Twitter are analyzed such as degree and activeness distribution, correlation between degree and activeness, and the degree of separation. Then the following preference is investigated by studying the assortative mixing, friend similarities, following distribution, edge balance ratio, and ranking correlation, where edge balance ratio is newly proposed to measure balance property of graphs. It is found that Sina Weibo has a lower reciprocity rate, more positive balanced relations and is more disassortative. Coinciding with Asian traditional culture, the following preference of Sina Weibo users is more concentrated and hierarchical: they are more likely to follow people at higher or the same social levels and less likely to follow people lower than themselves. In contrast, the same kind of following preference is weaker in Twitter. Twitter users are open as they follow people from levels, which accords with its global characteristic and the prevalence of western civilization. The message forwarding behavior is studied by displaying the propagation levels, delays, and critical users. The following preference derives from not only the usage habits but also underlying reasons such as personalities and social moralities that is worthy of future research.
Resolution and Datalog Rewriting Under Value Invention and Equality Constraints
Venue: arXiv cs.DB 2012
Year: 2012

This paper present several refinements of the Datalog +/- framework based on resolution and Datalog-rewriting. We first present a resolution algorithm which is complete for arbitrary sets of tgds and egds. We then show that a technique of saturation can be used to achieve completeness with respect to First-Order (FO) query rewriting. We then investigate the class of guarded tgds (with a loose definition of guardedness), and show that every set of tgds in this class can be rewritten into an equivalent set of standard Datalog rules. On the negative side, this implies that Datalog +/- has (only) the same expressive power as standard Datalog in terms of query answering. On the positive side however, this mean that known results and existing optimization techniques (such as Magic-Set) may be applied in the context of Datalog +/- despite its richer syntax.
Analytical model of misinformation of a social network node
Venue: arXiv cs.SI 2012
Year: 2012

This paper presents the research of the influence of cognitive, behavioral, representational factors on the susceptibility of the participants in social networks to misinformation, as well as on the activity of the nodes in this regard. The importance of this research consists of method of blocking the propaganda. This is very important because when people involuntarily acquire information some of them experience an undesired change in their social attitude. Such phenomena typically lead towards the information warfare. A model was developed during this research for calculating the level of misinformation of the social network participant (network node) based on the model of iterative learning process.
GLCM-based chi-square histogram distance for automatic detection of defects on patterned textures
Venue: arXiv cs.CV 2012
Year: 2012

Chi-square histogram distance is one of the distance measures that can be used to find dissimilarity between two histograms. Motivated by the fact that texture discrimination by human vision system is based on second-order statistics, we make use of histogram of gray-level co-occurrence matrix (GLCM) that is based on second-order statistics and propose a new machine vision algorithm for automatic defect detection on patterned textures. Input defective images are split into several periodic blocks and GLCMs are computed after quantizing the gray levels from 0-255 to 0-63 to keep the size of GLCM compact and to reduce computation time. Dissimilarity matrix derived from chi-square distances of the GLCMs is subjected to hierarchical clustering to automatically identify defective and defect-free blocks. Effectiveness of the proposed method is demonstrated through experiments on defective real-fabric images of 2 major wallpaper groups (pmm and p4m groups).
UCF101: A Dataset of 101 Human Actions Classes From Videos in The Wild
Venue: arXiv cs.CV 2012
Year: 2012

We introduce UCF101 which is currently the largest dataset of human actions. It consists of 101 action classes, over 13k clips and 27 hours of video data. The database consists of realistic user uploaded videos containing camera motion and cluttered background. Additionally, we provide baseline action recognition results on this new dataset using standard bag of words approach with overall performance of 44.5%. To the best of our knowledge, UCF101 is currently the most challenging dataset of actions due to its large number of classes, large number of clips and also unconstrained nature of such clips.