This thesis introduces analysis tools for improving the current state of the art of heuristics for the Maximum Clique (MC) problem. The analysis focusses on algorithmic building blocks, on their contribution in solving hard instances of the MC problem, and on the development of new tools for the visualisation of search landscapes. As a result of the analysis on the algorithmic building blocks, we re-engineer an existing Reactive Local Search heuristic for the Maximum Clique (RLS-MC. We propose implementation and algorithmic improvements over the original RLS-MC aimed at faster restarts and greater diversification. The newly designed algorithm (RLS-LTM) is one order of magnitude faster than the original RLS-MC on some benchmark instances; but the proposed algorithmic changes impact also on the dynamically adjusted tabu tenure, which grows wildly on some hard instances. A more in depth analysis of the search dynamics of RLS-MC and RLS-LTM reveals the reasons behind the tabu tenure explosion and sheds some new light on the reactive mechanism. We design and implement RLS-fast which cures the issues with the tabu tenure explosion in RLS-LTM while retaining the performance improvement over RLS-MC. Moreover, building on the knowledge gained from the analysis, we propose a new hyper-heuristic which defines the new state of the art, and a novel supervised clustering technique based on a clique-finding component.

Visual tracking under non-uniform illumination is challenging as the appearance of a target may change across the scene, while it is being tracked. To account for this, a built-in color correction can be used to transform local tracking observations into a globally normalized color space, hereby compensating for the uneven illumination affecting the tracking. In a static environment a parametric model of such correction can be calibrated to the scene illumination off-line, by using a color chart, but in practical applications this may not be feasible. In this research we present methods to obtain such correction without requiring a calibration pattern be placed in the environment, instead, we use observations of people moving around in the scene as illumination probes naturally collected with a detector. The learning is always carried out in an unsupervised manner with different methods, and in the final part of the of this research we proposed a data association step to group detections into tracklets, and the color correction parameters are then found by optimizing appearance similarity within tracklets. Reported experiments for each method show that our methods are able to effectively learn the color correction with multiple people to achieve robust tracking in unevenly illuminated scene.

The study of human interaction dynamics has been at the center for multiple research disciplines in- cluding computer and social sciences, conversational analysis and psychology, for over decades. Recent interest has been shown with the aim of designing computational models to improve human-machine interaction system as well as support humans in their decision-making process. Turn-taking is one of the key aspects of conversational dynamics in dyadic conversations and is an integral part of human- human, and human-machine interaction systems. It is used for discourse organization of a conversation by means of explicit phrasing, intonation, and pausing, and it involves intricate timing. In verbal (e.g., telephone) conversation, the turn transitions are facilitated by inter- and intra- speaker silences and over- laps. In early research of turn-taking in the speech community, the studies include durational aspects of turns, cues for turn yielding intention and lastly designing turn transition modeling for spoken dia- log agents. Compared to the studies of turn transitions very few works have been done for classifying overlap discourse, especially the competitive act of overlaps and function of silences. Given the limitations of the current state-of-the-art, this dissertation focuses on two aspects of con- versational dynamics: 1) design automated computational models for analyzing turn-taking behavior in a dyadic conversation, 2) predict the outcome of the conversations, i.e., observed user satisfaction, using turn-taking descriptors, and later these two aspects are used to design a conversational profile for each speaker using turn-taking behavior and the outcome of the conversations. The analysis, experiments, and evaluation has been done on a large dataset of Italian call-center spoken conversations where customers and agents are engaged in real problem-solving tasks. Towards solving our research goal, the challenges include automatically segmenting and aligning speakers’ channel from the speech signal, identifying and labeling the turn-types and its functional aspects. The task becomes more challenging due to the presence of overlapping speech. To model turn- taking behavior, the intension behind these overlapping turns needed to be considered. However, among all, the most critical question is how to model observed user satisfaction in a dyadic conversation and what properties of turn-taking behavior can be used to represent and predict the outcome. Thus, the computational models for analyzing turn-taking dynamics, in this dissertation includes au- tomatic segmenting and labeling turn types, categorization of competitive vs non-competitive overlaps, silences (e.g., lapse, pauses) and functions of turns in terms of dialog acts. The novel contributions of the work presented here are to 1. design of a fully automated turn segmentation and labeling (e.g., agent vs customer’s turn, lapse within the speaker, and overlap) system. 2. the design of annotation guidelines for segmenting and annotating the speech overlaps with the competitive and non-competitive labels. 3. demonstrate how different channels of information such as acoustic, linguistic, and psycholin- guistic feature sets perform in the classification of competitive vs non-competitive overlaps. 4. study the role of speakers and context (i.e., agents’ and customers’ speech) for conveying the information of competitiveness for each individual feature set and their combinations. 5. investigate the function of long silences towards the information flow in a dyadic conversation. The extracted turn-taking cues is then used to automatically predict the outcome of the conversation, which is modeled from continuous manifestations of emotion. The contributions include 1. modeling the state of the observed user satisfaction in terms of the final emotional manifestation of the customer (i.e., user). 2. analysis and modeling turn-taking properties to display how each turn type influence the user satisfaction. 3. study of how turn-taking behavior changes within each emotional state. Based on the studies conducted in this work, it is demonstrated that turn-taking behavior, specially competitiveness of overlaps, is more than just an organizational tool in daily human interactions. It represents the beneficial information and contains the power to predict the outcome of the conversation in terms of satisfaction vs not-satisfaction. Combining the turn-taking behavior and the outcome of the conversation, the final and resultant goal is to design a conversational profile for each speaker. Such profiled information not only facilitate domain experts but also would be useful to the call center agent in real time. These systems are fully automated and no human intervention is required. The findings are po- tentially relevant to the research of overlapping speech and automatic analysis of human-human and human-machine interactions.

Adaptation methods for phrase-based statistical Machine Translation (MT) have been explored in the literature under different paradigms, such as domain adaptation and topic adaptation, and most of the times in rather ideal experimental set-ups. We address this subject in three real-life industrial use cases, in which MT has to quickly adapt in accordance with specific operating conditions. In particular, we explore domain adaptation when no in-domain parallel data are available, which is a typical use case of MT service providers. Then, we investigate topic adaptation for the translation of short highly ambiguous item titles in an e-commerce setting. Finally, we consider the Computer Assisted Translation (CAT) scenario, in which MT interacts with a human translator by providing them with translation drafts and by adapting from their post-editions. In this scenario, we investigate online adaptation from human post-editions, respectively, in a single-user setting and in a multi-user setting, in which multiple translators are working on different parts of the same document. In addition, for the single-user case we also discuss the optimisation of the hyper-parameters of the employed online adaptation method.

This thesis contributes to the area of Enterprise Modeling by proposing the SIENA modeling framework for the representation of strategic enterprise architectures and automated reasoning with such models. In this work, we provide the SIENA language that provides abstractions for capturing enterprise’s motivational elements (i.e. goals of different shades like mission, vision, strategic, tactical and operational goals) and their connections with behavioral elements (i.e., operations, business processes, commitments and activities) through which they are operationalized. The SIENA language also introduces the distinguishing feature of dimensional refinement operators, a new operator that can be used for the refinement of strategic goals in terms of time, location and products/services dimensions. SIENA language is also accompanied by modeling guidelines for the construction of its models. Besides the SIENA language, we also propose a business process language called Azzurra which is founded on the primitives of commitments and protocols for the representation of business processes. The representation of business processes in terms of commitments is a distinguishing feature of our approach. Further, our framework also supports the design of business processes specified using the Azzurra language from SIENA operational goals. As one of the greatest advantages of conducting enterprise modeling is to gain the ability to perform automated analysis using enterprise models, we also propose a formal reasoning technique for the automated generation of strategic plans subject to constraints to satisfy enterprise’s strategic goals. The overall approach is validated by means of a number of different activities, including self-evaluation, experimentation and in-depth case studies with novices.

Sensory information in language enables us to share perceptual experiences and create a common understanding of the world around us. Especially in the creative language, which reveals itself in many forms, such as figurative language, persuasive or effective language, sensory factors impose a leveraging effect into semantic meaning by its expressive power. Although in the last decade, the studies focusing on the perceptual aspects of language have been thriving, automatic creative language analysis still suffers from the lack of perceptual grounding with its characteristics of vivid, non-literal and complex semantics. In this thesis, we propose the exploitation of the association between human senses and words as an external device to improve the computational linguistic models focusing on creative language. First, we present that sensory information reserved in the word meaning is obtainable by a distributional strategy over language. Second, we show that properly encoded sensory cues can enhance the automatic identification of figurative language. Finally, we argue that the exploitation of sensory information residing in linguistic modality in combination with the information coming from the perceptual modalities reinforces the computational assessment of multimodal creativity. We present a large scale sensory lexicon generation approach followed by its utilization in two main computational creativity experiments to confirm our arguments: 1) phrase-level and word-level metaphor identification in existing metaphor corpora; 2) creativity appreciation assessment in multimodal advertising prints incorporating the linguistic and visual modalities. The findings of the experiments show that sensory information is an invaluable indication of the creative aspect of the language and makes a significant contribution to the state of the art creative language analysis systems.

Machine Learning Methods for Urban Computing World population is increasingly moving from rural areas to urban centers, making large cities densely populated. In urban areas, there is greater access to work, a wide variety of options for education and training, ease of transport and the abundance of attractive places within a few kilometers. Across huge cities, people tend to move more and have to do it faster than in the past. On the other hand, heavy traffic (e.g., traffic jams), overbuilding and changes in the urban lifestyle can cause several new problems such as noise, atmospheric pollution (i.e., smog) and severe traffic congestions. However, the rise of novel data sources and machine learning techniques can help to tackle such problems and improve the quality of life of citizens. Indeed, in a smart city environment, the huge amount of data generated daily can be captured by sensors, actuators, and mobile devices. It goes without saying that using such data opens the door to several applications, including forecasting of urban displacements, land use classification and event detection in an urban environment. Motived by these opportunities, Urban Computing (UC) leverages on heterogeneous data sources and applies machine learning techniques to tackle these big challenges that modern cities are facing. In this perspective, one of the core questions when designing UC systems is how to enable models to learn from different urban data sources and thus how to represent urban spaces. The mainstream approach is to represent input objects as feature vectors that encode several aspects of the urban environment such as the presence of people, density of urban activities, and mobility flows. However, this tedious approach of manually feature engineering can be extremely complex, time-consuming and domain-specific dependent. Additionally, it can become even more complex when aggregating multiple geographical data sources such as point-of- interests, administrative boundaries, and mobility data. A valid alternative to feature-based methods is using kernels, which are non-linear functions that map input examples into some high dimensional space allowing for learning more powerful discriminative decision functions. Given a representation of the input object, kernels map it into some high-dimensional space where implicitly a large number of features are generated, allowing for learning robust discriminative functions. In this way the effort for the feature engineering pro- cess can be greatly reduced. Machine Learning Methods for Urban Computing Kernel methods have been widely applied in Natural Language Processing on tasks such as question answering, semantic role labeling and even for solving linguistic games. Taking inspiration from these successful cases, in this thesis we adapt kernel learning for solving novel tasks in UC. First, we focus on the problem of aggregating multiple urban data sources to provide datasets that fuse knowledge from a wide variety of data sources. Next, we focus on the problem of designing an input structure that is representative of urban space. In particular, we propose to model urban areas with tree structures that are fed to tree kernel functions for automatically generate expressive features. We propose several urban space representations that demonstrated to be very effecting in solving novel urban computing tasks such as land use classification and next location prediction in human mobility. Then, by applying a mining algorithm we enabled the interpretation of urban zones, providing help in the difficult problem of understanding the high-level urban characteristics of a city. In fact, our mined substructures provide help in identifying the different urban nature of cities. Finally, we explore the application of machine learning models to novel urban data sources by solving solve innovative tasks such as predicting the future presence of influenza-like symptoms looking at the people’s mobility behaviors.

Most of the world countries are challenged with a large ageing population who spend most of their time at home and are mostly sedentary (8.5 hours per day as of today). Sedentary behavior and physical inactivity affect the social, physical and mental states of people leading to social isolation and physical declines and hence an ideal candidate for chronic and degenerative diseases. To maintain an active aging process (healthy state of physical, mental and social wellbeing), regular and daily exercising is necessary. However, many older adults do not maintain regular exercising due to poor health, lack of company, lack of motivation, lack of transportation and suitable outdoor facilities. In this context, home based physical exercises can help people maintain their physical activity and ICT can act as a key player and facilitator by providing interactive training applications (through desktops and mobile devices), self-monitoring (using activity trackers and wearables) and automated coaching (using rule-based systems or remote assistance). Yet, for many people and, in particular, the sedentary older population at home; even with the existence of the technology, there is not enough motivation to maintain a regular exercising routine. Thus, this thesis aims to investigate the IT-mediated persuasive strategies that help independent-living older adults at home to maintain a regular exercising lifestyle. In particular, this research examines the effect of social inclusion and group exercising on the motivation of trainees at home to adhere to the training program which has proven to be effective.

Business process modeling refers to the design of business process models, using business processes languages, to orchestrate the work executed by employees, their interaction with external entities, and work items that are necessary to achieve a predefined goal. Model-driven development allows people, generally called modelers, to design also sophisticated application logic using high-level abstractions. Process modeling is typically connected with business, hence, existing process languages focus principally on the support and orchestration of activities executed by employees, or by external entities like web services. However, there is a wide range of other application logics that are process-driven and that can benefit from high-level abstractions to model low-level details. Our initial research focuses on distributed UIs, which are a distributed type of actors, and then particularly concentrated on Wireless Sensor Networks (WSNs) and crowdsourcing, which are distributed and also autonomous types of actors (they can execute a part of an application logic in an autonomous and isolated fashion). Developing applications in these areas requires a deep knowledge of the field and a non-trivial programming effort; domain experts have to code an orchestrate the logic executed by these actors. Since these applications are highly process-driven, domain experts could take advantage of high-level, process-oriented modeling conventions to design the internal logic of these kinds of applications. However, the intrinsic complexity of these domains and the current state of the art of modeling paradigms make the design and execution of processes for these new actors challenging. In this dissertation we analyze, design, and present modeling formalism and systems for managing processes in these contexts. We tackle the challenges of the three areas with an approach that analyzes and extends existing process modeling languages, to enable the design of the processes, and with an architecture, similar for the three focuses, to support the development and execution of processes. Starting from our initial work on the orchestration of distributed UIs, for which we present a modeling language with a set of modeling constructs specific for the UIs, we then present our contribution to WSNs and crowdsourcing domains, which are: a modeling convention for the development of WSN applications, with high-level modeling constructs that abstract the low-level details of the networks; and a modeling paradigm to design processes that are partially executed by a crowd of people. These languages are all equipped with prototypes that contain a modeling tool to design processes and a runtime environment to support the execution. The impact of this work is not only to the domains we focused on but also to the business process domain as we demonstrate how a process modeling is a flexible and suitable formalism to design processes with very diverging, domain-specific requirements.

Tree kernels and neural networks are powerful machine learning models for extracting patterns from data. Tree kernels compute the similarity between two tree-structured text representations that may incorporate syntactic and semantic information. Neural networks map words into informative embeddings, and learn complex non-linear decision functions by applying a number of transformations to the input. Joining the two approaches is an exciting research direction. In this work, which is set in a Question Answering (QA) context, we apply the individual models to classification and ranking tasks. More importantly, we explore the intersection of tree kernels and neural networks, with the goal of developing more accurate models. Initially, we focus on a challenging QA task, the resolution of Crossword Puzzles (CPs), and improve an automatic CP solver by tackling two problems: (i) answering crossword clues by reranking snippets from a search engine, and (ii) clue paraphrasing, which is extremely useful for finding clues with the same answers. We apply reranking models based on syntactic structures, and therefore tree kernels, to increase the accuracy and speed of the solver. In addition, we design and evaluate a composite kernel that combines a kernel over structures, and a kernel on neural network induced representations. Going beyond the neural feature vector approach, we develop a structural kernel that exploits a deep siamese network for evaluating the similarity between words. We assess the resulting model on two classification tasks: question classification and sentiment analysis. To conclude, we study QA models that establish links between question and candidate answer passages using semantic information. First, we present our tree kernel model for answer sentence selection, which captures relations between important question words and entities in the answer. Then, we build a neural network model that can be trained to extract semantic features from text, and eventually establish links between text pairs. We show that such network is able to better model the notion of question-answer relatedness on several QA datasets, compared to the tree kernel model.