| 1. |
- Berglund, Martin, 1981-, et al.
(författare)
-
Parsing unranked tree languages, folded once
- 2023
-
Ingår i: Fundamentals of computation theory. - : Springer Nature. - 9783031435867 ; , s. 60-73
-
Konferensbidrag (refereegranskat)abstract
- A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges, i.e., folds, selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation is enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper we address the remaining case where only one fold operation is applied, but the order among edges is discarded. We show that under these conditions, the problem is solvable in non-uniform polynomial time.
|
|
| 2. |
- Berglund, Martin, 1981-, et al.
(författare)
-
Parsing unranked tree languages, folded once
- 2024
-
Ingår i: Algorithms. - : MDPI. - 1999-4893. ; 17:6
-
Tidskriftsartikel (refereegranskat)abstract
- A regular unranked tree folding consists of a regular unranked tree language and a folding operation that merges (i.e., folds) selected nodes of a tree to form a graph; the combination is a formal device for representing graph languages. If, in the process of folding, the order among edges is discarded so that the result is an unordered graph, then two applications of a fold operation are enough to make the associated parsing problem NP-complete. However, if the order is kept, then the problem is solvable in non-uniform polynomial time. In this paper, we address the remaining case, where only one fold operation is applied, but the order among the edges is discarded. We show that, under these conditions, the problem is solvable in non-uniform polynomial time.
|
|
| 3. |
- Berglund, Martin, 1981-, et al.
(författare)
-
Transduction from trees to graphs through folding
- 2023
-
Ingår i: Information and Computation. - : Elsevier. - 0890-5401 .- 1090-2651. ; 295
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce a fold operation that realises a tree-to-graph transduction by merging selected nodes in the input tree to form a possibly cyclic output graph. The work is motivated by the increasing use of graph-based representations in semantic parsing. We show that a suitable class of graphs languages can be generated by applying the fold operation to regular unranked tree languages. We investigate two versions of the fold operation, one that preserves a depth-first ordering between the edges, and one that does not. Finally, we demonstrate that the time complexity for the associated non-uniform membership problem is solvable in polynomial time for the order-preserving version, and NP-complete for the order-cancelling one.
|
|
| 4. |
- Björklund, Henrik, et al.
(författare)
-
Tree-based generation of restricted graph languages
- 2024
-
Ingår i: International Journal of Foundations of Computer Science. - : World Scientific. - 0129-0541. ; 35:1 & 2, s. 215-243
-
Tidskriftsartikel (refereegranskat)abstract
- Order-preserving DAG grammars (OPDGs) is a formalism for representing languages of structurally restricted graphs. As demonstrated in [17], they are sufficiently expressive to model abstract meaning representations in natural language processing, a graph-based form of semantic representation in which nodes encode objects and edges relations. At the same time, they can be parsed in O (n2 + nm) , where m and n are the sizes of the grammar and the input graph, respectively. In this work, we provide an initial algebra semantic for OPDGs, which allows us to view them as regular tree grammars under an equivalence theory. This makes it possible to transfer results from the field of formal tree languages to the domain of OPDGs, both in the unweighted and the weighted case. In particular, we show that deterministic OPDGs can be minimised efficiently, and that they are learnable under the \minimal adequeate teacher" paradigm, that is, by querying an oracle for equivalence between languages, and membership of individual graphs. To conclude, we demonstrate that the languages generated by OPDGs are definable in monadic second-order logic.
|
|
| 5. |
- Andersson, Eric, et al.
(författare)
-
Generating semantic graph corpora with graph expansion grammar
- 2023
-
Ingår i: 13th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2023). - : Open Publishing Association. ; , s. 3-15
-
Konferensbidrag (refereegranskat)abstract
- We introduce LOVELACE, a tool for creating corpora of semantic graphs.The system uses graph expansion grammar as a representational language, thus allowing users to craft a grammar that describes a corpus with desired properties. When given such grammar as input, the system generates a set of output graphs that are well-formed according to the grammar, i.e., a graph bank.The generation process can be controlled via a number of configurable parameters that allow the user to, for example, specify a range of desired output graph sizes.Central use cases are the creation of synthetic data to augment existing corpora, and as a pedagogical tool for teaching formal language theory.
|
|
| 6. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Aggregation-based minimization of finite state automata
- 2021
-
Ingår i: Acta Informatica. - : Springer Nature. - 0001-5903 .- 1432-0525. ; 58, s. 177-194
-
Tidskriftsartikel (refereegranskat)abstract
- We present a minimization algorithm for non-deterministic finite state automata that finds and merges bisimulation-equivalent states. The bisimulation relation is computed through partition aggregation, in contrast to existing algorithms that use partition refinement. The algorithm simultaneously generalises and simplifies an earlier one by Watson and Daciuk for deterministic devices. We show the algorithm to be correct and run in time O(n2r2|Σ|), where n is the number of states of the input automaton M, r is the maximal out-degree in the transition graph for any combination of state and input symbol, and |Σ| is the size of the input alphabet. The algorithm has a higher time complexity than derivatives of Hopcroft’s partition-refinement algorithm, but represents a promising new solution approach that preserves language equivalence throughout the computation process. Furthermore, since the algorithm essentially computes the maximal model of a logical formula derived from M, optimisation techniques from the field of model checking become applicable.
|
|
| 7. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Bottom-up unranked tree-to-graph transducers for translation into semantic graphs
- 2021
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 870, s. 3-28
-
Tidskriftsartikel (refereegranskat)abstract
- We develop a finite-state transducer for translating unranked trees into general graphs. This work is motivated by recent progress in semantic parsing for natural language, where sentences are first mapped into tree-shaped syntactic representations, and then these trees are translated into graph semantic representations. We investigate formal properties of our tree-to-graph transducers and develop a polynomial time algorithm for translating a weighted language of input trees into a packed representation, from which best-score graphs can be efficiently recovered.
|
|
| 8. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Bridging Perception, Memory, and Inference through Semantic Relations
- 2021
-
Ingår i: Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. - : Association for Computational Linguistics (ACL). - 9781955917094 ; , s. 9136-9142
-
Konferensbidrag (refereegranskat)abstract
- There is a growing consensus that surface form alone does not enable models to learn meaning and gain language understanding. This warrants an interest in hybrid systems that combine the strengths of neural and symbolic methods. We favour triadic systems consisting of neural networks, knowledge bases, and inference engines. The network provides perception, that is, the interface between the system and its environment. The knowledge base provides explicit memory and thus immediate access to established facts. Finally, inference capabilities are provided by the inference engine which reflects on the perception, supported by memory, to reason and discover new facts. In this work, we probe six popular language models for semantic relations and outline a future line of research to study how the constituent subsystems can be jointly realised and integrated.
|
|
| 9. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Generation and polynomial parsing of graph languages with non-structural reentrancies
- 2023
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - : Association for Computational Linguistics. - 0891-2017 .- 1530-9312. ; 49:4, s. 841-882
-
Tidskriftsartikel (refereegranskat)abstract
- Graph-based semantic representations are popular in natural language processing (NLP), where it is often convenient to model linguistic concepts as nodes and relations as edges between them. Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but which context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.
|
|
| 10. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Improved N-Best Extraction with an Evaluation on Language Data
- 2022
-
Ingår i: Computational linguistics - Association for Computational Linguistics (Print). - : MIT Press. - 0891-2017 .- 1530-9312. ; 48:1, s. 119-153
-
Tidskriftsartikel (refereegranskat)abstract
- We show that a previously proposed algorithm for the N-best trees problem can be made more efficient by changing how it arranges and explores the search space. Given an integer N and a weighted tree automaton (wta) M over the tropical semiring, the algorithm computes N trees of minimal weight with respect to M. Compared with the original algorithm, the modifications increase the laziness of the evaluation strategy, which makes the new algorithm asymptotically more efficient than its predecessor. The algorithm is implemented in the software BETTY, and compared to the state-of-the-art algorithm for extracting the N best runs, implemented in the software toolkit TIBURON. The data sets used in the experiments are wtas resulting from real-world natural language processing tasks, as well as artificially created wtas with varying degrees of nondeterminism. We find that BETTY outperforms TIBURON on all tested data sets with respect to running time, while TIBURON seems to be the more memory-efficient choice.
|
|
| 11. |
- Björklund, Johanna, 1961-
(författare)
-
The impact of state merging on predictive accuracy in probabilistic tree automata : Dietze's conjecture revisited
- 2024
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier. - 0022-0000 .- 1090-2724. ; 146
-
Tidskriftsartikel (refereegranskat)abstract
- Dietze's conjecture concerns the problem of equipping a tree automaton M with weights to make it probabilistic, in such a way that the resulting automaton N predicts a given corpus C as accurately as possible. The conjecture states that the accuracy cannot increase if the states in M are merged with respect to an equivalence relation ∼ so that the result is a smaller automaton M∼. Put differently, merging states can never improve predictions. This is under the assumption that both M and M∼ are bottom-up deterministic and accept every tree in C. We prove that the conjecture holds, using a construction that turns any probabilistic version N∼ of M∼ into a probabilistic version N of M, such that N assigns at least as great a weight to each tree in C as N∼ does.
|
|
| 12. |
- Björklund, Johanna, 1961-
(författare)
-
The impact of state merging on predictive accuracy in probabilistic tree automata : Dietze’s conjecture revisited
- 2023
-
Ingår i: Fundamentals of computation theory. - : Springer Nature. - 9783031435867 - 9783031435874 ; , s. 74-87
-
Konferensbidrag (refereegranskat)abstract
- Dietze’s conjecture concerns the problem of equipping a tree automaton M with weights to make it probabilistic, in such a way that the resulting automaton N predicts a given corpus C as accurately as possible. The conjecture states that the accuracy cannot increase if the states in M are merged with respect to an equivalence relation ∼ so that the result is a smaller automaton M∼. Put differently, merging states can never improve predictions. This is under the assumption that both M and M∼ are bottom-up deterministic and accept every tree in C. We prove that the conjecture holds, using a construction that turns any probabilistic version N∼ of M∼ into a probabilistic version N of M, such that N assigns at least as great a weight to each tree in C as N∼ does.
|
|
| 13. |
- Björklund, Johanna, 1961-, et al.
(författare)
-
Towards Semantic Representations with a Temporal Dimension
- 2020
-
Konferensbidrag (refereegranskat)abstract
- We outline the initial ideas for a representational framework for capturing temporal aspects in semantic parsing of multimodal data.As a starting point, we take the Abstract Meaning Representations of Banarescu et al. andpropose a way of extending them to coversequential progressions of events. The firstmodality to be considered is text, but the long-term goal is to also incorporate informationfrom visual and audio modalities, as well ascontextual information.
|
|
| 14. |
- Björklund, Niklas, et al.
(författare)
-
Assessing the confidence in pest freedom gained in the past pine wood nematode surveys
- 2023
-
Ingår i: EFSA supporting publications. - 2397-8325. ; 20
-
Tidskriftsartikel (refereegranskat)abstract
- All Member States of the European Union must conduct annual surveys of pine wood nematode (PWN) to ensure its timely detection. However, the statistical confidence of these surveys is rarely assessed. To facilitate such assessments, we developed two easy-to-use web applications: NoBaSURV-PWN for assessment of the statistical confidence of past PWN surveys, and NoBa Land Cover Retriever for retrieving the land cover data needed in the assessments. This report explains how the statistical confidence of past PWN surveys can be assessed with NoBaSURV-PWN. In addition, the reportpresents the assessments done with the NoBaSURV-PWN applicationfor Estonia, Finland, Lithuania, Norway, and Sweden. The technical details of the developed applications are presented,and some matters that have general relevance for statistical assessment and planning of quarantine pest surveys are discussed. Also, the capacity building activitiesdone in the project are described and their impact is evaluated.The assessments forthe five Nordic-Baltic countries show that, in most of the countries, PWN surveys have been extensive enough to provide evidence for facilitating tradewith a rather high confidence. Yet, the surveys have clearly not been extensive enough to ensure detection of PWN invasions at such an early stage that they could be eradicated.
|
|
| 15. |
|
|
| 16. |
|
|
| 17. |
|
|
| 18. |
|
|
| 19. |
|
|
| 20. |
|
|
| 21. |
|
|
| 22. |
|
|
| 23. |
|
|
| 24. |
|
|
| 25. |
|
|
| 26. |
|
|
| 27. |
|
|
| 28. |
|
|
| 29. |
|
|
| 30. |
|
|
| 31. |
|
|
| 32. |
|
|
| 33. |
|
|
| 34. |
|
|
| 35. |
|
|
| 36. |
|
|
| 37. |
|
|
| 38. |
|
|
| 39. |
|
|
| 40. |
- Dahlgren Lindström, Adam, 1993-
(författare)
-
Learning, reasoning, and compositional generalisation in multimodal language models
- 2024
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- We humans learn language and how to interact with the world through our different senses, grounding our language in what we can see, touch, hear, and smell. We call these streams of information different modalities, and our efficient processing and synthesis of the interactions between different modalities is a cornerstone of our intelligence. Therefore, it is important to study how we can build multimodal language models, where machine learning models learn from more than just text. This is particularly important in the era of large language models (LLMs), where their general capabilities are unclear and unreliable. This thesis investigates learning and reasoning in multimodal language models, and their capabilities to compositionally generalise in visual question answering tasks. Compositional generalisation is the process in which we produce and understand novel sentences, by systematically combining words and sentences to uncover the meaning in language, and has proven a challenge for neural networks. Previously, the literature has focused on compositional generalisation in text-only language models. One of the main contributions of this work is the extensive investigation of text-image language models. The experiments in this thesis compare three neural network-based models, and one neuro-symbolic method, and operationalise language grounding as the ability to reason with relevant functions over object affordances.In order to better understand the capabilities of multimodal models, this thesis introduces CLEVR-Math as a synthetic benchmark of visual mathematical reasoning. The CLEVR-Math dataset involve tasks such as adding and removing objects from 3D scenes based on textual instructions, such as \emph{Remove all blue cubes. How many objects are left?}, and is given as a curriculum of tasks of increasing complexity. The evaluation set of CLEVR-Math includes extensive testing of different functional and object attribute generalisations. We open up the internal representations of these models using a technique called probing, where linear classifiers are trained to recover concepts such as colours or named entities from the internal embeddings of input data. The results show that while models are fairly good at generalisation with attributes (i.e.~solving tasks involving never before seen objects), it is a big challenge to generalise over functions and to learn abstractions such as categories. The results also show that complexity in the training data is a driver of generalisation, where an extended curriculum improves the general performance across tasks and generalisation tests. Furthermore, it is shown that training from scratch versus transfer learning has significant effects on compositional generalisation in models.The results identify several aspects of how current methods can be improved in the future, and highlight general challenges in multimodal language models. A thorough investigation of compositional generalisation suggests that the pre-training of models allow models access to inductive biases that can be useful to solve new tasks. Contrastingly, models trained from scratch show much lower overall performance on the synthetic tasks at hand, but show lower relative generalisation gaps. In the conclusions and outlook, we discuss the implications of these results as well as future research directions.
|
|
| 41. |
- Dahlgren Lindström, Adam, et al.
(författare)
-
Probing Multimodal Embeddings for Linguistic Properties: the Visual-Semantic Case
- 2020
-
Ingår i: Proceedings of the 28th International Conference on Computational Linguistics (COLING). - Stroudsburg, PA, USA : International Committee on Computational Linguistics. ; , s. 730-744
-
Konferensbidrag (refereegranskat)abstract
- Semantic embeddings have advanced the state of the art for countless natural language processing tasks, and various extensions to multimodal domains, such as visual-semantic embeddings, have been proposed. While the power of visual-semantic embeddings comes from the distillation and enrichment of information through machine learning, their inner workings are poorly understood and there is a shortage of analysis tools. To address this problem, we generalize the notion of probing tasks to the visual-semantic case. To this end, we (i) discuss the formalization of probing tasks for embeddings of image-caption pairs, (ii) define three concrete probing tasks within our general framework, (iii) train classifiers to probe for those properties, and (iv) compare various state-of-the-art embeddings under the lens of the proposed probing tasks. Our experiments reveal an up to 12% increase in accuracy on visual-semantic embeddings compared to the corresponding unimodal embeddings, which suggest that the text and image dimensions represented in the former do complement each other
|
|
| 42. |
- Demirel, Cagla
(författare)
-
Analyzing Competitive Victimhood : Narratives of recognition and nonrecognition in the pursuit of reconciliation
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This dissertation analyzes the narrative manifestation of competitive victimhood and its variations within reconciliation processes. Competitive victimhood (CV) emerges when opposing groups assert themselves to be the sole or primary victims of conflict or use their historical suffering to rationalize ingroup transgressions. This study explores the notion of CV in four relational settings with various levels of violence, ranging from low-level conflict to civil war and mass atrocities, each having a different temporal proximity to violent incidents: Turkish–Armenian relations, relations between Catholic Republicans and Protestant Unionists in Northern Ireland, and both Bosniak–Bosnian Serb and Bosnian Croat–Bosniak relations in Bosnia andHerzegovina. The data analyzed include 60 interviews, public opinion polls, political party manifestos, political statements, NGO reports, documents, and memory sites.The research investigates narratives that convey perceptions of outgroup suffering and the perpetration of harm against outgroups. In so doing, it underscores the challenging relationship between the recognition of outgroup victimhood and acknowledgment of harm the ingroup has perpetrated on others, resulting in five categories that indicate varying levels of competitiveness: revengeful victimhood, strong–CV, mid–CV, weak–CV, and inclusive victimhood. This novel analytical framework facilitates observation of the manifestation of different levels of CV in conflict-to-peace transitions, as well as analysis of empirical examples representing variation from highly competitive to more inclusive victimhood. The weak–CV and inclusive victimhood categories also enable identification of the potential for memory-sharing in ethnonational groups’ conflict- and war-related narratives. A reflexive comparative analysis of case studies highlights the presence of CV across all cases, despite variations in the level of violence and temporal proximity to its occurrence. Findings reveal the importance of considering two factors in analyzing competitive victimhood: the symmetry/asymmetry of exposure to violence and contemporary political power struggles between ethnonational groups.
|
|
| 43. |
|
|
| 44. |
- Hatefi, Arezoo, 1990-
(författare)
-
Deep learning for news topic identification in limited supervision and unsupervised settings
- 2024
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In today's world, following news is crucial for decision-making and staying informed. With the growing volume of daily news, automated processing is essential for timely insights and in aiding individuals and corporations in navigating the complexities of the information society. Another use of automated processing is contextual advertising, which addresses privacy concerns associated with cookie-based advertising by placing ads solely based on web page content, without tracking users or their online behavior. Therefore, accurately determining and categorizing page content is crucial for effective ad placements. The news media, heavily reliant on advertising to sustain operations, represent a substantial market for contextual advertising strategies.Inspired by these practical applications and the advancements in deep learning over the past decade, this thesis mainly focuses on using deep learning for categorizing news articles into topics of varying granularity. Considering the dynamic nature of these applications and the limited availability of relevant labeled datasets for training models, the thesis emphasizes developing methods that can be trained effectively using unlabeled or partially labeled data. It proposes semi-supervised text classification models for categorizing datasets into predefined coarse-grained topics, where only a few labeled examples exist for each topic, while the majority of the dataset remains unlabeled. Furthermore, to better explore coarse-grained topics within news archives and streams and overcome the limitations of predefined topics in text classification the thesis suggests deep clustering approaches that can be trained in unsupervised settings. Moreover, to address the identification of fine-grained topics, the thesis introduces a novel story discovery model for monitoring event-based topics in multi-source news streams. Given that online news reporting often incorporates diverse modalities like text, images, video, and audio to convey information, the thesis finally initiates an investigation into the synergy between textual and visual elements in news article analysis. To achieve this objective, a text-image dataset was annotated, and a baseline was established for event-topic discovery in multimodal news streams. While primarily intended for news monitoring and contextual advertising, the proposed models can, more generally, be regarded as novel approaches in semi-supervised text classification, deep clustering, and news story discovery. Comparison with state-of-the-art baseline models demonstrates their effectiveness in addressing the respective objectives.
|
|
| 45. |
- Hoffmann, Mikael, et al.
(författare)
-
Guiding principles for the use of knowledge bases and real-world data in clinical decision support systems : report by an international expert workshop at Karolinska Institutet
- 2020
-
Ingår i: Expert Review of Clinical Pharmacology. - : Taylor & Francis. - 1751-2433 .- 1751-2441. ; 13:9, s. 925-934
-
Tidskriftsartikel (refereegranskat)abstract
- Introduction Technical and logical breakthroughs have provided new opportunities in medicine to use knowledge bases and large-scale clinical data (real-world) at point-of-care as part of a learning healthcare system to diminish the knowledge-practice gap. Areas covered The article is based on presentations, discussions and recommendations from an international scientific workshop. Value, research needs and funding avenues of knowledge bases and access to real-world data as well as transparency and incorporation of patient perspectives are discussed. Expert opinion Evidence-based, publicly funded, well-structured and curated knowledge bases are of global importance. They ought to be considered as a public responsibility requiring transparency and handling of conflicts of interest. Information has to be made accessible for clinical decision support systems (CDSS) for healthcare staff and patients. Access to rich and real-world data is essential for a learning health care ecosystem and can be augmented by data on patient-reported outcomes and preferences. This field can progress by the establishment of an international policy group for developing a best practice guideline on the development, maintenance, governance, evaluation principles and financing of open-source knowledge bases and handling of real-world data.
|
|
| 46. |
- Häglund, Emil, et al.
(författare)
-
AI-driven contextual advertising : toward relevant messaging without personal data
- 2024
-
Ingår i: Journal of Current Issues and Research in Advertising. - : Routledge. - 1064-1734 .- 2164-7313.
-
Tidskriftsartikel (refereegranskat)abstract
- In programmatic advertising, bids are increasingly based on knowledge of the surrounding media context. This shift toward contextual advertising is in part a counter-reaction to the current dependency on personal data, which is problematic from legal and ethical standpoints. The transition is accelerated by developments in artificial intelligence (AI), which allow for a deeper semantic analysis of the context and, by extension, more effective ad placement. We survey existing literature on the influence of context on the reception of an advertisement, focusing on three context factors: the applicability of the content and the ad, the affective tone of the content, and the involvement of the consumer. We then discuss how AI can leverage these priming effects to optimize ad placement through techniques such as reinforcement learning, data clustering, and sentiment analysis. This helps close the gap between the state of the art in advertising technology and the AI-driven targeting methodologies described in prior academic research.
|
|
| 47. |
- Jonsson, Anna, 1992-
(författare)
-
Best Trees Extraction and Contextual Grammars for Language Processing
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In natural language processing, the syntax of a sentence refers to the words used in the sentence, their grammatical role, and their order. Semantics concerns the concepts represented by the words in the sentence and their relations, i.e., the meaning of the sentence. While a human can easily analyse a sentence in a language they understand to figure out its grammatical construction and meaning, this is a difficult task for a computer. To analyse natural language, the computer needs a language model. First and foremost, the computer must have data structures that can represent syntax and semantics. Then, the computer requires some information about what is considered correct syntax and semantics – this can be provided in the form of human-annotated corpora of natural language. Computers use formal languages such as programming languages, and our goal is thus to model natural languages using formal languages. There are several ways to capture the correctness aspect of a natural language corpus in a formal language model. One strategy is to specify a formal language using a set of rules that are, in a sense, very similar to the grammatical rules of natural language. In this thesis, we only consider such rule-based formalisms.Trees are commonly used to represent syntactic analyses of sentences, and graphs can represent the semantics of sentences. Examples of rule-based formalisms that define languages of trees and graphs are tree automata and graph grammars, respectively. When used in language processing, the rules of a formalism are normally given weights, which are then combined as specified by the formalism to assign weights to the trees or graphs in its language. The weights enable us to rank the trees and graphs by their similarity to the linguistic data in the human-annotated corpora. Since natural language is very complicated to model, there are many small gaps in the research of natural language processing to address. The research of this thesis considers two separate but related problems: First, we have the N-best problem, which is about finding a number N of top-ranked hypotheses given a ranked hypothesis space. In our case, the hypothesis space is represented by a weighted rule-based formalism, making the hypothesis space a weighted formal language. The hypotheses themselves can for example have the form of weighted syntax trees. The second problem is that of semantic modelling, whose aim is to find a formalism complex enough to define languages of semantic representations. This model can however not be too complex since we still want to be able to efficiently compute solutions to language processing tasks.This thesis is divided into two parts according to the two problems introduced above. The first part covers the N-best problem for weighted tree automata. In this line of research, we develop and evaluate multiple versions of an efficient algorithm that solves the problem in question. Since our algorithm is the first to do so, we theoretically and experimentally evaluate it in comparison to the state-of-the-art algorithm for solving an easier version of the problem. In the second part, we study how rule-based formalisms can be used to model graphs that represent meaning, i.e., semantic graphs. We investigate an existing formalism and through this work learn what properties of that formalism are necessary for semantic modelling. Finally, we use our new-found knowledge to develop a more specialised formalism, and argue that it is better suited for the task of semantic modelling than existing formalisms.
|
|
| 48. |
- Kristan, Matej, et al.
(författare)
-
The first visual object tracking segmentation VOTS2023 challenge results
- 2023
-
Ingår i: 2023 IEEE/CVF International conference on computer vision workshops (ICCVW). - : Institute of Electrical and Electronics Engineers Inc.. - 9798350307443 - 9798350307450 ; , s. 1788-1810
-
Konferensbidrag (refereegranskat)abstract
- The Visual Object Tracking Segmentation VOTS2023 challenge is the eleventh annual tracker benchmarking activity of the VOT initiative. This challenge is the first to merge short-term and long-term as well as single-target and multiple-target tracking with segmentation masks as the only target location specification. A new dataset was created; the ground truth has been withheld to prevent overfitting. New performance measures and evaluation protocols have been created along with a new toolkit and an evaluation server. Results of the presented 47 trackers indicate that modern tracking frameworks are well-suited to deal with convergence of short-term and long-term tracking and that multiple and single target tracking can be considered a single problem. A leaderboard, with participating trackers details, the source code, the datasets, and the evaluation kit are publicly available at the challenge website1
|
|
| 49. |
- Kristan, Matej, et al.
(författare)
-
The tenth visual object tracking VOT2022 challenge results
- 2023
-
Ingår i: Computer vision – ECCV 2022 workshops. - Cham : Springer. - 9783031250842 - 9783031250859 ; , s. 431-460
-
Konferensbidrag (refereegranskat)abstract
- The Visual Object Tracking challenge VOT2022 is the tenth annual tracker benchmarking activity organized by the VOT initiative. Results of 93 entries are presented; many are state-of-the-art trackers published at major computer vision conferences or in journals in recent years. The VOT2022 challenge was composed of seven sub-challenges focusing on different tracking domains: (i) VOT-STs2022 challenge focused on short-term tracking in RGB by segmentation, (ii) VOT-STb2022 challenge focused on short-term tracking in RGB by bounding boxes, (iii) VOT-RTs2022 challenge focused on “real-time” short-term tracking in RGB by segmentation, (iv) VOT-RTb2022 challenge focused on “real-time” short-term tracking in RGB by bounding boxes, (v) VOT-LT2022 focused on long-term tracking, namely coping with target disappearance and reappearance, (vi) VOT-RGBD2022 challenge focused on short-term tracking in RGB and depth imagery, and (vii) VOT-D2022 challenge focused on short-term tracking in depth-only imagery. New datasets were introduced in VOT-LT2022 and VOT-RGBD2022, VOT-ST2022 dataset was refreshed, and a training dataset was introduced for VOT-LT2022. The source code for most of the trackers, the datasets, the evaluation kit and the results are publicly available at the challenge website (http://votchallenge.net).
|
|
| 50. |
|
|
