Learning hard chart constraints for efficient context-free parsing by Brian Roark – Oregon Health & Science University

Abstract: In this talk, I’ll present some recent work in learning hard constraints for cells within a context-free parsing chart, to reduce parsing time. Each cell in the chart represents one of the O(n^2) substrings of the input string, and characteristics of each substring can be used to decide how much work to do in the associated chart cell. I’ll discuss finite-state models for tagging chart constraints on words, including methods for bounding the worst-case complexity of the parsing pipeline to quadratic or sub-quadratic in the length of the string. Empirical results will be presented for English and Chinese, achieved by constraining various high accuracy parsers.

Finally, I will present a generalization of these finite-state approaches that performs a quadratic number of classifications (one for each substring) to produce further (finer) constraints on the amount of processing within each cell. This latter approach has the nice property of being trained on maximum likelihood parses, rather than reference parses, making for a straightforward method for tuning parsing efficiency to new tasks and domains.

Continue reading

Event details

  • When: 27th September 2011 13:00 - 14:00
  • Where: Cole 1.33
  • Series: CS Colloquia Series
  • Format: Colloquium

Is provenance logical? (James Cheney, University of Edinburgh)

Research on provenance in databases (or other settings) sometimes has an arbitrary flavor. Once we abandon the classical semantics of queries there is a large design space for alternative semantics that could provide some useful provenance information, but there is little guidance for how to explore this space or justify or compare different proposals. Topics from mathematical or philosophical logic could be used as a way of inspiring, justifying or comparing different approaches to provenance in databases. This talk will give a short tutorial on provenance in databases and present several topics in logic that may bear upon provenance techniques. These areas include nonclassical logics (e.g. relevance logic), algebraic logic (cylindric algebras), substructural logic (e.g. linear logic) and logics of knowledge, belief or causality.

Event details

  • When: 21st September 2011 13:00 - 14:00
  • Where: Cole 1.33a
  • Format: Seminar

Staff BBQ

Despite the weather conditions, the end of summer BBQ went ahead, on Friday.

It provided the perfect opportunity to welcome new members of staff and newly arrived PhD students. Congratulations also to Greg on submitting his thesis, and farewell to Angus who will be starting work in New York soon.

Exploring semantics in situation identification using context lattices by Dr.Juan Ye

Pervasive systems must offer an open, extensible, and evolving portfolio of services which integrate sensor data from a diverse range of sources. The core challenge is to provide appropriate and consistent adaptive behaviours for these services in the face of huge volumes of sensor data exhibiting varying degrees of precision, accuracy and dynamism. Situation identification is an enabling technology that resolves noisy sensor data and abstracts it into higher-level concepts that are interesting to applications. 

In this talk, I will provide a comprehensive analysis of the nature and characteristics of situations, discuss the complexities of situation identification, and introduce a novel situation identification technique called “context lattice”. The context lattice is built on a sound mathematical model, aiming to identify situations by systematically exploring the semantics of sensor data, domain knowledge, and situations in a pervasive computing system. I will present and discuss the evaluation results when applying this technique to recognising human activities in smart home environments. This talk will be concluded with challenging questions in the area of situation identification.
Continue reading

Event details

  • When: 3rd October 2011 14:00 - 15:00
  • Where: Cole 1.33
  • Series: CS Colloquia Series
  • Format: Colloquium

Software Freedom Day

Software Freedom Day is an annual event held by communities who are passionate about free and open-source software (FOSS).
The event programme includes a talk by Dr Markus Tauber from the School, titled Expectations, Requirements and Survival when
Starting with Linux.

Markus has provided a short overview of his talk for those interested in attending:
“The talk is about some work I did with friends from an Austrian CS
society as a spare time activity about 2 years ago. We
semi-scientifically looked into the relation of what experts expect
Linux newbies to do when starting with Linux and what newbies expect or
what they are happy to do. The talk is for both, newbies who want to get
some guidelines and for experts to give them an idea about the
expectations of newbies.”

Software Freedom Day will be held on Saturday 17th September from 10am until 5pm in Abertay’s Hannah Maclure Centre. The event is hosted by Abertay’s Open Society in partnership with TayLUG, Dundee’s local Linux user group.

Evening Degree Welcome Reception and Meet Your Tutor

The annual welcome reception for the new evening degree students took place last night in the Gateway brasserie. The familiar but extremely useful Meet Your Tutor session followed shortly afterwards. Tuesday evening sessions for IT begin next week.

Graduate Claire Gorgan was singled out for her achievements. Congratulations Claire.

Evening Degree Programme website

Measuring the Effectiveness of Abstract Data Visualisations

Speaker: Mark Shovman, University of Abertay, Dundee

Abstract:
In natural and social sciences, novel insights are often derived from visual analysis of data. But what principles underpin the extraction of meaningful content from these visualisations? Abstract data visualisation can be traced at least as far back as 1801; but with the increase in the quantity and complexity of data that require analysis, standard tools and techniques are no longer adequate for the task. The ubiquity of computing power enables novel visualisations that are rich, multimodal and interactive; but what is the most effective way to exploit this power to support analysis of large, complex data sets? Often, the lack of fundamental theory is pointed out as a central ‘missing link’ in the development and assessment of efficient novel visualisation tools and techniques.

In this talk, I will present some first steps towards the theory of visualisation comprehension, drawing heavily on existing research in natural scene perception and reading comprehension. The central inspiration is the Reverse Hierarchy Theory of perceptual organisation, which is a recent (2002) development of the near-centennial Laws of Gestalt. The proposed theory comes complete with a testing methodology (the ‘pop-out’ effect testing) that is based on our understanding of the cognitive processes involved in visualisation comprehension.

About Mark:
Mark Shovman is a SICSA Lecturer in Information Visualisation in the Institute of Arts, Media and Computer Games Technology in the University of Abertay Dundee. He is an interdisciplinary researcher, studying the perception and cognition aspects of information visualisations, computer games, and immersive virtual reality. His recent research projects include the application of dynamic 3D link-charts in Systems Biology; alleviating cyber-sickness in VR helmets; and immersive VR as an art medium. Mark was born in Tbilisi, Georgia, and lived in Jerusalem, Israel since 1990. He can be found on http://www.linkedin.com/pub/mark-shovman/3/a4b/849

Event details

  • When: 13th September 2011 14:00 - 15:00
  • Where: Cole 1.33a
  • Format: Seminar

Arrival of Tony’s Cichlids

After much anticipation and excitement, the School welcomes 12 new African Cichlids for the start of a new semester.

Robocode Session

Students undertaking the pre-sessional language course before entering our taught Masters programme, had the opportunity to try out their programming skills this afternoon, in a fun and enjoyable context using Java to write programmes that control robots.

Jan de Muijnck-Hughes and Lars Kotthoff led the session in the John Honey Building.

Virtual reconstruction of the Acropolis Basilica

The Basilica reconstruction was a collaborative project between the School of Classics and the School Computer Science. Research Blog

A reconstruction of St Andrews Cathedral has also taken place.
The reconstruction was a research topic for successful computer science and information technology MSc. dissertations in the summer of 2010 and 2011.
Technical support was available in regular laboratory sessions; in addition students had input from experts in the history and architecture of the cathedral and direct access to the physical site.
A key innovative aspect of this project was to situate the reconstruction within the immersive 3D virtual world OpenSim. This allows visitors to explore the reconstruction through the proxy of an avatar.