Department of Computer Science and Information Systems

Research Seminars

Academic Year 2011/12

The department hosts a programme of research seminars by invited speakers and departmental staff. The seminars are open to all. The following seminars will be taking place at the Department of Computer Science and Information Systems (DCSIS), Birkbeck College, or London Knowledge Lab (LKL), Birkbeck College and Institute of Education.

If you are interested in presenting a seminar please contact

Abstracts

Generic editor for primary textile structures

Dr Georges Gyory

Room 745, Malet Street - Wednesday 15th of February, 16:45 to 17:45

Primary textile structures have been described by different criteria, like by the number of (sets of) threads and draqwings as in Emery and by the topological properties of a repeating cell by Grishanov et al. For cataloging a large number of patterns Velasquez et al used a matrix containing the identifier of the thread (warp or weft) above the other in the weave. This was insufficient for textiles of several layers and its extension to a 3D tensor is complicated for the consistency check and insufficient to follow the threads in the presence of supplementary warps, even without crossed warps. With crossed and twined warps and wefts or non-woven structures (knitting, sprang etc) something more general is needed. As opposed to taking the warps and the wefts as objects like in the matrix representation, we propose a representation of the textile with the (top view) intersections of two threads as basic objects. The intersections have pointers to their four neighbouring intersections (along the threads) and a few more fields for position, which of the threads crosses above and the other end of the four links (crossing and link). We shall expose this representation, the necessary operations of the textile editor and the computing needed to determine the 2D coordinates of the crossings and the rendering of the textile. The editor will be demonstrated

[top of page]

Understanding Search Engine Queries

Professor Mark Levene

Room 745, Malet Street - Wednesday 1st of February, 16:45 to 17:45

Search engine technology has been steadily advancing in the past 10 years with the massive growth of the Internet and it seems that the major search engines have succeeded in providing an almost perfect information retrieval machine. Still search engines are relatively weak in understanding what users' intentions are. I will discuss two directions to improve this situation. One is involves the classification of queries into a manageable ontology that corresponds to the categories of web pages are usually searching for. The other involves named entity recognition in order to better understand the semantics of queries. I will also discuss domain-specific search, which is not catered for directly by web search engines. In particular I will describe a search engine we are building for historians researching Aramaic texts. (All this research is being done in collaboration with colleagues and research students.)

[top of page]

Towards More Expressive Ontology Languages: The Query Answering Problem

Dr Andreas Pieris

Room 745, Malet Street - Wednesday 18th of January, 16:45 to 17:45

Ontology-based data access is a powerful form of extending database technology, where a classical extensional database is enhanced by an ontology that generates new intensional knowledge which may contribute to answer a query. The ontological integrity constraints for generating this intensional knowledge can be specified in description logics such as DL-Lite. It was shown that these formalisms allow for very efficient query answering w.r.t. the data complexity. They are, however, too weak to express simple and useful integrity constraints that involve joins. To overcome this limitation, a recently introduced family of Datalog-based languages, called Datalog+/-, which is a new framework for tractable ontology querying, uses tuple-generating dependencies as rules. In fact, Datalog+/- extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability of query answering. In this talk we present recent results on Datalog+/. In particular, a novel paradigm, called stickiness, ensuring tractability of query answering is discussed.

This is a joint work with Andrea Cali and Georg Gottlob.

[top of page]

A brief glance at fixed-parameter algorithms and their applications

Dr Igor Razgon

Room 745, Malet Street - Wednesday 9th of November, 16:45 to 17:45

Fixed-parameter algorithms is a method of coping with NP-hardness. They use the fact that aprat from the input size $n$ computational problems are often accompanied with additional parameters (e.g. maximum allowed size of the output, a structural parameter of the underlying graph, etc.) The fixed parameter algorithms take time exponential in this parameter but polynomial in $n$. If the parameter is small compared to $n$ then the exponential part becomes a negligible multiplicative or even additive constant and we have an illusion of a polynomial time algorithm precisely solving an NP-hard optimization problem. Problems that can be solved this way are called fixed-parameter tractable (FPT) and the area studying fixed-parameter tractability of computational problems is called parameterized complexity.

This talk will consist of two parts. In the first part I will define the above notions in a little bit more formal fashion and present two simple yet quite elegant fixed-parameter algorithms with the purpose to convey the aesthetic beauty of the field. In the second part I will consider applications of the methodology of fixed-parameter computation to the following three fields: computational biology, efficient solving of large satisfiability instances, and knowledge compilation.

The main purpose of the talk is that after it the audience would feel that they have learned something new and interesting. Therefore the talk will be self-contained and (I hope) entertaining.

[top of page]

Darwinian Algorithms in the Brain

Dr Chrisantha Fernando, Department of Informatics, Sussex University

Room 745, Malet Street - Tuesday 28th June, 16:45 to 17:45

Can good ideas literally evolve in the brain overnight? It is known that copying of information takes place in the brain, for example, orientation selective receptive fields are copied from neurons in one part of visual cortex to adjacent neurons. For such entities to be true Darwinian replicators there must be covariance between their traits and their fitness as defined by Price. However, synaptic receptive fields are limited heredity replicators. We ask, is it possible for groups of receptive fields to be units of evolution? Gerald Edelman argued that neuronal groups could be Darwinian individuals, an argument with which Francis Crick strongly disagreed. Crick called Edelman's theory Neural Edelmanism rather than Neural Darwinism for it lacked the ability to copy functional traits that were dependent on patterns of synaptic connections from group to group. In other words, Edelman's neuronal groups are merely implementing competitive learning, rather than natural selection which requires transmission of information between individuals. Edelman's neuronal groups are neither units of evolution as defined by John Maynard-Smith nor Darwinian units as defined by Price. In an attempt to debug Edelman's theory and to take Francis Crick seriously, I describe a mechanism by which higher-order units of evolution could indeed replicate in the brain, using causal inference mediated by spike-time dependent plasticity (STDP) to copy microcircuits (patterns of synaptic connections) from one brain region to another. Furthermore, I propose a host of other higher-order neuronal entities that may plausibly exist and be interpreted as undergoing Darwinian evolution, such as paths of activity through a network. Such paths can be interpreted as embedded and overlapping units of evolution within a network. For the first time this allows the insights of population genetics to directly apply to cellular and systems neuroscience, creating a new field we could call Population Synaptics.

[top of page]

Context-dependent Feedback Prioritisation in Exploratory Learning through Analytic Hierarchy Process and Neural Networks

Dr Mihaela Cocea, Lecturer, School of Computing, University of Portsmouth

Room 745, Malet Street - Tuesday 7th June, 16:45 to 17:45

The open nature of exploratory learning leads to situations when feedback is needed to address several conceptual difficulties. Not all, however, can be addressed at the same time, as this would lead to cognitive overload and confuse the learner rather than help him/her. To this end, we propose a personalised context-dependent feedback prioritisation mechanism based on Analytic Hierarchy Process (AHP) and Neural Networks (NN). AHP is used to dene feedback prioritisation as a multi-criteria decision-making problem, while NN is used to model the relation between the criteria and the order in which the conceptual difficulties should be addressed. When used alone, AHP needs a large amount of data from experts to cover all possible combinations of the criteria, while the AHP-NN synergy leads to a general model that outputs results for any such combination. This work was developed and tested in an exploratory learning environment for mathematical generalisation called eXpresser.

[top of page]

Hierarchical Bayesian Models of Language and Text

Dr Yee Whye Teh, Lecturer, Gatsby Computational Neuroscience Unit, University College London

Room 745, Malet Street - Tuesday 24th May, 16:45 to 17:45

In this talk I will present a new approach to modelling sequence data called the sequence memoizer. As opposed to most other sequence models, our model does not make any Markovian assumptions. Instead, we use a hierarchical Bayesian approach which enforces sharing of statistical strength across the different parts of the model. To make computations with the model efficient, and to better model the power-law statistics often observed in sequence data, we use a Bayesian nonparametric prior called the Pitman-Yor process as building blocks in the hierarchical model. We show state-of-the-art results on language modelling and text compression. This is joint work with Frank Wood, Jan Gasthaus, Cedric Archambeau and Lancelot James.

[top of page]

Getting computers to play poker

Dr Troels Sørensen, Department of Computer Science, University of Warwick

Room 745, Malet Street - Tuesday 17th May, 16:45 to 17:45

Whenever game theory is applied to real world games, the models tend to be much larger than the toy examples that are traditionally studied. New techniques are constantly being developed to try to tackle large games. One of the benchmarks for evaluating such new techniques is poker. In this talk, I will present some of the techniques that have been applied recently to the game of Texas Hold'em poker. The talk will include an introduction to the game theory used as well as an introduction to poker.

[top of page]

Learning to Integrate Deduction and Search in Reasoning about QBFs

Dr Luca Pulina, University of Sassari, Italy

Room 745, Malet Street - Tuesday 10th May, 16:45 to 17:45 (Please notice, all seminars This Term are on Tuesdays and not Wednesday (unless stated otherwise)).

We study the problem of integrating deduction and search with the aid of machine learning techniques to yield practically efficient decision procedures for quantified Boolean formulas (QBFs). We show that effective on-line policies can be learned from the observed performances of deduction and search on representative sets of formulas. Such policies can be leveraged to switch between deduction and search during the solving process. We provide empirical evidence that learned policies perform better than either deduction and search, even when the latter are combined using hand-made policies based on previous works. The fact that even with a proof-of-concept implementation, our approach is competitive with sophisticated state-of-the-art QBF solvers shows the potential of machine learning techniques in the integration of different reasoning methods.

[top of page]

Modelling a choreography as a composition of partial descriptions

Ashley McNeile

Room 745, Malet Street  - Tuesday, 3rd May, 16:45 to 17:45 (Please notice, the seminar is on Tuesday and not Wednesday)

Multiparty e-commerce collaborations and cross-organizational workflow applications are increasingly attractive given the universal connectivity provided by the Internet. Such applications are inherently concurrent and non-deterministic and, as always with such applications, ensuring that implemented designs will behave correctly under all circumstances is a significant challenge.

The emerging technique for designing extended collaborations is to use a "choreography": a global description of the possible sequencing of message exchange between the participants. The idea is that, once a choreography has been designed, designs for the individual participants can be extracted from it - a technique called "projection". If the participants then interact, each according to its own projected behaviour, the emergent behaviour of the collaboration as a whole should exactly follow the original choreography. If this works successfully the choreography is said to be "realizable". The key question which research into choreography seeks to answer is this: What conditions does a choreography need to obey in order to guarantee that it is realizable? In general, determining realizability of a choreography is a non-trivial question, particularly when the collaboration uses asynchronous messaging and it is possible for different participants to send messages simultaneously.

I will describe my work in this area, which centres on the idea of modelling a choreography as a composition of partial descriptions using ideas from Process Algebra. This has potential to simplify realizability analysis, as it turns out that composition preserves realizability.

This talk does not assume any prior knowledge of choreography techniques or Process Algebras.

[top of page]

Mining and visualising information from RSS feeds

Martin O'Shea 

Room 745, Malet Street. - Wednesday 23rd of March, 17:00 (Please notice, the seminar is formally starting a bit later than usual).

This seminar is going to have a special format, consisting of two short presentations by two of our PhD students. Each presentation will last approximately 10 minutes and will be followed by 10 minutes of questions.

[top of page]

Analyzing User Intent in Community-based Question Answering Services

Long Chen

Room 745, Malet Street. - Wednesday 23rd of March, 17:45.

See above.

[top of page]

A Story of Logic and OWL

Roman Kontchakov, Department of Computer Science and Information Systems, Birkbeck, University of London

Room 745, Malet Street. - Wednesday 16th of March, 16:45 to 17:45 (There will be cookies and coffee from 16:35, so it is recommended to arrive a bit earlier).

In this talk we look at the classical automated reasoning problem---given a theory with a set of ground atoms and a formula, decide whether the formula follows from the theory. We argue that this problem resurfaces as the main reasoning problem in WWW. We consider, in particular, ontology-based data access (OBDA) and ontology maintenance. In a typical OBDA scenario, the theory is an `ontology' providing a user-oriented view of raw data (ground atoms), and the formula is a query. The latest W3C recommendation for the Web Ontology Language identifies a specialised profile, OWL 2 QL, tailored for ODBA. In this talk we analyse advantages and limitations of the two OBDA paradigms, the query rewriting and the combined approaches, and the ontology languages they can work with (OWL 2 QL and OWL 2 EL). We also demonstrate how the classical notion of conservative extensions can be adapted (we say ontologies are inseparable if the same formulas follow from them) and used in formalising ontology versioning, re-use and module extraction.

[top of page]

Querying the Deep Web

Dr. Andrea Cali, Department of Computer Science and Information Systems, Birkbeck, University of London

Room 745, Malet Street building - Wednesday 9 March 2011 at 16.45

The term Deep Web refers to the data content that is created dynamically as the result of a specific search on the Web. In this respect, such content resides outside web pages, and is only accessible through interaction with the web site - typically via HTML forms. Usually, data sources accessible through web forms are modeled by relations that require certain fields to be selected - i.e., some fields in the form need to be filled in. These requirements are commonly referred to as access limitations in that access to data can only take place according to given patterns. In such context, computing the answer to a user query cannot be done as in a traditional database; instead, a query plan is needed that provides the best answer possible while complying with the access limitations. In this talk, we illustrate the semantics of answers to queries over data sources under access limitations and present techniques for query answering in this context. We show different algorithms to optimize query answering both at the time of the query plan generation and at the time of the execution of the query plan.

[top of page]

Some Recent Fundamental Approaches to Data Quality Assessment and Cleaning

Prof. Leopoldo Bertossii Carleton University, Ottawa, Canada, Department of Computer Science and Information Systems, Birkbeck, University of London

Room 745, Malet Street building - Wednesday 23 February 2011 at 16.45

Data cleaning techniques have largely been rather ad hoc, vertical, and rigid activities. We present some recent developments in the area that are more declarative and generic. More specifically, we consider on-the-fly quality query answering wrt integrity constraints, and matching dependencies for entity resolution. We also propose a model of contexts for data quality assessment.

[top of page]

Matroid-Secretary-Problem

Oded Lachish, Department of Computer Science and Information Systems, Birkbeck, University of London

Room 745, Malet Street building - Wednesday 16 February 2011 at 16.45

Imagine that you want to hire a single secretary. For this goal you interview fifty candidates. Ideally you would like to decide whom to hire after the interviews. However due to managerial constraints, after each interview you must make an irrevocable decision whether to hire or not. How can the probability of hiring an optimal candidate be maximized?

The scenario just described is an illustration of the classical-secretary-problem, which was introduced in the sixties. Although the problem has long been solved, many of its generalizations are still open and receive significant attention. We will discuss on-going research regarding a specific generalization called the Matroid-Secretary-Problem.There the candidates are elements of a Matroid. Like in the classical case the decision whether to hire is irrevocable. Yet unlike the classical problem it is possible to hire more than one candidate, as long as all the hired candidates form an independent set. The goal is to maximize the expected value of the candidates hired.

[top of page]

Evolutionary document classification for content-based recommender systems

John Pagonis, Pragmaticomm Limited

Room 403, Malet Street building - Wednesday 3 November 2010 at 16.30

During this session John will give background on information filtering with genetic algorithms, recommender systems and present a GA-based document classifier designed for use by a content-based recommender system that operates with implicit feedback only. He will explain why GA-based classifiers have been in recent years neglected in content-based recommender systems and indicate what is their true value in classification and recommendation.

[top of page]

Quick links

Seminars Menu

• Seminars Home
• London Knowledge Lab Seminars

Previous Seminars

Select... Year 2009/10 Year 2008/9 Summer 2008 Spring 2008 Autumn 2007 Summer 2007 Spring 2007 Autumn 2006 Summer 2006 Spring 2006 Autumn 2005 Summer 2005 Spring 2005 Autumn 2004 Summer 2004 Spring 2004 Autumn 2003 Summer 2003 Spring 2003 Autumn 2002 Summer 2002 Spring 2002 Autumn 2001 Summer 2001 Spring 2001 Autumn 2000 Summer 2000 Spring 2000 Autumn 1999 Go