AI Applications

Resource allocation

Resource allocation is the problem of assigning a set of resources to tasks which need to be carried out. This assignment must respect two constraints: the resources must be capable of executing the task, and they must be available during the time that the task must be executed. Resource allocation is a fundamental problem with many practical applications. At the LIA, we have developed techniques for decomposing the problem into subparts which can be solved independently.Distributed resource allocation is a special case of resource allocation, where the task of allocating the resources is distributed among a set of agents. In this direction, we have experimented with distributed resource allocation in a sensor network, and proposed some improvements to existing techniques.Current projects:

  • Distributed Service Placements in a Peer-to-Peer Network: in this setting we have considered problems where a set of self-interested agents want to each place in-network processing operators on a set of servers. Each agent has its own private preferences about different combinations of operator placements. Each server in the overlay network is able to perform some set of operators, and servers differ in their network and computational characteristics. The task is to provide a distributed algorithm that finds the globally optimal allocation of operators to servers, such that the overall utility of all users is maximized. For more details, please refer to [Faltings et al., 2006].
  • Distributed Combinatorial Auctions: Combinatorial Auctions (CAs) are a popular means to allocate resources to multiple agents. In Cas, bidders can bid on bundles of goods (as opposed to bidding on single goods). Combinatorial bids can model both complementarity and substitutability among the goods, i.e. when the valuation for the bundle is more, respectively less than the sum of the valuations for individual items. In our setting the agents are distributed (geographically or logically), and form a problem graph in which neighbors are agents with whom their bids overlap. The objective is to find the feasible solution (i.e. declare bids as winning or losing such that no two winning bids share a good) that maximizes the total utility of the agents. Combinatorial auctions can be adopted as a stylized model of distributed allocation problems such as airport slot allocation and wireless spectrum allocation as discussed in the Introduction. In our DCOP model, each agent holds a variable for each one of its bids, with two possible values: 0 when the bid is rejected, and 1 when the bid is accepted. Any pair of overlapping bids (bids that share at least one good) is connected by a “at most one” constraint that specifies that they cannot be both accepted. When multiple bids are submitted by an agent then they can be connected by additional constraints to capture the bid logic, for instance exclusive-or constraints if only one bid can be accepted.

Past projects:

Electronic Commerce

Electronic commerce presents numerous challenges for intelligent systems. Many of these involve the interactions of customers with merchants through the internet, in partiuclar searching for items and obtaining recommendations. We have worked on the example-critiquing approach to preference-based search and developed commercial applications through the startup company Iconomic Systems SA. For recommender systems, we have developed the new approach of ontology filtering. It solves the cold-start problem of having to require new users to provide a large number or ratings before meaningful recommendations can be made. Ontology filtering is commercialized through the startup companyPrediggo. Another application related to e-commerce is monitoring seller behavior through reputation systems. As part of a project involving several groups ( Computational Reputation Mechanisms for Enabling Peer-To-Peer Commerce in Decentralized Networks.), we have developed various techniques for obtaining truthful feedback in reputation systems. Based on these, we have developed a novel method for >Reliable Quality of Service Monitoring Based on Client Feedback that can be used for example for service-level agreements related to electronic services.

Knowledge Extraction & Text Mining

The current boom in information technology produced an enormous amount of data and information available. However, the retrieval of needed documents is often difficult and media such as the Internet do not provide sophisticated structuring and organization to face the task of finding relevant documents in a particular situation. The automatic detection of similarity between texts and the determination of relevance of documents relative to a certain query is therefore essential to the efficient use of the humungous amount of data available. At the LIA, research into automatic structuring of documents and probabilistic parsing as undertaken in order to improve current retrieval and similarity approaches.Current projects:Past projects:

Natural Language Processing in Speech Recognition

Speech recognition is a key issue in developing intuitive and well accepted user interfaces. The task is, however, very difficult, since real time restrictions limit the effort which can be spent on computation. At the LIA we consider combining state-of-the-art acoustic models with advanced linguistic models in order to improve the performance of speech understanding systems in maintaining dialogs.Current projects:Past Projects:

  • INSPECT – Integration of acoustic and advanced linguistic models into speech understanding systems,
  • INFOVOX Project: Interactive Voice Servers for Advanced Computer Telephony Applications
  • ISIS – Design of Advanced Vocal Information Servers