Quantifying Sequential Subsumption

Research output: Contribution to journalArticle

Abstract

Subsumption is used in knowledge representation and ontology to describe the relationship between concepts. Concept A is subsumed by concept B if the exten- sion of A is always a subset of the extension of B, irrespective of the interpretation. The subsumption relation is also useful in other data analysis tasks such as pattern recognition – for example in image analysis to detect objects in an image, and in spectral data analysis to detect the presence of a reference pattern in a given spec- trum. Sometimes the subsumption relation may not be 100% true, so it is useful to quantify this relationship.
In this paper we study how to quantify subsumption for sequential patterns. We review existing work on subsumption, give an axiomatic characterisation of subsumption, and present one general approach to quantification in terms of set intersection operation over concept extension. Constructing the concept extension set explicitly is impossible without specifying the domain of discourse and the interpretation. Instead, we focus on concept intension for sequences as patterns and propose to represent concept intension of a sequence by its subsequences. We further consider different types of concept intension set – subsequence set, subse- quence multiset, embedding set and embedding set with constraints such as warp- ing and selection. We then present a general algorithmic framework for computing set intersections, and specific algorithms for computing different concept intension sets. We also present an experimental evaluation of these algorithms with regard to their runtime performance.
LanguageEnglish
Number of pages32
JournalTheoretical Computer Science
Early online date13 Jun 2019
DOIs
Publication statusE-pub ahead of print - 13 Jun 2019

Fingerprint

Knowledge representation
Image analysis
Pattern recognition
Ontology

Keywords

  • Subsumption characterisation; Subsumption quantification; Sequence and subsequence analysis; Sequence similarity; Grid algorithm
  • Subsumption characterisation
  • Grid algorithm
  • Subsumption quantification
  • Sequence similarity
  • Sequence and subsequence analysis

Cite this

@article{caf43e15e38749018bc0bb60c8fb8c04,
title = "Quantifying Sequential Subsumption",
abstract = "Subsumption is used in knowledge representation and ontology to describe the relationship between concepts. Concept A is subsumed by concept B if the exten- sion of A is always a subset of the extension of B, irrespective of the interpretation. The subsumption relation is also useful in other data analysis tasks such as pattern recognition – for example in image analysis to detect objects in an image, and in spectral data analysis to detect the presence of a reference pattern in a given spec- trum. Sometimes the subsumption relation may not be 100{\%} true, so it is useful to quantify this relationship.In this paper we study how to quantify subsumption for sequential patterns. We review existing work on subsumption, give an axiomatic characterisation of subsumption, and present one general approach to quantification in terms of set intersection operation over concept extension. Constructing the concept extension set explicitly is impossible without specifying the domain of discourse and the interpretation. Instead, we focus on concept intension for sequences as patterns and propose to represent concept intension of a sequence by its subsequences. We further consider different types of concept intension set – subsequence set, subse- quence multiset, embedding set and embedding set with constraints such as warp- ing and selection. We then present a general algorithmic framework for computing set intersections, and specific algorithms for computing different concept intension sets. We also present an experimental evaluation of these algorithms with regard to their runtime performance.",
keywords = "Subsumption characterisation; Subsumption quantification; Sequence and subsequence analysis; Sequence similarity; Grid algorithm, Subsumption characterisation, Grid algorithm, Subsumption quantification, Sequence similarity, Sequence and subsequence analysis",
author = "H. Wang and Cees Elzinga and Zhiwei Lin and Jordan Vincent",
year = "2019",
month = "6",
day = "13",
doi = "10.1016/j.tcs.2019.05.025",
language = "English",

}

Quantifying Sequential Subsumption. / Wang, H.; Elzinga, Cees; Lin, Zhiwei; Vincent, Jordan.

13.06.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Quantifying Sequential Subsumption

AU - Wang, H.

AU - Elzinga, Cees

AU - Lin, Zhiwei

AU - Vincent, Jordan

PY - 2019/6/13

Y1 - 2019/6/13

N2 - Subsumption is used in knowledge representation and ontology to describe the relationship between concepts. Concept A is subsumed by concept B if the exten- sion of A is always a subset of the extension of B, irrespective of the interpretation. The subsumption relation is also useful in other data analysis tasks such as pattern recognition – for example in image analysis to detect objects in an image, and in spectral data analysis to detect the presence of a reference pattern in a given spec- trum. Sometimes the subsumption relation may not be 100% true, so it is useful to quantify this relationship.In this paper we study how to quantify subsumption for sequential patterns. We review existing work on subsumption, give an axiomatic characterisation of subsumption, and present one general approach to quantification in terms of set intersection operation over concept extension. Constructing the concept extension set explicitly is impossible without specifying the domain of discourse and the interpretation. Instead, we focus on concept intension for sequences as patterns and propose to represent concept intension of a sequence by its subsequences. We further consider different types of concept intension set – subsequence set, subse- quence multiset, embedding set and embedding set with constraints such as warp- ing and selection. We then present a general algorithmic framework for computing set intersections, and specific algorithms for computing different concept intension sets. We also present an experimental evaluation of these algorithms with regard to their runtime performance.

AB - Subsumption is used in knowledge representation and ontology to describe the relationship between concepts. Concept A is subsumed by concept B if the exten- sion of A is always a subset of the extension of B, irrespective of the interpretation. The subsumption relation is also useful in other data analysis tasks such as pattern recognition – for example in image analysis to detect objects in an image, and in spectral data analysis to detect the presence of a reference pattern in a given spec- trum. Sometimes the subsumption relation may not be 100% true, so it is useful to quantify this relationship.In this paper we study how to quantify subsumption for sequential patterns. We review existing work on subsumption, give an axiomatic characterisation of subsumption, and present one general approach to quantification in terms of set intersection operation over concept extension. Constructing the concept extension set explicitly is impossible without specifying the domain of discourse and the interpretation. Instead, we focus on concept intension for sequences as patterns and propose to represent concept intension of a sequence by its subsequences. We further consider different types of concept intension set – subsequence set, subse- quence multiset, embedding set and embedding set with constraints such as warp- ing and selection. We then present a general algorithmic framework for computing set intersections, and specific algorithms for computing different concept intension sets. We also present an experimental evaluation of these algorithms with regard to their runtime performance.

KW - Subsumption characterisation; Subsumption quantification; Sequence and subsequence analysis; Sequence similarity; Grid algorithm

KW - Subsumption characterisation

KW - Grid algorithm

KW - Subsumption quantification

KW - Sequence similarity

KW - Sequence and subsequence analysis

UR - http://www.scopus.com/inward/record.url?scp=85067668501&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2019.05.025

DO - 10.1016/j.tcs.2019.05.025

M3 - Article

ER -