1990-08-10|DARPA

01 | Title

• DARPA Research on Text Retrieval and Understanding: Algorithm for Extracting specified data from documents
  • BAA#90-16

  • DUE 1990-09-04

• DARPA Research in Speech and Natural Language: System to extract specified information from free text
  • BAA#91-15

  • DUE 1991-08-30

02 | innovative claims

02.01 | extraction algorithm featuring recursive packetizing process

• knowledge representation in packet and compartment form

• LISP-like structured knowledge notation

• preposition-driven extraction engine

• flexible modular algorithm approach

02.02 | generic knowledge storage mechanism

• conversion of various free formats into standard formats

• absolute indexing and addressing

• knowledge soft-link to unique items to avoid duplication

• quantification of uncertainty levels

03 | deliverables

03.01 | document describing the following

• extraction algorithm

• knowledge packet format specification

03.02 | demonstration prototype system

• coded extraction algorithm and lexicon/grammar databases

• hardware and software workstation platform to be determined

04 | schedule and milestones for the proposed research

• 1991-06, 1992-06
  • complete setup of hardware and software workstation platform

• 1991-09, 1992-09
  • demonstrate in concept workable extraction algorithm

• 1991-12, 1992-12
  • document modular algorithm, knowledge packet properties and attributes

• 1992-03, 1993-03
  • build sufficient lexicon/grammar databases for short samples
    • English and French

  • demonstrate workable extraction algorithm for short samples
    • English and French

• 1992-06, 1993-06
  • successfully run sample free texts
    • English and French

• 1992-09, 1993-09
  • test portability, trainability, extensibility, improvability, and robustness

• 1992-12, 1993-12
  • deliver documentation and prototype system

05 | proprietary claims

• There are no proprietary claims to results, prototypes, or systems supporting and/or necessary for the use of the research, results, and/or prototype.

06 | a statement of work

06.01 | language-independent part

• decide and obtain hardware and software workstation platform

• develop sentence detection algorithm

• develop packetization algorithm

• develop recursive packetization and database look-up algorithm

• develop template mapping algorithm

06.02 | language-dependent part

• English
  • obtain XWINDOW software utility for English

  • obtain machine-readable English dictionary

  • develop word separation algorithm for English

  • develop preposition identification algorithm for English

  • develop proximity analysis and verb recognition algorithm for English

• French
  • obtain XWINDOW software utility for French

  • obtain machine-readable French dictionary

  • develop word separation algorithm for French

  • develop preposition identification algorithm for French

  • develop proximity analysis and verb recognition algorithm for French

07 | a description of results, products, and transferable technology

07.01 | primary focus on stretching the state of the art

• algorithm development leading to technological breakthroughs

• significant amount of theoretical work as well as some experimental and prototyping efforts anticipated

• substantial computational cost predicted to achieve accuracy

• no commercial product available now based on the proposed algorithm
  • too CPU intensive in today's computing capability

07.02 | expected human-machine interface

• single point-of-entry to the system for absolute simplicity and consistency

• menu-driven interface
  • push-button operation

  • user interventions queued for any-time human processing

  • on-line help facility only (no paper manuals whatsoever)

  • Hypertext application

• success/failure control
  • algorithm transparent if the process succeeds

  • highlighting on flow chart of the modular algorithm to identify failure

  • robust enough to skip the failed part and go to the next step if desired

07.03 | specification of data

• user to specify a sequence to go through the algorithm
  • sequence to contain the files for the system

  • SGML tags required for each text

  • language specification to be picked (English or French)

• results will be in filled templates
  • stored in a category folder

  • retrieval query method to be determined

07.04 | amount of human effort involved

• initial building of personal profile

• rule check/correction of input data
  • correction of major grammatical and spelling mistakes

  • intervention for clearing ambiguity (more in English than in French)

07.05 | guestimate of the volume of text

• 10M Bytes/person/day
  • based on today's computing capability

• computing efficiency between English and French texts
  • comparable efficiency due to 8-bit ASCII character encoding

  • the use of "unicode" will be investigated

08 | a technical rationale section

08.01 | model

• data ---> information ---> knowledge ---> intelligence

08.02 | knowledge framework

• modular algorithm
  • flexibility in language accommodation

  • context-free grammar and augmented transition network

  • portability

• knowledge packet properties and attributes
  • improvability, robustness

• grammar databases
  • rule-based databases for different kinds of words (preposition, etc.)

  • trainability, extensibility

08.03 | modular algorithm

1. sentence detection
   • spacing rules checked

2. word separation
   • spelling rules checked and standardized

   • "who's what" formatted to "(what (who))"

3. preposition identification
   • lexical unit analysis

   • based on the preposition grammar database

   • date and time extracted even without a preposition

4. proximity analysis and verb recognition
   • participle and conjugate verb formatted to "(verb (tense))"

   • infinitives and participles treated (to broaden, by making, etc.)

   • combined phrases identified (instead of, etc.)

   • conjunction identified (however, etc.)

5. packetization
   • preposition-driven extraction engine

   • sentence parsed and subject, verb, etc. assigned

   • tabulation according to properties and attributes

   • exception list generated if the process fails

6. recursive packetization and database look-up
   • knowledge soft-link created

   • parent properties and attributes inherited by child packets

   • knowledge filter and clean-up process

   • redundancy screened and removed

7. template mapping
   • knowledge extraction based on topic description database

   • determine entities (people, places, etc.) from final packets

   • determine events (who did what to whom, etc.) from final packets

08.04 | language-independence

1. sentence detection
   • language independent except for punctuation marks

2. word separation algorithm
   • English: separation of words with apostrophe, "not" in "cannot", etc.

   • French: separation of words with apostrophe

3. preposition identification
   • language-dependent lexicon/grammar databases required

4. proximity analysis and verb recognition
   • English: forward look-ahead analysis

   • French: backward look-ahead analysis

5. packetization
   • English: forward packetization

   • French: backward packetization

6. recursive packetization and database look-up
   • English: forward packetization

   • French: backward packetization

7. template mapping
   • language-dependent lexicon/grammar databases required

08.05 | domain-independence

• domain independent except for template mapping

08.06 | algorithm demonstration example (English)

1. original text

   <DOCNO>20
   <DD>05/30/90
   <SO>Financial Times
   Moscow is to broaden.collaboration with Fiat by making a version of Fiat's Panda small car instead of a new vehicle of its own design.  This means Fiat may be involved in all three phases of Soviet plans for raising output at the Yelabuga plant, 1,000 miles south-east of Moscow, by 900 units by the end of the 1990s.  The two sides agreed last November to launch a joint venture at Yelabuga to make 300,000 small cars from 1994, and to discuss output of an extra 300,000 medium-sized vehicles from 1995.
     

2. sentence detection

3. word separation

   INDEX:      ((20/1) (from 1 to 135 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   Moscow is to broaden.collaboration with Fiat by making a version of (Panda (Fiat)) small car instead of a new vehicle of its own design.
     
   
   INDEX:      ((20/2) (from 136 to 317 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   This means Fiat may be involved in all three phases of Soviet plans for raising output at the Yelabuga plant, 1,000 miles south-east of Moscow, by 900 units by the end of the 1990s.
     
   
   INDEX:      ((20/3) (from 318 to 503 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   The two sides agreed last November to launch a joint venture at Yelabuga to make 300,000 small cars from 1994, and to discuss output of an extra 300,000 medium-sized vehicles from 1995.
     

4. preposition identification

5. proximity analysis and verb recognition

   INDEX:      ((20/1) (from 1 to 135 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   Moscow is to broaden collaboration with Fiat by making a version of (Panda (Fiat)) small car instead of a new vehicle of its own design.
     
   
   INDEX:      ((20/2) (from 136 to 317 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   This means Fiat may be involved in all three phases of Soviet plans for raising output at the Yelabuga plant, 1,000 miles south-east of Moscow, by 900 units by the end of the 1990s.
     
   
   INDEX:      ((20/3) (from 318 to 503 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   The two sides agreed last November to launch a joint venture at Yelabuga to make 300,000 small cars from 1994, and to discuss output of an extra 300,000 medium-sized vehicles from 1995.
     

6. packetization

   INDEX:      ((20/1) (from 1 to 135 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   SUBJECT:    (Moscow)
   VERB:       (is)
   to:         (broaden (collaboration))
   with:       (Fiat)
   by:         (making (a version (Panda (Fiat) (small car))))
   instead of: (a new vehicle (its own design))
     
   
   INDEX:      ((20/2) (from 136 to 317 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   SUBJECT:    (This)
   VERB:       (means)
   SUBJECT:    (Fiat)
   VERB:       (may be involved)
   in:         (all three phases (Soviet plans))
   for:        (raising output)
   at:         (Yelabuga plant (1,000 miles south-east (Moscow)))
   by:         (900 units)
   by:         (the end (the 1990s))
   
   INDEX:      ((20/3) (from 318 to 503 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   SUBJECT:    (The two sides)
   VERB:       (agreed (last November))
   to:         (launch (a joint venture))
   at:         (Yelabuga)
   to:         (make (300,000 small cars))
   from:       (1994)
   to:         (discuss output (an extra 300,000 medium-sized vehicles))
   from:       (1995)
     

7. recursive packetization and database look-up

   INDEX:      ((20/1) (from 1 to 135 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   SUBJECT:    (Moscow (Soviet Union))
   VERB:       (be (present))
   WHAT:       (broaden (collaboration))
   WHOM/WITH:  (Fiat (company (Italy)))
   HOW/BY:     (make (a version (Panda (Fiat) (small car))))
   INSTEAD OF: (a new vehicle (design (@ SUBJECT/20/1)))
     
   
   INDEX:      ((20/2) (from 136 to 138 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   SUBJECT:    (@ SUBJECT/20/1)
   VERB:       (mean (present))
   WHAT:       (@ SUBJECT/20/2/1)
     
   
   INDEX:      ((20/2/1) (from 139 to 317 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   SUBJECT:    (Fiat (company (Italy)))
   VERB:       (involve (present))
   CERTAINTY:  (from 30 to 70 (%))
   HOW:        (all three phases (Soviet plans))
   WHAT:       (raise output)
   WHERE:      (Yelabuga plant (1.6M (meter) (south-east (Moscow))))
   HOW/MUCH:   (900 (units))
   WHEN/BY:    (1999)
     
   
   INDEX:      ((20/3) (from 318 to 503 Bytes))
   DATE:       (1990-05-30)
   SOURCE:     (Financial Times)
   SUBJECT:    (The two sides)
   VERB:       (agree (past) (1989-11))
   WHAT:       (launch (a joint venture))
   WHERE:      (@ Yelabuga)
   WHAT:       (make (300K (small cars)))
   WHEN/FROM:  (1994)
   WHAT:       (discuss output (an extra 300K (medium-sized vehicles)))
   WHEN/FROM:  (1995)
     

8. template mapping

   ARTICLE ID:           20
   DATE OF ARTICLE:      1990-05-30
   NEWS SOURCE:          Financial Times
   STATUS OF AGREEMENT:
   NAME OF COMPANY A:    Moscow (Soviet Union)
   NAME OF COMPANY B:    Fiat
   DATE OF AGREEMENT:    1989-11
   PRODUCT/SERVICE:      small car
   LOCATION:             Yelabuga (Soviet Union)
   % OF INVESTMENT OF A:
   % OF INVESTMENT OF B:
   START-UP DATE:        1994
   etc.
     

08.07 | knowledge packet properties and attributes

• knowledge representation in packet and compartment form
  • LISP-like structured recursive grouping syntax

  • (primary/1 (secondary/1) primary/2 (secondary/2 (tertiary/2)))

• knowledge soft-link
  • @ notation

• generic knowledge storage mechanism
  • dynamic indexing and database builder

• text rule check function
  • ambiguity identified and eliminated as much as possible

• user-specific profile
  • information filter

  • property and attribute customization

• language independent

• domain independent

08.08 | lexicon/grammar databases

• mutually exclusive lexicon/grammar databases
  • word with different meanings uniquely specified

  • multiple levels of hierarchy (personal (organizational (universal)))

  • lexical unit database

• conversion to standardized notation
  • engineering format for numbers (m, K, M, G, etc.)

  • S.I. metric format (meter, gram, etc.)

  • I.S.O. date/time format (1991-07-10T14:35:99,0-05:00 etc.)

  • normalized to Coordinated Universal Time (UTC)

  • International Monetary System

  • French numerics in Arabic format only

• knowledge database storage to have single sources
  • duplication of any kind avoided as much as possible

  • absolute indexing and addressing

• quantification of uncertainty levels
  • transformation of some descriptive words into percentage

• template specification database
  • topics of interest described

  • data translated to specified format

• essentially domain independent
  • domain dependent database subset would give shorter CPU time

08.09 | the corpora, lexicons, and grammars for algorithm development

• plan to use Oxford English Dictionary on CD-ROM
  • developed by the University of Waterloo (Ontario) Canada

• French dictionary on CD-ROM to be obtained

08.10 | example of databases

• company database

                              place           employees  revenue
                              -----           ---------  -------
  Fiat                        (Italy)         (32K)      (7.49G (ITL))
  Motorola                    (U.S.A.)        (43K)      (5.2G (USD))
  Daicel Chemical Industries  (Japan)         (1.1K)     (3.34G (JPY))
  Hoechst AG                  (West Germany)  (593)      (48K (DEM))
  Baily Controls              (Ohio (U.S.A.)) (2.7K)     (370M (USD))
    

• universal database

  me             (Go.Simon.Sunatori@+1-519-595-9210)
  mother-in-law  (Rolande.Provencher@+1-418-658-7779)
  Charles Wayne  (clwayne@vax.darpa.mil)
  Ottawa         (Ottawa (Ontario (Canada))) (UTC - 5 hours)
  Canada         (Earth (Solar System (Milky Way)))
    

• synonym/abbreviation database

  ABS/1          (acetylene butylene styrene)
  ABS/2          (anti-skid braking system)
    

• preposition database

  at             ((where) or (when (hour) or (minutes) or (second)))
  in             ((where) or (when (year) or (month)))
  on             ((where) or (when (day)))
  with           ((which) or (whom))
    

• certainty database

  never          (0 (%))
  maybe          (from 20 to 30 (%))
  perhaps        (from 20 to 30 (%))
  may be         (from 30 to 70 (%))
  probably       (from 40 to 60 (%))
  about          (from 40 to 60 (%))
  always         (from 80 to 90 (%))
  usually        (from 90 to 100 (%))
    

• conversion database

  0.001          (1m)
  1,000          (1K)
  1,000,000      (1M)
  1,000,000,000  (1G)
  YY/MM/DD       (YYYY-MM-DD)
  MMM/DD/YY      (YYYY-MM-DD)
  DD/MMM/YY      (YYYY-MM-DD)
  inch           (25.4m (meter))
  mile           (1.6K (meter))
  pound          (454 (gram))
    

• dynamically created database

  Yelabuga plant (1.6M (meter) (south-east (Moscow)))
    

08.11 | porting the algorithms to other languages

• modular nature of the algorithm allows easy porting
  • reuse language-independent algorithms

  • development of language-dependent algorithm modules

  • development of language-dependent lexicon/grammar databases

08.12 | future applications

• "integrated knowledge database system"
  • knowledge storage in SQL relational database

• Artificial Intelligence to Hypermedia/Hypertext link

• evolution path for LISP and/or PROLOG processing

• automatic knowledge equivalence comparison and consistency check

• automatic knowledge build-up, compression and archive

• sentence/speech reconstruction from knowledge source-code database

• natural language translation

09 | previous accomplishments and work in this or related area

• SAG | integrated knowledge database system

10 | a description of the facilities

10.01 | type of business

• small disadvantaged business

10.02 | company profile

• Corporate Profile

11 | key personnel

• Sunatori, Go Simon

• 100 % of Go Simon Sunatori's effort would be expended for the algorithm during 1992 and 1993 contract years

• 2 full-time researchers will be on board if the contract is awarded

12 | the qualifications of key personnel

• Sunatori, Go Simon

• speaks and writes English and French

• no major sources of support or related proposals pending elsewhere

13 | a cost breakdown

• 1991, 1992
  • capital expenditure ............................. $200K USD
    • workstation hardware resources ................ $100K USD
    • workstation software resources ................ $100K USD

  • salary ($50K USD/personnel) ..................... $150K USD

  • overhead ......................................... $50K USD

  • total (1991, 1992) .............................. $400K USD

• 1992, 1993
  • capital expenditure ............................. $200K USD
    • workstation hardware resources ................ $100K USD
    • workstation software resources ................ $100K USD

  • salary ($50K USD/personnel) ..................... $150K USD

  • overhead ......................................... $50K USD

  • total (1992, 1993) .............................. $400K USD

14 | a bibliography of relevant technical papers and research notes

• Revenue Canada Scientific Research and Experimental Development Incentive Program

Go to home page/Aller à la page d'accueil

Go to Weblog/Aller au Weblog

English / Français

Comments/Commentaire

"Sunatori, Go Simon" <GS.Sunatori@HyperInfo.CA>

[Donation/Don, SVP]

Copyright/Droit d'auteur © 1995-2024 by/par HyperInfo Canada Inc.

• All rights reserved./Tous droits réservés.
• Produced in Canada./Produit au Canada.

ISBN 978-0-929105-04-8

• 2024-12-17T20:35:59.000Z