OpenRaiser/Intern-Atlas huggingface dataset:
Interesting Multi-Relational Patterns
Venue: arXiv cs.DB 2011
Year: 2011

Mining patterns from multi-relational data is a problem attracting increasing interest within the data mining community. Traditional data mining approaches are typically developed for highly simplified types of data, such as an attribute-value table or a binary database, such that those methods are not directly applicable to multi-relational data. Nevertheless, multi-relational data is a more truthful and therefore often also a more powerful representation of reality. Mining patterns of a suitably expressive syntax directly from this representation, is thus a research problem of great importance. In this paper we introduce a novel approach to mining patterns in multi-relational data. We propose a new syntax for multi-relational patterns as complete connected subgraphs in a representation of the database as a K-partite graph. We show how this pattern syntax is generally applicable to multirelational data, while it reduces to well-known tiles [7] when the data is a simple binary or attribute-value table. We propose RMiner, an efficient algorithm to mine such patterns, and we introduce a method for quantifying their interestingness when contrasted with prior information of the data miner. Finally, we illustrate the usefulness of our approach by discussing results on real-world and synthetic databases.
Sub-Nyquist Sampling: Bridging Theory and Practice
Venue: arXiv cs.IT 2011
Year: 2011

Sampling theory encompasses all aspects related to the conversion of continuous-time signals to discrete streams of numbers. The famous Shannon-Nyquist theorem has become a landmark in the development of digital signal processing. In modern applications, an increasingly number of functions is being pushed forward to sophisticated software algorithms, leaving only those delicate finely-tuned tasks for the circuit level. In this paper, we review sampling strategies which target reduction of the ADC rate below Nyquist. Our survey covers classic works from the early 50's of the previous century through recent publications from the past several years. The prime focus is bridging theory and practice, that is to pinpoint the potential of sub-Nyquist strategies to emerge from the math to the hardware. In that spirit, we integrate contemporary theoretical viewpoints, which study signal modeling in a union of subspaces, together with a taste of practical aspects, namely how the avant-garde modalities boil down to concrete signal processing systems. Our hope is that this presentation style will attract the interest of both researchers and engineers in the hope of promoting the sub-Nyquist premise into practical applications, and encouraging further research into this exciting new frontier.
Learning When Training Data are Costly: The Effect of Class Distribution on Tree Induction
Venue: arXiv cs.AI 2011
Year: 2011

For large, real-world inductive learning problems, the number of training examples often must be limited due to the costs associated with procuring, preparing, and storing the training examples and/or the computational costs associated with learning from them. In such circumstances, one question of practical importance is: if only n training examples can be selected, in what proportion should the classes be represented? In this article we help to answer this question by analyzing, for a fixed training-set size, the relationship between the class distribution of the training data and the performance of classification trees induced from these data. We study twenty-six data sets and, for each, determine the best class distribution for learning. The naturally occurring class distribution is shown to generally perform well when classifier performance is evaluated using undifferentiated error rate (0/1 loss). However, when the area under the ROC curve is used to evaluate classifier performance, a balanced distribution is shown to perform well. Since neither of these choices for class distribution always generates the best-performing classifier, we introduce a budget-sensitive progressive sampling algorithm for selecting training examples based on the class associated with each example. An empirical analysis of this algorithm shows that the class distribution of the resulting training set yields classifiers with good (nearly-optimal) classification performance.
Acquiring Word-Meaning Mappings for Natural Language Interfaces
Venue: arXiv cs.CL 2011
Year: 2011

This paper focuses on a system, WOLFIE (WOrd Learning From Interpreted Examples), that acquires a semantic lexicon from a corpus of sentences paired with semantic representations. The lexicon learned consists of phrases paired with meaning representations. WOLFIE is part of an integrated system that learns to transform sentences into representations such as logical database queries. Experimental results are presented demonstrating WOLFIE's ability to learn useful lexicons for a database interface in four different natural languages. The usefulness of the lexicons learned by WOLFIE are compared to those acquired by a similar system, with results favorable to WOLFIE. A second set of experiments demonstrates WOLFIE's ability to scale to larger and more difficult, albeit artificially generated, corpora. In natural language acquisition, it is difficult to gather the annotated data needed for supervised learning; however, unannotated data is fairly plentiful. Active learning methods attempt to select for annotation and training only the most informative examples, and therefore are potentially very useful in natural language applications. However, most results to date for active learning have only considered standard classification tasks. To reduce annotation effort while maintaining accuracy, we apply active learning to semantic lexicons. We show that active learning can significantly reduce the number of annotated examples required to achieve a given level of performance.
Towards Adjustable Autonomy for the Real World
Venue: arXiv cs.AI 2011
Year: 2011

Adjustable autonomy refers to entities dynamically varying their own autonomy, transferring decision-making control to other entities (typically agents transferring control to human users) in key situations. Determining whether and when such transfers-of-control should occur is arguably the fundamental research problem in adjustable autonomy. Previous work has investigated various approaches to addressing this problem but has often focused on individual agent-human interactions. Unfortunately, domains requiring collaboration between teams of agents and humans reveal two key shortcomings of these previous approaches. First, these approaches use rigid one-shot transfers of control that can result in unacceptable coordination failures in multiagent settings. Second, they ignore costs (e.g., in terms of time delays or effects on actions) to an agent's team due to such transfers-of-control. To remedy these problems, this article presents a novel approach to adjustable autonomy, based on the notion of a transfer-of-control strategy. A transfer-of-control strategy consists of a conditional sequence of two types of actions: (i) actions to transfer decision-making control (e.g., from an agent to a user or vice versa) and (ii) actions to change an agent's pre-specified coordination constraints with team members, aimed at minimizing miscoordination costs. The goal is for high-quality individual decisions to be made with minimal disruption to the coordination of the team. We present a mathematical model of transfer-of-control strategies. The model guides and informs the operationalization of the strategies using Markov Decision Processes, which select an optimal strategy, given an uncertain environment and costs to the individuals and teams. The approach has been carefully evaluated, including via its use in a real-world, deployed multi-agent system that assists a research group in its daily activities.
Early Phishing
Venue: arXiv cs.CR 2011
Year: 2011

The history of phishing traces back in important ways to the mid-1990s when hacking software facilitated the mass targeting of people in password stealing scams on America Online (AOL). The first of these software programs was mine, called AOHell, and it was where the word phishing was coined. The software provided an automated password and credit card-stealing mechanism starting in January 1995. Though the practice of tricking users in order to steal passwords or information possibly goes back to the earliest days of computer networking, AOHell's phishing system was the first automated tool made publicly available for this purpose. The program influenced the creation of many other automated phishing systems that were made over a number of years. These tools were available to amateurs who used them to engage in a countless number of phishing attacks. By the later part of the decade, the activity moved from AOL to other networks and eventually grew to involve professional criminals on the internet. What began as a scheme by rebellious teenagers to steal passwords evolved into one of the top computer security threats affecting people, corporations, and governments.
Key Factors for Information Dissemination on Communicating Products and Fixed Databases
Venue: arXiv cs.NI 2011
Year: 2011

Intelligent products carrying their own information are more and more present nowadays. In recent years, some authors argued the usage of such products for the Supply Chain Management Industry. Indeed, a multitude of informational vectors take place in such environments like fixed databases or manufactured products on which we are able to embed significant proportion of data. By considering distributed database systems, we can allocate specific data fragments to the product useful to manage its own evolution. The paper aims to analyze the Supply Chain performance according to different strategies of information distribution. Thus, different distribution patterns between informational vectors are studied. The purpose is to determine the key factors which lead to improve information distribution performance in term of time properties.
VHPOP: Versatile Heuristic Partial Order Planner
Venue: arXiv cs.AI 2011
Year: 2011

VHPOP is a partial order causal link (POCL) planner loosely based on UCPOP. It draws from the experience gained in the early to mid 1990's on flaw selection strategies for POCL planning, and combines this with more recent developments in the field of domain independent planning such as distance based heuristics and reachability analysis. We present an adaptation of the additive heuristic for plan space planning, and modify it to account for possible reuse of existing actions in a plan. We also propose a large set of novel flaw selection strategies, and show how these can help us solve more problems than previously possible by POCL planners. VHPOP also supports planning with durative actions by incorporating standard techniques for temporal constraint reasoning. We demonstrate that the same heuristic techniques used to boost the performance of classical POCL planning can be effective in domains with durative actions as well. The result is a versatile heuristic POCL planner competitive with established CSP-based and heuristic state space planners.
The Capacity of MIMO Channels with Per-Antenna Power Constraint
Venue: arXiv cs.IT 2011
Year: 2011

We establish the optimal input signaling and the capacity of MIMO channels under per-antenna power constraint. While admitting a linear eigenbeam structure, the optimal input is no longer diagonalizable by the channel right singular vectors as with sum power constraint. We formulate the capacity optimization as an SDP problem and solve in closed-form the optimal input covariance as a function of the dual variable. We then design an efficient algorithm to find this optimal input signaling for all channel sizes. The proposed algorithm allows for straightforward implementation in practical systems in real time. Simulation results show that with equal constraint per antenna, capacity with per-antenna power can be close to capacity with sum power, but as the constraint becomes more skew, the two capacities diverge. Forcing input eigenbeams to match the channel right singular vectors achieves no improvement over independent signaling and can even be detrimental to capacity.
Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model
Venue: arXiv cs.SI 2011
Year: 2011

Networks arising from social, technological and natural domains exhibit rich connectivity patterns and nodes in such networks are often labeled with attributes or features. We address the question of modeling the structure of networks where nodes have attribute information. We present a Multiplicative Attribute Graph (MAG) model that considers nodes with categorical attributes and models the probability of an edge as the product of individual attribute link formation affinities. We develop a scalable variational expectation maximization parameter estimation method. Experiments show that MAG model reliably captures network connectivity as well as provides insights into how different attributes shape the network structure.
Exploiting Reputation in Distributed Virtual Environments
Venue: arXiv cs.AI 2011
Year: 2011

The cognitive research on reputation has shown several interesting properties that can improve both the quality of services and the security in distributed electronic environments. In this paper, the impact of reputation on decision-making under scarcity of information will be shown. First, a cognitive theory of reputation will be presented, then a selection of simulation experimental results from different studies will be discussed. Such results concern the benefits of reputation when agents need to find out good sellers in a virtual market-place under uncertainty and informational cheating.
Morphological Reconstruction for Word Level Script Identification
Venue: arXiv cs.CV 2011
Year: 2011

A line of a bilingual document page may contain text words in regional language and numerals in English. For Optical Character Recognition (OCR) of such a document page, it is necessary to identify different script forms before running an individual OCR system. In this paper, we have identified a tool of morphological opening by reconstruction of an image in different directions and regional descriptors for script identification at word level, based on the observation that every text has a distinct visual appearance. The proposed system is developed for three Indian major bilingual documents, Kannada, Telugu and Devnagari containing English numerals. The nearest neighbour and k-nearest neighbour algorithms are applied to classify new word images. The proposed algorithm is tested on 2625 words with various font styles and sizes. The results obtained are quite encouraging
A Distributed Agent Based System to Control and Coordinate Large Scale Data Transfers
Venue: arXiv cs.DC 2011
Year: 2011

We present a distributed agent based system used to monitor, configure and control complex, large scale data transfers in the Wide Area Network. The Localhost Information Service Agent (LISA) is a lightweight dynamic service that provides complete system and applications monitoring, is capable to dynamically configure system parameters and can help in optimizing distributed applications. As part of the MonALISA (Monitoring Agents in A Large Integrated Services Architecture) system, LISA is an end host agent capable to collect any type of monitoring information, to distribute them, and to take actions based on local or global decision units. The system has been used for the Bandwidth Challenge at Supercomputing 2006 to coordinate global large scale data transfers using Fast Data Transfer (FDT) application between hundreds of servers distributed on major Grid sites involved in processing High Energy Physics data for the future Large Hadron Collider experiments.
The Open Annotation Collaboration (OAC) Model
Venue: arXiv cs.DL 2011
Year: 2011

Annotations allow users to associate additional information with existing resources. Using proprietary and closed systems on the Web, users are already able to annotate multimedia resources such as images, audio and video. So far, however, this information is almost always kept locked up and inaccessible to the Web of Data. We believe that an important step to take is the integration of multimedia annotations and the Linked Data principles. This should allow clients to easily publish and consume, thus exchange annotations about resources via common Web standards. We first present the current status of the Open Annotation Collaboration, an international initiative that is currently working on annotation interoperability specifications based on best practices from the Linked Data effort. Then we present two use cases and early prototypes that make use of the proposed annotation model and present lessons learned and discuss yet open technical issues.
Learning Shape and Texture Characteristics of CT Tree-in-Bud Opacities for CAD Systems
Venue: arXiv cs.CV 2011
Year: 2011

Although radiologists can employ CAD systems to characterize malignancies, pulmonary fibrosis and other chronic diseases; the design of imaging techniques to quantify infectious diseases continue to lag behind. There exists a need to create more CAD systems capable of detecting and quantifying characteristic patterns often seen in respiratory tract infections such as influenza, bacterial pneumonia, or tuborculosis. One of such patterns is Tree-in-bud (TIB) which presents \textit{thickened} bronchial structures surrounding by clusters of \textit{micro-nodules}. Automatic detection of TIB patterns is a challenging task because of their weak boundary, noisy appearance, and small lesion size. In this paper, we present two novel methods for automatically detecting TIB patterns: (1) a fast localization of candidate patterns using information from local scale of the images, and (2) a Möbius invariant feature extraction method based on learned local shape and texture properties. A comparative evaluation of the proposed methods is presented with a dataset of 39 laboratory confirmed viral bronchiolitis human parainfluenza (HPIV) CTs and 21 normal lung CTs. Experimental results demonstrate that the proposed CAD system can achieve high detection rate with an overall accuracy of 90.96%.
Learning to Coordinate Efficiently: A Model-based Approach
Venue: arXiv cs.AI 2011
Year: 2011

In common-interest stochastic games all players receive an identical payoff. Players participating in such games must learn to coordinate with each other in order to receive the highest-possible value. A number of reinforcement learning algorithms have been proposed for this problem, and some have been shown to converge to good solutions in the limit. In this paper we show that using very simple model-based algorithms, much better (i.e., polynomial) convergence rates can be attained. Moreover, our model-based algorithms are guaranteed to converge to the optimal value, unlike many of the existing algorithms.
Planning Through Stochastic Local Search and Temporal Action Graphs in LPG
Venue: arXiv cs.AI 2011
Year: 2011

We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting 'durative actions' and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called 'Temporal Action Graphs' (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.
Potential-Based Shaping and Q-Value Initialization are Equivalent
Venue: arXiv cs.LG 2011
Year: 2011

Shaping has proven to be a powerful but precarious means of improving reinforcement learning performance. Ng, Harada, and Russell (1999) proposed the potential-based shaping algorithm for adding shaping rewards in a way that guarantees the learner will learn optimal behavior. In this note, we prove certain similarities between this shaping algorithm and the initialization step required for several reinforcement learning algorithms. More specifically, we prove that a reinforcement learner with initial Q-values based on the shaping algorithm's potential function make the same updates throughout learning as a learner receiving potential-based shaping rewards. We further prove that under a broad category of policies, the behavior of these two learners are indistinguishable. The comparison provides intuition on the theoretical properties of the shaping algorithm as well as a suggestion for a simpler method for capturing the algorithm's benefit. In addition, the equivalence raises previously unaddressed issues concerning the efficiency of learning with potential-based shaping.
Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources
Venue: arXiv cs.AI 2011
Year: 2011

The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types. Finally, we present empirical results of applying our scheduling algorithm to the Latin Square problem.
The Metric-FF Planning System: Translating "Ignoring Delete Lists" to Numeric State Variables
Venue: arXiv cs.AI 2011
Year: 2011

Planning with numeric state variables has been a challenge for many years, and was a part of the 3rd International Planning Competition (IPC-3). Currently one of the most popular and successful algorithmic techniques in STRIPS planning is to guide search by a heuristic function, where the heuristic is based on relaxing the planning task by ignoring the delete lists of the available actions. We present a natural extension of ``ignoring delete lists'' to numeric state variables, preserving the relevant theoretical properties of the STRIPS relaxation under the condition that the numeric task at hand is ``monotonic''. We then identify a subset of the numeric IPC-3 competition language, ``linear tasks'', where monotonicity can be achieved by pre-processing. Based on that, we extend the algorithms used in the heuristic planning system FF to linear tasks. The resulting system Metric-FF is, according to the IPC-3 results which we discuss, one of the two currently most efficient numeric planners.