Incremental, Systematic Acquiring of Knowledge (using closure ...

Incremental, Systematic Acquiring of Knowledge (using closure ...

Incremental, Systematic Acquiring of Knowledge (using Closure Algorithms) Roger L. Costello February 1, 2014 Example #1 Problem Statement Problem: What cities can you get to from Boston? Boston Miami Miami Houston

Cleveland Akron Boston Denver It is easy to eyeball this sample XML and see that from Boston you can get to Miami, Houston (via Miami), and Denver. But if the XML document had thousands of flights, it would be impossible to eyeball it to get the answer. 3

Need a Strategy We need a systematic, incremental approach to obtaining the answer. Thats what closure algorithms give us. 4 Closure algorithms A closure algorithm enables the incremental, systematic acquiring of knowledge. Closure algorithms are characterized by two components: An initialization, which is an assessment of what we know initially. An inference rule, which is a rule telling how knowledge from several places is to be combined. The inference rule(s) are repeated until nothing changes any more. 5

Initial Knowledge This is what we know initially: All the flights From Boston we can get to Miami and Denver since there are direct flights to those cities. Boston Miami Miami Houston Cleveland Akron Boston

Denver 6 Inference Rule If we can get to the city identified in , then we can get to the city identified in . 7 Initial knowledge Go through the XML and for each with a direct flight from Boston, mark it as Can get there from Boston. Flight BostonMiami MiamiHouston ClevelandAkron

BostonDenver Can get there from Boston? Yes Yes 8 Build on top of our knowledge Apply the inference rule to gain more knowledge. This is round two (round one was marking the initial knowledge). Flight BostonMiami MiamiHouston ClevelandAkron BostonDenver

Can get there from Boston? Yes Yes (since we can get to Miami) Yes 9 Round Three A third round yields no additional cities. Flight BostonMiami MiamiHouston ClevelandAkron BostonDenver Can get there from Boston? Yes

Yes Yes 10 Problem/Answer Problem: What cities can you get to from Boston? Answer: We can get to these cities: {Miami, Denver, Houston} 11 Example #2 Clean XML Schema Problem: Are there any element declarations in the adjacent XML

Schema that, if used, do not result in a valid XML instance document (e.g., perhaps because they loop infinitely)? In other words, are there any nonproductive element declarations?

13 Concise Notation For brevity, lets depict the element declarations this way: Document A B | D E A string B string C C string D d F E string F string D A string means the value of element A is a string.

B string C means the value of element B is a string and a child element C (i.e., B has mixed content). 14 Terminology Document A B | D E A string B string C C string D d F E string F string D These are rules. Each rule has a left-hand side and a righthand side (the two sides are separated by an arrow ). Document, A, B, , F are non-terminal symbols.

string is a terminal symbol. 15 Find the productive rules We find the non-productive rules by finding the productive ones. A rule is productive if its right-hand side consists of symbols all of which are productive. Symbols that are productive: Terminal symbols are productive since they produce values. A non-terminal is productive if there is a productive rule for it. 16 Initial knowledge Go through the grammar and for each rule for which we know that all its right-hand side members are productive, mark the rule and the non-terminal it defines as productive.

Rule Is it productive? Document A B Document D E A string Yes B string C C string Yes D string F E string Yes

F string D 17 Build on top of our knowledge Apply the inference rule to gain more knowledge. Rule Is it productive? Document A B Document D E A string Yes B string C Yes (since string and C are productive) C string

Yes D string F E string Yes F string D 18 Round three Rule Is it productive? Document A B Yes (since A and B are productive)

Document D E A string Yes B string C Yes (since string and C are productive) C string Yes D string F E string Yes F string D

19 Round four A fourth round yields nothing new. Rule Is it productive? Document A B Yes (since A and B are productive) Document D E A string Yes B string C

Yes (since string and C are productive) C string Yes D string F E string Yes F string D 20 Recap We now know that Document, A, B, C, and E are productive and D, F, and the rule Document D E are not productive. Rule

Is it productive? Document A B Yes (since A and B are productive) Document D E A string Yes B string C Yes (since C is productive) C string Yes

D string F E string Yes F string D 21 Remove non-productive rules We have pursued all possible avenues for productivity, and have not found any possibilities for D, F, and the second rule for Document. That means the rules for D, F, and the second rule for Document can be removed from the XML Schema. Rule Is it productive? Document A B

Yes (since A and B are productive) A string Yes B string C Yes (since C is productive) C string Yes E string Yes The XML Schema after removing non-productive rules

22 Cleaned XML Schema Problem: Does the XML Schema have any nonproductive element declarations? Answer: Yes, and the cleaned XML Schema is shown in the adjacent box.

23 Bottom-up process Removing the non-productive rules is a bottom-up process: only the bottom level, where the terminal symbols live, can we know what is productive. 24

Why is it called closure? We have seen two examples where new knowledge was incrementally, systematically acquired using a closure algorithm. Question: Where does the term closure come from? Answer: Applying the inference rule yields knowledge about existing symbols, without going outside the universe of discourse. In the last example, applying the inference rule resulted in new knowledge about the elements that are productive in the XML Schema. Conversely, say the inference rule were to result in knowledge about elements in a completely different XML Schema, then the algorithm would not be closed. In a closure algorithm the universe of discourse is self-contained, no information outside of the universe is generated. 25 Acknowledgement Some of the information in these slides come from this fabulous book:

Parsing Techniques by Dick Grune and Ceriel Jacobs.X 26

Recently Viewed Presentations

  • Chapter Seven: Atomic Structure and Periodicity

    Chapter Seven: Atomic Structure and Periodicity

    Full electron configuration spdf notation. 1s22s22p63s23p2. Noble Gas Notation. The innermost electrons (core) can be represented by the full shell of noble gas electron configuration:
  • EQuIP Student Work Protocol — ELA/Literacy

    EQuIP Student Work Protocol — ELA/Literacy

    Use the EQuIP Student Work Protocol to examine student work and provide evidence-based feedback for both the task and also its lesson/unit. Develop a common understanding among reviewers of task alignment and quality. Develop a common understanding of the alignment...
  • Ratio Transformation for Stationary Time Series with Special ...

    Ratio Transformation for Stationary Time Series with Special ...

    From table [2] below the Ljumg-Box test has p-values at lag K =12 and K=24 equal to 0.000 and therefore we can confidently say the model MA of order 1 is adequately fit the ratio transformation data. The invertibility condition...
  • Mos Nicolae & Mos Craciun

    Mos Nicolae & Mos Craciun

    Tot acum erau preparate douasprezece feluri de mancare de post (grau pisat si fiert, prune afumate fierte, bob fiert, sarmale cu crupe, ciuperci tocate cu usturoi, bors de bureti, fasole fiarta si "sleita" etc), precum si mancaruri din peste.
  • Start-Up - Daily Oral Language

    Start-Up - Daily Oral Language

    did she write winder footsteps, a short poem. 1/16/18. Week 2 - Day 7. the Company . hes. working for is . amsco. ... sarah. link. 1299 . oakhurst. drive. los . angeles. ca . 90036. i wish i could...
  • Electron Storage Ring Design - Indico

    Electron Storage Ring Design - Indico

    Low-β squeeze achieved by β-wave through adjacent arcs ("ATS lattice") Spin matching ( Talk by F. Méot) Coupling compensation of spin rotator solenoids. Spin rotator concept. Electron spin rotators will be based on solenoids with subsequent horizontal bends:
  • Slayt 1 - Harran Üniversitesi

    Slayt 1 - Harran Üniversitesi

    Parsel bacaları, binaya ait caddede yer alırlar. Eğer bahçe bulunmuyorsa, yaya kaldırımı altına inşa edilirler. Parsel bacasında toplanan atıksular, tek bir boru hattı ile ana kanala iletilirler. Parsel bacası çıkışı bir çatal parçası ile ana mecraya bağlanır.
  • Social Innovation and Self Directed Support (Dundee)

    Social Innovation and Self Directed Support (Dundee)

    What is Self Directed Support (SDS)?. SDS is intended to support, promote and protect the human rights and independent living of people using care and support services in Scotland . SDS aims to ensure that care and support is delivered...