OpenRaiser/Intern-Atlas huggingface dataset:
Nonparametric Bayesian Mixed-effect Model: a Sparse Gaussian Process Approach
Venue: arXiv cs.LG 2012
Year: 2012

Multi-task learning models using Gaussian processes (GP) have been developed and successfully applied in various applications. The main difficulty with this approach is the computational cost of inference using the union of examples from all tasks. Therefore sparse solutions, that avoid using the entire data directly and instead use a set of informative "representatives" are desirable. The paper investigates this problem for the grouped mixed-effect GP model where each individual response is given by a fixed-effect, taken from one of a set of unknown groups, plus a random individual effect function that captures variations among individuals. Such models have been widely used in previous work but no sparse solutions have been developed. The paper presents the first sparse solution for such problems, showing how the sparse approximation can be obtained by maximizing a variational lower bound on the marginal likelihood, generalizing ideas from single-task Gaussian processes to handle the mixed-effect model as well as grouping. Experiments using artificial and real data validate the approach showing that it can recover the performance of inference with the full sample, that it outperforms baseline methods, and that it outperforms state of the art sparse solutions for other multi-task GP formulations.
The role of colour preattentive processing in human-computer interaction task efficiency: a preliminary study
Venue: arXiv cs.HC 2012
Year: 2012

In this paper, results of experimental research on the preattentive mechanism in the human-computer interaction (HCI) were presented. Fifty four subjects were asked to find interface elements from various panel structures. The arrangements were differentiated by their orientation (vertical, horizontal), colour pattern (ordered, unordered) and object background colours (green-blue, green-red, blue-red). The main finding of the study generally confirms the profits provided by the visual preattentive processing of the colour feature in graphical panel operation efficiency. However, the vertical way of arranging the items in search layouts resulted in decreasing the preattentive effect related to the item background colour. In regular, chessboard-like patterns of different coloured items, the effect of the early vision was less salient than in the case of structures with randomly dispersed colours. The reported results can help in designing efficient graphical user-computer interfaces in many interactive information systems.
Graph Laplacians on Singular Manifolds: Toward understanding complex spaces: graph Laplacians on manifolds with singularities and boundaries
Venue: arXiv cs.AI 2012
Year: 2012

Recently, much of the existing work in manifold learning has been done under the assumption that the data is sampled from a manifold without boundaries and singularities or that the functions of interest are evaluated away from such points. At the same time, it can be argued that singularities and boundaries are an important aspect of the geometry of realistic data. In this paper we consider the behavior of graph Laplacians at points at or near boundaries and two main types of other singularities: intersections, where different manifolds come together and sharp "edges", where a manifold sharply changes direction. We show that the behavior of graph Laplacian near these singularities is quite different from that in the interior of the manifolds. In fact, a phenomenon somewhat reminiscent of the Gibbs effect in the analysis of Fourier series, can be observed in the behavior of graph Laplacian near such points. Unlike in the interior of the domain, where graph Laplacian converges to the Laplace-Beltrami operator, near singularities graph Laplacian tends to a first-order differential operator, which exhibits different scaling behavior as a function of the kernel width. One important implication is that while points near the singularities occupy only a small part of the total volume, the difference in scaling results in a disproportionately large contribution to the total behavior. Another significant finding is that while the scaling behavior of the operator is the same near different types of singularities, they are very distinct at a more refined level of analysis. We believe that a comprehensive understanding of these structures in addition to the standard case of a smooth manifold can take us a long way toward better methods for analysis of complex non-linear data and can lead to significant progress in algorithm design.
The monotonicity of f-vectors of random polytopes
Venue: arXiv cs.CG 2012
Year: 2012

Let K be a compact convex body in Rd, let Kn be the convex hull of n points chosen uniformly and independently in K, and let fi(Kn) denote the number of i-dimensional faces of Kn. We show that for planar convex sets, E(f0(Kn)) is increasing in n. In dimension d>=3 we prove that if lim(E((f[d -1](Kn))/(An^c)->1 when n->infinity for some constants A and c > 0 then the function E(f[d-1](Kn)) is increasing for n large enough. In particular, the number of facets of the convex hull of n random points distributed uniformly and independently in a smooth compact convex body is asymptotically increasing. Our proof relies on a random sampling argument.
A Method for Constructing Minimally Unsatisfiable CNFs
Venue: arXiv cs.LO 2012
Year: 2012

We generalize a method of Ivor Spence (J. of Experimental Algorithms 15(March 2010)) that produces unsatisfiable cnfs and show experimentally that, for the most part, the resulting cnfs are minimally unsatisfiable.
Erratum: Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation
Venue: arXiv cs.NE 2012
Year: 2012

This erratum points out an error in the simplified drift theorem (SDT) [Algorithmica 59(3), 369-386, 2011]. It is also shown that a minor modification of one of its conditions is sufficient to establish a valid result. In many respects, the new theorem is more general than before. We no longer assume a Markov process nor a finite search space. Furthermore, the proof of the theorem is more compact than the previous ones. Finally, previous applications of the SDT are revisited. It turns out that all of these either meet the modified condition directly or by means of few additional arguments.
Efficient algorithms for robust recovery of images from compressed data
Venue: arXiv cs.IT 2012
Year: 2012

Compressed sensing (CS) is an important theory for sub-Nyquist sampling and recovery of compressible data. Recently, it has been extended by Pham and Venkatesh to cope with the case where corruption to the CS data is modeled as impulsive noise. The new formulation, termed as robust CS, combines robust statistics and CS into a single framework to suppress outliers in the CS recovery. To solve the newly formulated robust CS problem, Pham and Venkatesh suggested a scheme that iteratively solves a number of CS problems, the solutions from which converge to the true robust compressed sensing solution. However, this scheme is rather inefficient as it has to use existing CS solvers as a proxy. To overcome limitation with the original robust CS algorithm, we propose to solve the robust CS problem directly in this paper and drive more computationally efficient algorithms by following latest advances in large-scale convex optimization for non-smooth regularization. Furthermore, we also extend the robust CS formulation to various settings, including additional affine constraints, $\ell_1$-norm loss function, mixed-norm regularization, and multi-tasking, so as to further improve robust CS. We also derive simple but effective algorithms to solve these extensions. We demonstrate that the new algorithms provide much better computational advantage over the original robust CS formulation, and effectively solve more sophisticated extensions where the original methods simply cannot. We demonstrate the usefulness of the extensions on several CS imaging tasks.
Exploiting Metric Structure for Efficient Private Query Release
Venue: arXiv cs.DS 2012
Year: 2012

We consider the problem of privately answering queries defined on databases which are collections of points belonging to some metric space. We give simple, computationally efficient algorithms for answering distance queries defined over an arbitrary metric. Distance queries are specified by points in the metric space, and ask for the average distance from the query point to the points contained in the database, according to the specified metric. Our algorithms run efficiently in the database size and the dimension of the space, and operate in both the online query release setting, and the offline setting in which they must in polynomial time generate a fixed data structure which can answer all queries of interest. This represents one of the first subclasses of linear queries for which efficient algorithms are known for the private query release problem, circumventing known hardness results for generic linear queries.
Mathematical Frameworks for Pricing in the Cloud: Revenue, Fairness, and Resource Allocations
Venue: arXiv cs.CY 2012
Year: 2012

As more and more users begin to use the cloud for their computing needs, datacenter operators are increasingly pressed to effectively allocate their resources among these client users. Yet while much work has been done in this area, relatively little attention has been paid to studying perhaps the ultimate lever of resource allocation: pricing. Most data centers today charge users by "bundling" heterogeneous resources together in a fixed ratio and selling these bundles to their clients. But bundling masks the fact that different users require different combinations of resources (e.g., CPUs, memory, bandwidth) to process their jobs. The presence of multiple resources in fact allows an operator to offer many different types of pricing strategies, which may have different effects on its revenue. Moreover, to avoid user dissatisfaction, operators must consider the impact of their chosen prices on the fairness of the jobs processed for different users. In this paper, we develop an analytical framework that accounts for the fairness and revenue tradeoffs that arise in a datacenter's multi-resource setting and the impact that different pricing plans can have on this tradeoff. We characterize the implications of different pricing plans on various fairness metrics and derive analytical limits on the operator's fairness-revenue tradeoff. We then provide an algorithm to navigate this tradeoff and compare the tradeoff points for different pricing strategies on a data trace taken from a Google cluster.
Properties of the dual planar triangulations
Venue: arXiv cs.DM 2012
Year: 2012

This article is devoted to the properties of the planar triangulations. The conjugated planar triangulation will be introduced and on the base of the properties, which were achieved by the other authors there will be proved some theorems, which will show the properties of the dual triangulations. Also the numeric properties of the dual planar triangulations will be examined for the sake of understanding the interdependences of the cyclimatic numbers of different graphs between themselves. We'll see how the cyclomatic number of the planar conjugated triangulation depends on the cyclomatic number of the planar triangulation and how its increment depends on the number of the vertexes. These characteristics will be further very important for examining of Four Color Problem. The properties of the dual matrixes will also be examined. We will see that both matrixes on the one hand must meet the equal requirements, but on the other hand we will see that one characteristic cannot be fulfilled. This fact will further form the restrictions for the solution of Four Color Problem.
Computing Strong and Weak Permissions in Defeasible Logic
Venue: arXiv cs.LO 2012
Year: 2012

In this paper we propose an extension of Defeasible Logic to represent and compute three concepts of defeasible permission. In particular, we discuss different types of explicit permissive norms that work as exceptions to opposite obligations. Moreover, we show how strong permissions can be represented both with, and without introducing a new consequence relation for inferring conclusions from explicit permissive norms. Finally, we illustrate how a preference operator applicable to contrary-to-duty obligations can be combined with a new operator representing ordered sequences of strong permissions which derogate from prohibitions. The logical system is studied from a computational standpoint and is shown to have liner computational complexity.
A scalable mining of frequent quadratic concepts in d-folksonomies
Venue: arXiv cs.SI 2012
Year: 2012

Folksonomy mining is grasping the interest of web 2.0 community since it represents the core data of social resource sharing systems. However, a scrutiny of the related works interested in mining folksonomies unveils that the time stamp dimension has not been considered. For example, the wealthy number of works dedicated to mining tri-concepts from folksonomies did not take into account time dimension. In this paper, we will consider a folksonomy commonly composed of triples <users, tags, resources> and we shall consider the time as a new dimension. We motivate our approach by highlighting the battery of potential applications. Then, we present the foundations for mining quadri-concepts, provide a formal definition of the problem and introduce a new efficient algorithm, called QUADRICONS for its solution to allow for mining folksonomies in time, i.e., d-folksonomies. We also introduce a new closure operator that splits the induced search space into equivalence classes whose smallest elements are the quadri-minimal generators. Carried out experiments on large-scale real-world datasets highlight good performances of our algorithm.
A Construction for Periodic ZCZ Sequences
Venue: arXiv cs.IT 2012
Year: 2012

We introduce a construction for periodic zero correlation zone (ZCZ) sequences over roots of unity. The sequences share similarities to the perfect periodic sequence constructions of Liu, Frank, and Milewski. The sequences have two non-zero off-peak autocorrelation values which asymptotically approach $\pm 2 π$, so the sequences are asymptotically perfect.
An Ontology based System for Cloud Infrastructure Services Discovery
Venue: arXiv cs.DC 2012
Year: 2012

The Cloud infrastructure services landscape advances steadily leaving users in the agony of choice. As a result, Cloud service identification and discovery remains a hard problem due to different service descriptions, non standardised naming conventions and heterogeneous types and features of Cloud services. In this paper, we present an OWL based ontology, the Cloud Computing Ontology (CoCoOn) that defines functional and non functional concepts, attributes and relations of infrastructure services. We also present a system...
Fuzzy Based Stator Flux Optimizer Design For Direct Torque Control
Venue: arXiv cs.SY 2012
Year: 2012

Direct Torque Control (DTC) is well known as an effective control technique for high performance drives in a wide variety of industrial applications and conventional DTC technique uses two constant reference value: torque and stator flux. In this paper, a new fuzzy based stator flux optimizer has been proposed for DTC controlled induction motor drivers and simulation studies have been carried out with Matlab/Simulink to compare the proposed system behaviours at vary load conditions. The most important feature of the proposed fuzzy logic based stator flux optimizer that it self-regulates the stator flux reference value using the motor load situation without need of any motor parameters. Simulation results show that the performance of the proposed DTC technique has been improved and especially at low-load conditions torque ripples are greatly reduced with respect to the conventional DTC.
Approximating Large Frequency Moments with Pick-and-Drop Sampling
Venue: arXiv cs.DS 2012
Year: 2012

Given data stream $D = \{p_1,p_2,...,p_m\}$ of size $m$ of numbers from $\{1,..., n\}$, the frequency of $i$ is defined as $f_i = |\{j: p_j = i\}|$. The $k$-th \emph{frequency moment} of $D$ is defined as $F_k = \sum_{i=1}^n f_i^k$. We consider the problem of approximating frequency moments in insertion-only streams for $k\ge 3$. For any constant $c$ we show an $O(n^{1-2/k}\log(n)\log^{(c)}(n))$ upper bound on the space complexity of the problem. Here $\log^{(c)}(n)$ is the iterative $\log$ function. To simplify the presentation, we make the following assumptions: $n$ and $m$ are polynomially far; approximation error $ε$ and parameter $k$ are constants. We observe a natural bijection between streams and special matrices. Our main technical contribution is a non-uniform sampling method on matrices. We call our method a \emph{pick-and-drop sampling}; it samples a heavy element (i.e., element $i$ with frequency $Ω(F_k)$) with probability $Ω(1/n^{1-2/k})$ and gives approximation $\tilde{f_i} \ge (1-ε)f_i$. In addition, the estimations never exceed the real values, that is $ \tilde{f_j} \le f_j$ for all $j$. As a result, we reduce the space complexity of finding a heavy element to $O(n^{1-2/k}\log(n))$ bits. We apply our method of recursive sketches and resolve the problem with $O(n^{1-2/k}\log(n)\log^{(c)}(n))$ bits.
Simplification and integration in computing and cognition: the SP theory and the multiple alignment concept
Venue: arXiv cs.AI 2012
Year: 2012

The main purpose of this article is to describe potential benefits and applications of the SP theory, a unique attempt to simplify and integrate ideas across artificial intelligence, mainstream computing and human cognition, with information compression as a unifying theme. The theory, including a concept of multiple alignment, combines conceptual simplicity with descriptive and explanatory power in several areas including representation of knowledge, natural language processing, pattern recognition, several kinds of reasoning, the storage and retrieval of information, planning and problem solving, unsupervised learning, information compression, and human perception and cognition. In the SP machine -- an expression of the SP theory which is currently realised in the form of computer models -- there is potential for an overall simplification of computing systems, including software. As a theory with a broad base of support, the SP theory promises useful insights in many areas and the integration of structures and functions, both within a given area and amongst different areas. There are potential benefits in natural language processing (with potential for the understanding and translation of natural languages), the need for a versatile intelligence in autonomous robots, computer vision, intelligent databases, maintaining multiple versions of documents or web pages, software engineering, criminal investigations, the management of big data and gaining benefits from it, the semantic web, medical diagnosis, the detection of computer viruses, the economical transmission of data, and data fusion. Further development of these ideas would be facilitated by the creation of a high-parallel, web-based, open-source version of the SP machine, with a good user interface. This would provide a means for researchers to explore what can be done with the system and to refine it.
Review of Knowledge Management Systems As Socio-Technical System
Venue: arXiv cs.OH 2012
Year: 2012

Knowledge Management Systems as socio-technical systemperspectives has recognized for decades. Practitioners and scholars belief Knowledge Management is best carried out throught the optimization both technological and social-aspect.Lacking of understand and consider both aspects could lead organizations in misinterpretation while developing andimplementing Knowledge Management System. There is a need for practical guidance how Knowledge Management System should implement in organizations. We propose a framework that could use by practitioner and manager as guidance in developing and implementing Knowledge Management System as Socio-Technical Systems. The framework developed base on Pan and Scarborough view of Knowledge Management as Socio-Technical system. Our framework consists of: Infrastructure(technology), Info structure (organizational structure) and Info culture (organizational culture). This concept would lead practitioners get clear understand aspect contribute to Knowledge Management System success as Socio-Technical System.
Uniform Strategies
Venue: arXiv cs.GT 2012
Year: 2012

We consider turn-based game arenas for which we investigate uniformity properties of strategies. These properties involve bundles of plays, that arise from some semantical motive. Typically, we can represent constraints on allowed strategies, such as being observation-based. We propose a formal language to specify uniformity properties and demonstrate its relevance by rephrasing various known problems from the literature. Note that the ability to correlate different plays cannot be achieved by any branching-time logic if not equipped with an additional modality, so-called R in this contribution. We also study an automated procedure to synthesize strategies subject to a uniformity property, which strictly extends existing results based on, say standard temporal logics. We exhibit a generic solution for the synthesis problem provided the bundles of plays rely on any binary relation definable by a finite state transducer. This solution yields a non-elementary procedure.
Take Care: A Study on Usability Evaluation Methods for Children
Venue: arXiv cs.HC 2012
Year: 2012

Nowadays whenever a user buys any gadget, apart from the price his focus would also be on how easy is the functionality of the gadget. This means users are more concerned towards the usability of the gadget. Therefore, this study set to explore usability evaluations methods for children in order to analyze their roles in the development of technology. Usability evaluation methods which are successfully tested on the adults are investigated to find out how successfully they can also be applied to children. The results of the review indicate that usability evaluation with children is more challenging than with adults. The study found that depending on one type of usability evaluation method would not be an appropriate decision.
An ontology-based approach to relax traffic regulation for autonomous vehicle assistance
Venue: arXiv cs.AI 2012
Year: 2012

Traffic regulation must be respected by all vehicles, either human- or computer- driven. However, extreme traffic situations might exhibit practical cases in which a vehicle should safely and reasonably relax traffic regulation, e.g., in order not to be indefinitely blocked and to keep circulating. In this paper, we propose a high-level representation of an automated vehicle, other vehicles and their environment, which can assist drivers in taking such "illegal" but practical relaxation decisions. This high-level representation (an ontology) includes topological knowledge and inference rules, in order to compute the next high-level motion an automated vehicle should take, as assistance to a driver. Results on practical cases are presented.