Instance weighting versus threshold adjusting for cost-sensitive classification

In real-world classification problems, different types of misclassification errors often have asymmetric costs, thus demanding cost-sensitive learning methods that attempt to minimize average misclassification cost rather than plain error rate. Instance weighting and post hoc threshold adjusting are two major approaches to cost-sensitive classifier learning. This paper compares the effects of these two approaches on several standard, off-the-shelf classification methods. The comparison indicates that the two approaches lead to similar results for some classification methods, such as Naïve Bayes, logistic regression, and backpropagation neural network, but very different results for other methods, such as decision tree, decision table, and decision rule learners. The findings from this research have important implications on the selection of the cost-sensitive classifier learning approach as well as on the interpretation of a recently published finding about the relative performance of Naïve Bayes and decision trees.     

Algorithms for unimodal segmentation with applications to unimodality detection

We study the problem of segmenting a sequence into k pieces so that the resulting segmentation satisfies monotonicity or unimodality constraints. Unimodal functions can be used to model phenomena in which a measured variable first increases to a certain level and then decreases. We combine a well-known unimodal regression algorithm with a simple dynamic-programming approach to obtain an optimal quadratic-time algorithm for the problem of unimodal k-segmentation. In addition, we describe a more efficient greedy-merging heuristic that is experimentally shown to give solutions very close to the optimal. As a concrete application of our algorithms, we describe methods for testing if a sequence behaves unimodally or not. The methods include segmentation error comparisons, permutation testing, and a BIC-based scoring scheme. Our experimental evaluation shows that our algorithms and the proposed unimodality tests give very intuitive results, for both real-valued and binary data. Niina Haiminen received the M.Sc. degree from the University of Helsinki in 2004. She is currently a Graduate Student at the Department of Computer Science of University of Helsinki, and a Researcher at the Basic Research Unit of Helsinki Institute for Information Technology. Her research interests include algorithms, bioinformatics, and data mining. Aristides Gionis received the Ph.D. degree from Stanford University in 2003, and he is currently a Senior Researcher at the Basic Research Unit of Helsinki Institute for Information Technology. His research experience includes summer internship positions at Bell Labs, AT&T Labs, and Microsoft Research. His research areas are data mining, algorithms, and databases. Kari Laasonen received the M.Sc. degree in Theoretical Physics in 1995 from the University of Helsinki. He is currently a Graduate Student in Computer Science at the University of Helsinki and a Researcher at the Basic Research Unit of Helsinki Institute for Information Technology. His research is focused on algorithms and data analysis methods for pervasive computing.     

A framework for simulating real-time multi-agent systems

In this paper, we describe an implementation of use in demonstrating the effectiveness of architectures for real-time multi-agent systems. The implementation provides a simulation of a simplified RoboCup Search and Rescue environment, with unexpected events, and includes a simulator for both a real-time operating system and a CPU. We present experimental evidence to demonstrate the benefit of the implementation in the context of a particular hybrid architecture for multi-agent systems that allows certain agents to remain fully autonomous, while others are fully controlled by a coordinating agent. In addition, we discuss the value of the implementation for testing any models for the construction of real-time multi-agent systems and include a comparison to related work.

Konzeptuelle Modellierung von Geodiensten

Zusammenfassung  Navigationssysteme, ortsbezogene Suchdienste wie Google Maps, interaktive Augmented-Reality-Spiele, Handy-basierte FindMe-Dienste – diese wenige Beispiele zeigen bereits, wie direkt oder indirekt raumbezogene Dienste unser Alltagsleben immer mehr durchdringen. Wir beobachten, wie sich die Nutzung von Geodaten schrittweise vom pers?nlichen Desktop-Geoinformationssystem (GIS) über hausinternen Zugriff auf die Geodatenbank bis zum Webzugriff durch Clients und Servern unterschiedlicher Provenienz ausweitet (,,Web-GIS“). Klassische Aufgaben wie Kartenproduktion und Beauskunftung treten dabei gegenüber komplexen, situationsbezogenen Verknüpfungen von Geo- mit anderen Daten eher in den Hintergrund. Damit geht offensichtlich ein Paradigmenwechsel von der einfachen, passiven Geodatenbereitstellung via WWW zu funktional komplexeren Geodiensten einher. Sollen solche Mehrwertdienste offen und flexibel orchestrierbar sein, so müssen Geodaten systemübergreifend ad hoc abgefragt werden k?nnen. Unabdingbar sind dafür offene Standards, nicht nur auf der Ebene von Datenaustauschformaten, sondern auch bei den Zugriffsdiensten; diese Geoservice-Standardisierung leistet das Open GeoSpatial Consortium (OGC). Im vorliegenden Beitrag geben wir einen überblick über die Modellierung von Web-basierten Geodiensten auf Basis ausgew?hlter OGC-Standards. Modellierung bedeutet in diesem Kontext die Gestaltung von Funktionalit?t und Schnittstellen eines potenziell komplexen Dienstes auf Basis offener Standards und ihrer Basisdienste und -operationen. Diskutiert werden Standards für den Meta-, Vektor- und Rasterdatenzugriff sowie ein anwendungsorientierter Standard für Sensordaten.     

,,Location-based Services“ – Personalisierung mobiler Dienste durch Verortung

Zusammenfassung Im Zeitalter der Informationsgesellschaft, so wurde postuliert, spielten r?umliche Distanzen keine Rolle mehr und unsere r?umliche Mobilit?t n?hme ab. Die Mobilit?t in den letzten Jahren, speziell die Freizeitmobilit?t, hat hingegen zugenommen. Die Bereitstellung ortsbezogener Dienste – ,,Location-based Services“ – unterstützt und f?rdert dieses Verhalten.     

Efficient product sampling using hierarchical thresholding

We present an efficient method for importance sampling the product of multiple functions. Our algorithm computes a quick approximation of the product on the fly, based on hierarchical representations of the local maxima and averages of the individual terms. Samples are generated by exploiting the hierarchical properties of many low-discrepancy sequences, and thresholded against the estimated product. We evaluate direct illumination by sampling the triple product of environment map lighting, surface reflectance, and a visibility function estimated per pixel. Our results show considerable noise reduction compared to existing state-of-the-art methods using only the product of lighting and BRDF.     

Walrasian Equilibrium: Hardness,Approximations and Tractable Instances

We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004) showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria. In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still NP-hard for general graphs.     

Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

In this paper we consider the p-ary transitive reduction (TR _p ) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TR _p have been investigated before in different contexts; the best previous results are as follows:

Haptic two-finger contact with textiles

Real-time cloth simulation involves many computational challenges to be solved, particularly in the context of haptic applications, where high frame rates are necessary for obtaining a satisfying experience. In this paper, we present an interactive cloth simulation system that offers a compromise between a realistic physics-based simulation of fabrics and a haptic application meeting high requirements in terms of computation speed. Our system allows the user to interact with the fabric using two fingers. The required performance of the system is achieved by introducing an intermediate layer responsible for the simulation of the small part of the surface being in contact with the fingers. Additionally we separate the possible contact situations into different cases, each being individually handled by a specialised contact algorithm.