Finding the way in known and unknown city environments is a task that all pedestrians carry out regularly. Current technology allows the use of smart devices as aids that can give automatic verbal route directions on the basis of the pedestrian's current position. Many such systems only give route directions, but are unable to interact with the user to answer clarifications or understand other verbal input. Furthermore, they rely mainly on conveying the quantitative information that can be derived directly from geographic map representations: 'In 300 meters, turn into High Street'. However, humans are reasoning about space predominantly in a qualitative manner, and it is less cognitively demanding for them to understand route directions that express such qualitative information, such as 'At the church, turn left' or 'You will see a café'. This thesis addresses three challenges that an interactive wayfinding system faces in the context of natural language generation and understanding: in a given situation, it must decide on whether it is appropriate to give an instruction based on a relative direction, it must be able to select salient landmarks, and it must be able to resolve the user's references to objects. In order to address these challenges, this thesis takes a data-driven approach: data was collected in a large-scale city environment to derive decision-making models from pedestrians' behavior. As a representation for the geographical environment, all studies use the crowd-sourced Openstreetmap database. The thesis presents methodologies on how the geographical and language data can be utilized to derive models that can be incorporated into an automatic route direction system. / <p>QC 20160516</p>

Reference resolution is a major component of any natural language system. In the past 30 years significant progress has been made in coreference resolution. However, there is more anaphora in texts than coreference. I present a computational treatment of other-anaphora, i.e., referential noun phrases (NPs) with non-pronominal heads modi- fied by “other” or “another”: [. . . ] the move is designed to more accurately reflect the value of products and to put steel on more equal footing with other commodities. Such NPs are anaphoric (i.e., they cannot be interpreted in isolation), with an antecedent that may occur in the previous discourse or the speaker’s and hearer’s mutual knowledge. For instance, in the example above, the NP “other commodities” refers to a set of commodities excluding steel, and it can be paraphrased as “commodities other than steel”. Resolving such cases requires first identifying the correct antecedent(s) of the other-anaphors. This task is the major focus of this dissertation. Specifically, the dissertation achieves two goals. First, it describes a procedure by which antecedents of other-anaphors can be found, including constraints and preferences which narrow down the search. Second, it presents several symbolic, machine learning and hybrid resolution algorithms designed specifically for other-anaphora. All the algorithms have been implemented and tested on a corpus of examples from the Wall Street Journal. The major results of this research are the following: 1. Grammatical salience plays a lesser role in resolving other-anaphors than in resolving pronominal anaphora. Algorithms that solely rely on grammatical features achieved worse results than algorithms that used semantic features as well. 2. Semantic knowledge (such as “steel is a commodity”) is crucial in resolving other-anaphors. Algorithms that operate solely on semantic features outperformed those that operate on grammatical knowledge. 3. The quality and relevance of the semantic knowledge base is important to success. WordNet proved insufficient as a source of semantic information for resolving other-anaphora. Algorithms that use the Web as a knowledge base achieved better performance than those using WordNet, because the Web contains domain specific and general world knowledge which is not available from WordNet. 4. But semantic information by itself is not sufficient to resolve other-anaphors, as it seems to overgenerate, leading to many false positives. 5. Although semantic information is more useful than grammatical information, only integration of semantic and grammatical knowledge sources can handle the full range of phenomena. The best results were obtained from a combination of semantic and grammatical resources. 6. A probabilistic framework is best at handling the full spectrum of features, both because it does not require commitment as to the order in which the features should be applied, and because it allows features to be treated as preferences, rather than as absolute constraints. 7. A full resolution procedure for other-anaphora requires both a probabilistic model and a set of informed heuristics and back-off procedures. Such a hybrid system achieved the best results so far on other-anaphora.

In everyday conversation, we frequently express relationships between two entities by using attributive possessive NPs. Structurally, these consist of a possessor referent, a possessum nominal and a possessive marker which explicates said relationship. For example, if I want to enquire about a house owned by your friend Mary which you are currently decorating, I might feasibly say "How are you getting on with Mary’s house?". My utterance of the pre-nominal possessive NP Mary’s house allows you to represent a specific referent, ensuring that we mentally converge on the same house and are able to talk about it. This study investigates English pre-nominal possessive NPs from a pragmatic point of view. It does so with the aim of providing a cognitively plausible description of their interpretationwhich simultaneously serves to understand how they function as referring expressions in communication. In particular, I discuss some of the intricacies they pose to interlocutors when itcomes to their referential interpretation. One of these concerns the fact that pre-nominal possessives are semantically compatible with numerous different interpretations, yet reference aparticular possessive relation in concrete communicative situations. Thus, given that the Englishlanguage, quite in contrast to the majority of the world’s languages, does not render thepossessive relation that holds between two entities morphosyntactically explicit, the interpretation of pre-nominal possessive NPs falls entirely within the remit of a pragmatic theory. This should explain how Mary’s house, which is compatible with interpretations such asthe house that Mary is letting, the house that Mary wishes to buy, as well as various others,comes to denote the house that Mary owns in a communicative situation like the above. Fullyinterpreting this NP, as Peters & Westerståhl (2013) suggest, involves knowing what possibleinterpretations it gives rise to, selecting the most salient one to the detriment of any others, and, finally, representing a determinate referent denoted by the NP as a whole. While the first aspect has received much attention (e.g. Barker, 1995; Vikner & Jensen, 2002), the other two have been considered by only few researchers. This study represents the first holistic account of possessive interpretations which combinesall three questions to explain the various facets of their pragmatics. On the theoretical level, itsuggests that the currently dominant stance (advocated by Vikner & Jensen, 2002), accordingto which it is the lexical semantic content of the possessum nominal which largely exhausts theinterpretation process, is in need of rethinking. Contrary to existing insights, I attribute a greaterrole to context and pragmatic reasoning both at the level of possible and at the level of salientinterpretations. On the methodological level, the study is multimethodological in its approach,complementing theoretical argument by means of a psycholinguistic production study and alarge-scale corpus study. In this respect, the present study paves the way for a description of pragmatic aspects of theEnglish grammar which have hitherto been explained in terms of more descriptive possessivetaxonomies, including ones delineating alienable vs. inalienable (e.g. Nikolaeva & Spencer,2013), prototypical vs. non-prototypical (e.g. Langacker, 1995; Rosenbach, 2002) and lexicalvs. pragmatic interpretations (Vikner & Jensen, 2002). Ultimately, I suggest that construing referential interpretation as an addressee-dependent search for relevance (e.g. Sperber & Wilson, 1986/1995) largely obviates the need for taxonomies of this kind at the descriptive level.

Imagine that you are in the new city and want to explore it. Trying to navigate with maps leads to the unnecessary confusion about street names and prevents you from a enjoying a wonderful walk. The dialogue system that could navigate you from by means of a simple conversation using salient landmarks in your immediate vicinity would be much more helpful! Developing such dialogue system is non-trivial and requires solving a lot of complicated tasks. One of such tasks, tackled in the present thesis, is called reference resolution (RR), i.e. resolving utterances to the underlying geographical entities, referents (if any). The utterances that have referent(s) are called referring expressions (REs). The RR task is decomposed into two tasks: RE identification and resolution itself. Neural network models for both tasks have been designed and extensively evaluated. The model for RE identification, called RefNet, utilizes recurrent neural networks (RNNs) for handling sequential input, i.e. phrases. For each word in an utterance, RefNet outputs a label indicating whether this word is in the beginning of the RE, inside or outside it. The reference resolution model, called SpaceRefNet, uses the RefNet's RNN layer to encode REs and the designed feature extractor to represent geographical objects. Both encodings are fed to a simple feed-forward network with a softmax prediction layer, yielding the probability of match between the RE and the geographical object. Both introduced models have beaten the respective baselines and show promising results in general. / Tänk dig att du är i en ny stad och vill känna staden bättre. Du försöker att använda kartor, men blir förvirrad av gatunamn och kan inte njuta av din promenad. Ett dialogsystem, som kan hjälpa dig att navigera med hjälp av talade instruktioner, och som använder sig av framträdande landmärken i din närhet skulle vara mer användbart! Att utveckla ett sådant system är mycket komplicerat och man behöver att lösa ett antal mycket svåra uppgifter. En av dessa uppgifter kallas referenslösning (RR), vilket innebär att associera refererande fraser (RE) i yttranden till de geografiska objekt som avses. RR har brutits ner i två deluppgifter: identifiering av RE i yttranden, och referenslösning av dessa RE. Neurala-nätverksmodeller har utformats och utvärderats för båda uppgifterna. Modellen för identifiering av RE kallas RefNet och använder återkopplande neuronnät (RNN) för att behandla sekventiellindata, d.v.s. fraser. Varje ord i ett yttrande klassificeras av RefNet som en av tre följande kategorier: “i början av RE”, “i mitten av RE” samt “utanför RE”. Modellen för RR kallas SpaceRefNet och använder RefNets RNN-lager för att representera RE, samt en designad särdragsextraktor för att koda geografiska objekt. Båda kodningarna används som indata för ett enkelt framåtmatande neuronnät med ett avslutande softmax-lager. Det avslutande lagret producerar en sannolikhet att en viss RE motsvarar det geografiska objektet i fråga. Båda modellerna fungerade bättre än respektive baslinjemodeller, och visar lovande resultat i allmänhet. / Уявiть, що Ви опинилися у мiстi, яке нiколи не вiдвiдували. Ви хочете побачити все, що мiсто може Вам запропонувати, але не знаєте нiкого, хто може з цим допомогти. Назви вулиць на електронних картах не тiльки не допомагають, а ще й заплутують Вас, заважаючи отримувати насолоду вiд чудової прогулянки. Було б набагато зручнiше, якщо Ви могли б говорити з дiалоговою системою, як Ви говорите з друзями. Така система допомагала б Вам орiєнтуватися, використовуючи помiтнi орiєнтири у Вашому оточеннi. Розробка такої системи включає в себе багато нетривiальних задач, одна з яких називається задача розв’язання географiчних посилань (РГП). Словосполучення, вживанi з метою вказати на специфiчний географiчний об’єкт, є досить розповсюдженими у повсякденнiй мовi. Такi словосполучення називаються географiчними посиланнями (ГП), а географiчнi об’єкти, на якi вони посилаються - референтами. Задача розв’язання географiчних посилань полягає у спiвставленнi їх з вiдповiдними референтами.У рамках даної дипломної роботи задача РГП була декомпозована на двi частини: iдентифiкацiя географiчних посилань (IГП) та власне розв’язання (ВРГП). Для вирiшення обох задач було розроблено, протестовано та оцiнено вiдповiднi нейроннi мережi. Модель для розв’язання задачi IГП називається RefNet та використовує рекурентнi нейроннi мережi, щоб мати змогу обробляти послiдовнi вхiднi данi, як-то фрази. RefNet аналiзує висловлене речення дослiвно та визначає для кожного слова чи воно знаходиться на початку, всерединi чи поза ГП. Модель для розв’язання задачi ВРГП називається SpaceRefNet та використовує рекурентний шар RefNet для представлення поданих на вхiд ГП. Географiчнi об’єкти представляються за допомогою розробленого алгоритму видiляння ознак. Обидва представлення подаються на вхiд простої нейронної мережi прямого поширення з кiнцевим шаром softmax, який обчислює ймовiрнiсть того, що подане ГП описує поданий географiчний об’єкт.Обидвi мережi показали гарний результат, кращий за вiдповiднi базовi моделi. Результати загалом показують, що використання нейронних мереж для вирiшення задачi розв’язання географiчних посилань – це перспективний напрям для майбутнiх дослiджень.

This thesis is motivated by the need for scalable and reliable methods and technologies that support the construction of network data based on information from text data. Ultimately, the resulting data can be used for answering substantive and graph-theoretical questions about socio-technical networks. One main limitation with constructing network data from text data is that the validation of the resulting network data can be hard to infeasible, e.g. in the cases of covert, historical and large-scale networks. This thesis addresses this problem by identifying the impact of coding choices that must be made when extracting network data from text data on the structure of networks and network analysis results. My findings suggest that conducting reference resolution on text data can alter the identity and weight of 76% of the nodes and 23% of the links, and can cause major changes in the value of commonly used network metrics. Also, performing reference resolution prior to relation extraction leads to the retrieval of completely different sets of key entities in comparison to not applying this pre-processing technique. Based on the outcome of the presented experiments, I recommend strategies for avoiding or mitigating the identified issues in practical applications. When extracting socio-technical networks from texts, the set of relevant node classes might go beyond the classes that are typically supported by tools for named entity extraction. I address this lack of technology by developing an entity extractor that combines an ontology for sociotechnical networks that originates from the social sciences, is theoretically grounded and has been empirically validated in prior work, with a supervised machine learning technique that is based on probabilistic graphical models. This thesis does not stop at showing that the resulting prediction models achieve state of the art accuracy rates, but I also describe the process of integrating these models into an existing and publically available end-user product. As a result, users can apply these models to new text data in a convenient fashion. While a plethora of methods for building network data from information explicitly or implicitly contained in text data exists, there is a lack of research on how the resulting networks compare with respect to their structure and properties. This also applies to networks that can be extracted by using the aforementioned entity extractor as part of the relation extraction process. I address this knowledge gap by comparing the networks extracted by using this process to network data built with three alternative methods: text coding based on thesauri that associate text terms with node classes, the construction of network data from meta-data on texts, such as key words and index terms, and building network data in collaboration with subject matter experts. The outcomes of these comparative analyses suggest that thesauri generated with the entity extractor developed for this thesis need adjustments with respect to particular categories and types of errors. I am providing tools and strategies to assist with these refinements. My results also show that once these changes have been made and in contrast to manually constructed thesauri, the prediction models generalize with acceptable accuracy to other domains (news wire data, scientific writing, emails) and writing styles (formal, casual). The comparisons of networks constructed with different methods show that ground truth data built by subject matter experts are hardly resembled by any automated method that analyzes text bodies, and even less so by exploiting existing meta-data from text corpora. Thus, aiming to reconstruct social networks from text data leads to largely incomplete networks. Synthesizing the findings from this work, I outline which types of information on socio-technical networks are best captured by what network data construction method, and how to best combine these methods in order to gain a more comprehensive view on a network. When both, text data and relational data, are available as a source of information on a network, people have previously integrated these data by enhancing social networks with content nodes that represent salient terms from the text data. I present a methodological advancement to this technique and test its performance on the datasets used for the previously mentioned evaluation studies. By using this approach, multiple types of behavioral data, namely interactions between people as well as their language use, can be taken into account. I conclude that extracting content nodes from groups of structurally equivalent agents can be an appropriate strategy for enabling the comparison of the content that people produce, perceive or disseminate. These equivalence classes can represent a variety of social roles and social positions that network members occupy. At the same time, extracting content nodes from groups of structurally coherent agents can be suitable for enabling the enhancement of social networks with content nodes. The results from applying the latter approach to text data include a comparison of the outcome of topic modeling; an efficient and unsupervised information extraction technique, to the outcomes of alternative methods, including entity extraction based on supervised machine learning. My findings suggest that key entities from meta-data knowledge networks might serve as proper labels for unlabeled topics. Also, unsupervised and supervised learning leads to the retrieval of similar entities as highly likely members of highly likely topics, and key nodes from text-based knowledge networks, respectively. In summary, the contributions made with this thesis help people to collect, manage and analyze rich network data at any scale. This is a precondition for asking substantive and graph-theoretical questions, testing hypotheses, and advancing theories about networks. This thesis uses an interdisciplinary and computationally rigorous approach to work towards this goal; thereby advancing the intersection of network analysis, natural language processing and computing.