Efficient Computation of the Relative Entropy of Probabilistic Automata View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Corinna Cortes , Mehryar Mohri , Ashish Rastogi , Michael D. Riley

ABSTRACT

The problem of the efficient computation of the relative entropy of two distributions represented by deterministic weighted automata arises in several machine learning problems. We show that this problem can be naturally formulated as a shortest-distance problem over an intersection automaton defined on an appropriate semiring. We describe simple and efficient novel algorithms for its computation and report the results of experiments demonstrating the practicality of our algorithms for very large weighted automata. Our algorithms apply to unambiguous weighted automata, a class of weighted automata that strictly includes deterministic weighted automata. These are also the first algorithms extending the computation of entropy or of relative entropy beyond the class of deterministic weighted automata. More... »

PAGES

323-336

References to SciGraph publications

Book

TITLE

LATIN 2006: Theoretical Informatics

ISBN

978-3-540-32755-4
978-3-540-32756-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11682462_32

DOI

http://dx.doi.org/10.1007/11682462_32

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1034484968


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Google (United States)", 
          "id": "https://www.grid.ac/institutes/grid.420451.6", 
          "name": [
            "Google Research, New York, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cortes", 
        "givenName": "Corinna", 
        "id": "sg:person.010042472421.96", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010042472421.96"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Courant Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.482020.c", 
          "name": [
            "Google Research, New York, NY, USA", 
            "Courant Institute of Mathematical Sciences, New York University, New York, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mohri", 
        "givenName": "Mehryar", 
        "id": "sg:person.014747403275.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014747403275.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Courant Institute of Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.482020.c", 
          "name": [
            "Courant Institute of Mathematical Sciences, New York University, New York, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rastogi", 
        "givenName": "Ashish", 
        "id": "sg:person.014423335421.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014423335421.13"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Google (United States)", 
          "id": "https://www.grid.ac/institutes/grid.420451.6", 
          "name": [
            "Google Research, New York, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Riley", 
        "givenName": "Michael D.", 
        "id": "sg:person.011157321425.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011157321425.92"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1006/csla.2001.0184", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012095627"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1017490034", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-69959-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017490034", 
          "https://doi.org/10.1007/978-3-642-69959-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-69959-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017490034", 
          "https://doi.org/10.1007/978-3-642-69959-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(77)90056-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018441534"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-59126-6_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036199133", 
          "https://doi.org/10.1007/978-3-642-59126-6_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-59126-6_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036199133", 
          "https://doi.org/10.1007/978-3-642-59126-6_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1046944411", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-6264-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046944411", 
          "https://doi.org/10.1007/978-1-4612-6264-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-6264-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046944411", 
          "https://doi.org/10.1007/978-1-4612-6264-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054102000996", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062896396"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ita/1997310504371", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083550548"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/0471200611", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098661155"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/0471200611", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098661155"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109710706", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-73235-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109710706", 
          "https://doi.org/10.1007/978-3-642-73235-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-73235-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109710706", 
          "https://doi.org/10.1007/978-3-642-73235-5"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "The problem of the efficient computation of the relative entropy of two distributions represented by deterministic weighted automata arises in several machine learning problems. We show that this problem can be naturally formulated as a shortest-distance problem over an intersection automaton defined on an appropriate semiring. We describe simple and efficient novel algorithms for its computation and report the results of experiments demonstrating the practicality of our algorithms for very large weighted automata. Our algorithms apply to unambiguous weighted automata, a class of weighted automata that strictly includes deterministic weighted automata. These are also the first algorithms extending the computation of entropy or of relative entropy beyond the class of deterministic weighted automata.", 
    "editor": [
      {
        "familyName": "Correa", 
        "givenName": "Jos\u00e9 R.", 
        "type": "Person"
      }, 
      {
        "familyName": "Hevia", 
        "givenName": "Alejandro", 
        "type": "Person"
      }, 
      {
        "familyName": "Kiwi", 
        "givenName": "Marcos", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11682462_32", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-32755-4", 
        "978-3-540-32756-1"
      ], 
      "name": "LATIN 2006: Theoretical Informatics", 
      "type": "Book"
    }, 
    "name": "Efficient Computation of the Relative Entropy of Probabilistic Automata", 
    "pagination": "323-336", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034484968"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11682462_32"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a446465b53a2600e3c3e5fabd4619e7c8ae17486c328e6e3b0dd46c167fce5e2"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11682462_32", 
      "https://app.dimensions.ai/details/publication/pub.1034484968"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000356_0000000356/records_57880_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11682462_32"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11682462_32'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11682462_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11682462_32'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11682462_32'


 

This table displays all metadata directly associated to this object as RDF triples.

137 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11682462_32 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N1399ea4f78d64f248ec4cf9ab45dc846
4 schema:citation sg:pub.10.1007/978-1-4612-6264-0
5 sg:pub.10.1007/978-3-642-59126-6_10
6 sg:pub.10.1007/978-3-642-69959-7
7 sg:pub.10.1007/978-3-642-73235-5
8 https://app.dimensions.ai/details/publication/pub.1017490034
9 https://app.dimensions.ai/details/publication/pub.1046944411
10 https://app.dimensions.ai/details/publication/pub.1109710706
11 https://doi.org/10.1002/0471200611
12 https://doi.org/10.1006/csla.2001.0184
13 https://doi.org/10.1016/0304-3975(77)90056-1
14 https://doi.org/10.1051/ita/1997310504371
15 https://doi.org/10.1142/s0129054102000996
16 schema:datePublished 2006
17 schema:datePublishedReg 2006-01-01
18 schema:description The problem of the efficient computation of the relative entropy of two distributions represented by deterministic weighted automata arises in several machine learning problems. We show that this problem can be naturally formulated as a shortest-distance problem over an intersection automaton defined on an appropriate semiring. We describe simple and efficient novel algorithms for its computation and report the results of experiments demonstrating the practicality of our algorithms for very large weighted automata. Our algorithms apply to unambiguous weighted automata, a class of weighted automata that strictly includes deterministic weighted automata. These are also the first algorithms extending the computation of entropy or of relative entropy beyond the class of deterministic weighted automata.
19 schema:editor N195e9dc06bcd420e8f7efaa12fb987c6
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N9e19139cc0a7418d91a7d49ca43e16e5
24 schema:name Efficient Computation of the Relative Entropy of Probabilistic Automata
25 schema:pagination 323-336
26 schema:productId N3242f58ae6e74ec6b27591168c1e25f2
27 N8736c462caad4c4a983b499a77f08f6d
28 Nacefdbb8232d4ed2b996c2b8593b9ca5
29 schema:publisher Nd328f4eafd114fa989aece562632b8fe
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034484968
31 https://doi.org/10.1007/11682462_32
32 schema:sdDatePublished 2019-04-16T07:30
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N0505af216ebc4821980ef40af5fbae4f
35 schema:url https://link.springer.com/10.1007%2F11682462_32
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N03a2be467bc0405e8610a131344560ff schema:familyName Hevia
40 schema:givenName Alejandro
41 rdf:type schema:Person
42 N0505af216ebc4821980ef40af5fbae4f schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N05bf6dda5c9e4c6cae4b59c0dc6ae8ff rdf:first sg:person.011157321425.92
45 rdf:rest rdf:nil
46 N1399ea4f78d64f248ec4cf9ab45dc846 rdf:first sg:person.010042472421.96
47 rdf:rest Nc30500a816624d7fa5b0147cd047b962
48 N195e9dc06bcd420e8f7efaa12fb987c6 rdf:first N86f7c3cc56b146a6a76b7e98df1e255c
49 rdf:rest N3c1725e8408b4070a1c98033032bfbc5
50 N20b0164b38a849298bb5275e580a4c39 rdf:first N698bf521eb0a4dbebcc5fe7838f3024e
51 rdf:rest rdf:nil
52 N3242f58ae6e74ec6b27591168c1e25f2 schema:name dimensions_id
53 schema:value pub.1034484968
54 rdf:type schema:PropertyValue
55 N3c1725e8408b4070a1c98033032bfbc5 rdf:first N03a2be467bc0405e8610a131344560ff
56 rdf:rest N20b0164b38a849298bb5275e580a4c39
57 N50a9d7f6e81643de909bf51559bac601 rdf:first sg:person.014423335421.13
58 rdf:rest N05bf6dda5c9e4c6cae4b59c0dc6ae8ff
59 N698bf521eb0a4dbebcc5fe7838f3024e schema:familyName Kiwi
60 schema:givenName Marcos
61 rdf:type schema:Person
62 N86f7c3cc56b146a6a76b7e98df1e255c schema:familyName Correa
63 schema:givenName José R.
64 rdf:type schema:Person
65 N8736c462caad4c4a983b499a77f08f6d schema:name doi
66 schema:value 10.1007/11682462_32
67 rdf:type schema:PropertyValue
68 N9e19139cc0a7418d91a7d49ca43e16e5 schema:isbn 978-3-540-32755-4
69 978-3-540-32756-1
70 schema:name LATIN 2006: Theoretical Informatics
71 rdf:type schema:Book
72 Nacefdbb8232d4ed2b996c2b8593b9ca5 schema:name readcube_id
73 schema:value a446465b53a2600e3c3e5fabd4619e7c8ae17486c328e6e3b0dd46c167fce5e2
74 rdf:type schema:PropertyValue
75 Nc30500a816624d7fa5b0147cd047b962 rdf:first sg:person.014747403275.19
76 rdf:rest N50a9d7f6e81643de909bf51559bac601
77 Nd328f4eafd114fa989aece562632b8fe schema:location Berlin, Heidelberg
78 schema:name Springer Berlin Heidelberg
79 rdf:type schema:Organisation
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.010042472421.96 schema:affiliation https://www.grid.ac/institutes/grid.420451.6
87 schema:familyName Cortes
88 schema:givenName Corinna
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010042472421.96
90 rdf:type schema:Person
91 sg:person.011157321425.92 schema:affiliation https://www.grid.ac/institutes/grid.420451.6
92 schema:familyName Riley
93 schema:givenName Michael D.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011157321425.92
95 rdf:type schema:Person
96 sg:person.014423335421.13 schema:affiliation https://www.grid.ac/institutes/grid.482020.c
97 schema:familyName Rastogi
98 schema:givenName Ashish
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014423335421.13
100 rdf:type schema:Person
101 sg:person.014747403275.19 schema:affiliation https://www.grid.ac/institutes/grid.482020.c
102 schema:familyName Mohri
103 schema:givenName Mehryar
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014747403275.19
105 rdf:type schema:Person
106 sg:pub.10.1007/978-1-4612-6264-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046944411
107 https://doi.org/10.1007/978-1-4612-6264-0
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-642-59126-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036199133
110 https://doi.org/10.1007/978-3-642-59126-6_10
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/978-3-642-69959-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017490034
113 https://doi.org/10.1007/978-3-642-69959-7
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/978-3-642-73235-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109710706
116 https://doi.org/10.1007/978-3-642-73235-5
117 rdf:type schema:CreativeWork
118 https://app.dimensions.ai/details/publication/pub.1017490034 schema:CreativeWork
119 https://app.dimensions.ai/details/publication/pub.1046944411 schema:CreativeWork
120 https://app.dimensions.ai/details/publication/pub.1109710706 schema:CreativeWork
121 https://doi.org/10.1002/0471200611 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098661155
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1006/csla.2001.0184 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012095627
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1016/0304-3975(77)90056-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018441534
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1051/ita/1997310504371 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083550548
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1142/s0129054102000996 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896396
130 rdf:type schema:CreativeWork
131 https://www.grid.ac/institutes/grid.420451.6 schema:alternateName Google (United States)
132 schema:name Google Research, New York, NY, USA
133 rdf:type schema:Organization
134 https://www.grid.ac/institutes/grid.482020.c schema:alternateName Courant Institute of Mathematical Sciences
135 schema:name Courant Institute of Mathematical Sciences, New York University, New York, NY, USA
136 Google Research, New York, NY, USA
137 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...