Linear Discriminant Analysis (LDA) is a very common technique for dimensionality reduction problems as a preprocessing step for machine learning and pattern classification applications. At the same time, it is usually used as a black box, but (sometimes) not well understood. The aim of this paper is to build a solid intuition for what is LDA, and how LDA works, thus enabling readers of all levels be able to get a better understanding of the LDA and to know how to apply this technique in different applications. The paper first gave the basic definitions and steps of how LDA technique works supported with visual explanations of these steps. Moreover, the two methods of computing the LDA space, i.e. class-dependent and class-independent methods, were explained in details. Then, in a step-by-step approach, two numerical examples are demonstrated to show how the LDA space can be calculated in case of the class-dependent and class-independent methods. Furthermore, two of the most common LDA problems (i.e. Small Sample Size (SSS) and non-linearity problems) were highlighted and illustrated, and state-of-the-art solutions to these problems were investigated and explained. Finally, a number of experiments was conducted with different datasets to (1) investigate the effect of the eigenvectors that used in the LDA space on the robustness of the extracted feature for the classification accuracy, and (2) to show when the SSS problem occurs and how it can be addressed.
Collaborative tagging systems allow users to assign keywords - so called "tags" - to resources. Tags are used for navigation, finding resources and serendipitous browsing and thus provide an immediate benefit for users. These systems usually include tag recommendation mechanisms easing the process of finding good tags for a resource, but also consolidating the tag vocabulary across users. In practice, however, only very basic recommendation strategies are applied. In this paper we evaluate and compare several recommendation algorithms on large-scale real life datasets: an adaptation of user-based collaborative filtering, a graph-based recommender built on top of the FolkRank algorithm, and simple methods based on counting tag occurrences. We show that both FolkRank and collaborative filtering provide better results than non-personalized baseline methods. Moreover, since methods based on counting tag occurrences are computationally cheap, and thus usually preferable for real time scenarios, we discuss simple approaches for improving the performance of such methods. We show, how a simple recommender based on counting tags from users and resources can perform almost as good as the best recommender.
Minimally Unsatisfiable Subformulas (MUS) find a wide range of practical applications, including product configuration, knowledge-based validation, and hardware and software design and verification. MUSes also find application in recent Maximum Satisfiability algorithms and in CNF formula redundancy removal. Besides direct applications in Propositional Logic, algorithms for MUS extraction have been applied to more expressive logics. This paper proposes two algorithms for computation of MUSes of propositional formulas in Conjunctive Normal Form (CNF). The first algorithm is optimal in its class, meaning that it requires the smallest number of calls to a SAT solver. The second algorithm extends earlier work, but implements a number of new techniques. Among these, this paper analyzes in detail the technique of recursive model rotation, which provides significant performance gains in practice. Experimental results, obtained on representative practical benchmarks, indicate that the new algorithms achieve significant performance gains with respect to state of the art MUS extraction algorithms.
Agreement, cooperation and trust would be straightforward if deception did not ever occur in communicative interactions. Humans have deceived one another since the species began. Do machines deceive one another or indeed humans? If they do, how may we detect this? To detect machine deception, arguably requires a model of how machines may deceive, and how such deception may be identified. Theory of Mind (ToM) provides the opportunity to create intelligent machines that are able to model the minds of other agents. The future implications of a machine that has the capability to understand other minds (human or artificial) and that also has the reasons and intentions to deceive others are dark from an ethical perspective. Being able to understand the dishonest and unethical behaviour of such machines is crucial to current research in AI. In this paper, we present a high-level approach for modelling machine deception using ToM under factors of uncertainty and we propose an implementation of this model in an Agent-Oriented Programming Language (AOPL). We show that the Multi-Agent Systems (MAS) paradigm can be used to integrate concepts from two major theories of deception, namely Information Manipulation Theory 2 (IMT2) and Interpersonal Deception Theory (IDT), and how to apply these concepts in order to build a model of computational deception that takes into account ToM. To show how agents use ToM in order to deceive, we define an epistemic agent mechanism using BDI-like architectures to analyse deceptive interactions between deceivers and their potential targets and we also explain the steps in which the model can be implemented in an AOPL. To the best of our knowledge, this work is one of the first attempts in AI that (i) uses ToM along with components of IMT2 and IDT in order to analyse deceptive interactions and (ii) implements such a model.
Cognitive agent abstractions can help to engineer intelligent systems across mobile devices. On smartphones, the data obtained from onboard sensors can give valuable insights into the user's current situation. Unfortunately, today's cognitive agent frameworks cannot cope well with the challenging characteristics of sensor data. Sensor data is located on a low abstraction level and the individual data elements are not meaningful when observed in isolation. In contrast, cognitive agents operate on high-level percepts and lack the means to effectively detect complex spatio-temporal patterns in sequences of multiple percepts. In this paper, we present a stream-based perception approach that enables the agents to perceive meaningful situations in low-level sensor data streams. We present a crowdshipping case study where autonomous, self-interested agents collaborate to deliver parcels to their destinations. We show how situations derived from smartphone sensor data can trigger and guide auctions, which the agents use to reach agreements. Experiments with real smartphone data demonstrate the benefits of stream-based agent perception.
Task delegation is essential to many applications, ranging from outsourcing of work to the design of routing protocols. Much research in computational trust has been devoted to the generation of policies to determine which agent should the task be delegated to, given the agent's past behaviour. Such work, however, does not consider the possibility of the agent delegating the task onwards, inducing a chain of delegation events before the task is finally executed. In this paper, we consider the process of delegation chain formation, introducing a new algorithm based on quitting games to cater for recursive scenarios. We evaluate our proposal under various network topologies, consistently demonstrating its superiority with respect to recursive adaptations of existing multi-armed bandit algorithms.
We study a property of procedures for allocating indivisible goods to agents called duplication monotonicity, first proposed by Baumeister et al. (Journal of Autonomous Agents and Multi-Agent Systems 31 (2017) 628-655). An allocation procedure satisfies duplication monotonicity if two agents with identical preferences always receive at least as good a share together than one agent would on her own. We study this property first for rules that take cardinal inputs, i.e., the numerical utility of each item to each agent; and secondly for rules that take ordinal inputs, i.e., a ranking of all the items for each agent. In the first case, the rules are parametrized by a social welfare ordering interpolating between utilitarian and egalitarian approaches. In the second case, the rules are additionally parametrized by a scoring vector. We show that in the ordinal setting, only the rule using utilitarian social welfare satisfies duplication monotonicity. In stark contrast, in the ordinal setting we prove that a form of duplication monotonicity holds under a weak assumption on the social welfare function (satisfied by all our examples), answering a question by Baumeister et al. (Journal of Autonomous Agents and Multi-Agent Systems 31 (2017) 628-655).
Many creative methods, such as different types of brainstorming, are based on the collaboration among a set of persons. The collaboration follows some well established workflows, which could be formalized. This would allow the generation of computational models that can be implemented to make some tools that facilitate the enactment of creative processes, or the simulation for the analysis of their characteristics. This work shows how to model this kind of collaborative creative processes as multi-agent systems, by representing the participants as interacting agents in well-defined workflows. This is done with the INGENIAS modeling language and tools, which also support rapid prototyping using the JADE agent platform. A concrete creative method, Symbolic Brainstorming, is used to illustrate and validate the feasibility of the approach.
The paper reviews methods on automatic annotation of texts with Wikipedia entries. The process, called Wikification aims at building references between concepts identified in the text and Wikipedia articles. Wikification finds many applications, especially in text representation, where it enables one to capture the semantic similarity of the documents. Also, it can be considered as automatic tagging of the text. We describe typical approaches to Wikification, and identify their advantages and disadvantages. The main problem for wide usage of the Wikification method is the lack of open-sourced frameworks that enable researchers to work cooperatively on that problem. Also problematic is the lack of a unified platform for evaluation of the results proposed by different approaches.
Speaker state recognition is an important issue to understand the human behaviour and to achieve more comprehensive speech interactive systems, and therefore has received much attention in recent years. This work addresses the automatic classification of three types of child emotions in vocalisations: neutral mood, fussing (negative mood) and crying (negative mood). Speech, in a broad sense, contains a lot of para-linguistic information that can be revealed by means of different methods for feature extraction and, in this case, these would be useful for mood detection. Here, several set of features are proposed, combined and compared with state-of-art characteristics used for speech-related tasks, and these are based on spectral information, bio-inspired ear model, auditory sparse representations with dictionaries, optimised wavelet coefficients and optimised filter bank for cepstral representation. All the experiments were performed using the Extreme Learning Machines as classifier because it is a state-of-art classifier and to achieve comparable results. The results show that by means of the proposed feature extraction methods it is possible to improve the performance provided by the baseline features. Also, different combinations of the developed feature sets were studied in order to further exploit their properties.
The problem of Multi-Agent Path Finding (MAPF) is to find paths for a fixed set of agents from their current locations to some desired locations in such a way that the agents do not collide with each other. This problem has been extensively theoretically studied, frequently using an abstract model, that expects uniform durations of moving primitives and perfect synchronization of agents/robots. In this paper we study the question of how the abstract plans generated by existing MAPF algorithms perform in practice when executed on real robots, namely Ozobots. In particular, we use several abstract models of MAPF, including a robust version and a version that assumes turning of a robot, we translate the abstract plans to sequences of motion primitives executable on Ozobots, and we empirically compare the quality of plan execution (real makespan, the number of collisions).
Nowadays, society is in constant evolution, which allows constant production of new knowledge. In this way, citizens are constantly pressured to obtain new qualifications through training/requalification. The need for qualified people has been growing exponentially, which means that resources for education/training are limited to being used more efficiently. In this paper we will focus in the design the user model, so, we propose an innovative approach to design a user model that monitors the user's biometric behaviour by measuring their level of attention during e-learning activities. In addition, a machine learning catego-rization model is presented that oversees user activity during the session. We intend to use non-invasive methods of intelligent tutoring systems, observing the interaction of users during the session. Furthermore, this article highlights the main biometric behavioural variations for each activity and bases the set of attributes relevant to the development of machine learning classifiers to predict users' learning preference. The results show that there are still mechanisms that can be explored and improved to better understand the complex relationship between human behaviour, attention and evaluation that could be used to implement better learning strategies. These results can be decisive in improving ITS in e-learning environments and to predict user behaviour based on their interaction with technology devices.
Time is pervasive of the human way of approaching reality, so that it has been widely studied in many research areas, including AI and relational Temporal Databases (TDB). While temporally imprecise information has been widely studied by the AI community, only few approaches have faced temporal indeterminacy (in particular, "don't know exactly when" indeterminacy) in TDBs. Indeed, as we will show in this paper, the treatment of time in general, and of temporal indeterminacy in particular, involves the introduction of implicit forms of data representation in TDBs. As a consequence, we propose a new AI-style methodology to cope with temporal indeterminacy in TDBs. Specifically, we show that typical AI notions and techniques, such as making explicit the semantics of the representation formalism, and adopting symbolic manipulation techniques based on such a semantics, can be fruitfully exploited in the development of a "principled" treatment of indeterminate time in relational databases.
The extraction of the relevant and debated opinions from online social media and commercial websites is an emerging task in the opinion mining research field. Its growing relevance is mainly due to the impact of exploiting such techniques in different application domains from social science analysis to personal advertising. In this paper, we present SMACk, our opinion summary system built on top of an argumentation framework with the aim to exchange, communicate and resolve possibly conflicting viewpoints. SMACk allows the user to extract debated opinions from a set of documents containing user-generated content from online commercial websites, and to automatically identify the mostly debated positive aspects of the issue of the debate, as well as the mostly debated negative ones. The key advantage of such a framework is the combination of different methods, i.e., formal argumentation theory and natural language processing, to support users in making more informed decisions, e.g., in the context of online purchases.
A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.