Source: http://www.google.com/patents/US20050076037?dq=1886562
Timestamp: 2013-12-07 06:29:32
Document Index: 724977365

Matched Legal Cases: ['art 300', 'art 400', 'art 400', 'art 400', 'art 500', 'art 400', 'art 700', 'art 800', 'art 300']

Patent US20050076037 - Method and apparatus for computerized extracting of scheduling information ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsA processor is connected to a storage device storing an incoming e-mail, a dependency database, and code for a calendar application. The dependency database can be built from an e-mail corpus containing a plurality of natural language e-mails containing scheduling information. The incoming e-mail is...http://www.google.com/patents/US20050076037?utm_source=gb-gplus-sharePatent US20050076037 - Method and apparatus for computerized extracting of scheduling information from a natural language e-mailPublication numberUS20050076037 A1Publication typeApplicationApplication numberUS 10/605,500Publication dateApr 7, 2005Filing dateOct 2, 2003Priority dateOct 2, 2003Also published asCN1604102A, US7158980Publication number10605500, 605500, US 2005/0076037 A1, US 2005/076037 A1, US 20050076037 A1, US 20050076037A1, US 2005076037 A1, US 2005076037A1, US-A1-20050076037, US-A1-2005076037, US2005/0076037A1, US2005/076037A1, US20050076037 A1, US20050076037A1, US2005076037 A1, US2005076037A1InventorsCheng-Chung ShenOriginal AssigneeCheng-Chung ShenReferenced by (12), Classifications (8), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for computerized extracting of scheduling information from a natural language e-mailUS 20050076037 A1Abstract A processor is connected to a storage device storing an incoming e-mail, a dependency database, and code for a calendar application. The dependency database can be built from an e-mail corpus containing a plurality of natural language e-mails containing scheduling information. The incoming e-mail is parsed by the processor to build a dependency tree containing word pairs from the e-mail that are found in the dependency tree. The word pairs are stored as dependency pairs in a tree structure in the dependency tree. A probability sum for the dependency tree is calculated to determine if the e-mail contains scheduling information. If the probability sum exceeds a predetermined value, the e-mail is assumed to contain scheduling information and the scheduling information is extracted from the dependency tree and exported to the calendar application. Images(10) Claims(20)
DETAILED DESCRIPTION Natural human languages are both varied and complicated, however, in any text understandable by a human, all elements of the text are related in a certain way. In or der to extract scheduling information from a natural language text, it is necessary to determine candidates for the scheduling information and decide whether these candidates contain scheduling information. The assumption is that information in a natural language appears in a specific pattern for specific types of information. According to the present invention, dependency grammar is used to define a base set of possible pattern structures. Dependency grammar defines this basic structure as word pairs (dependency pairs) and constructs larger patterns (dependency trees) using these dependency pairs. Incoming E-mail messages are parsed to gather dependency pairs applicable to scheduling information and the result is a possible scheduling event. FIG. 2 shows a dependency pair diagram 200 for a sample sentence according to the present invention. According to dependency grammar, each word in a sentence has one and only one dominating head word. This forms a basic set of dependency pairs for each sentence as indicated with arrows, the arrow pointing from the head word to a dependent word. In FIG. 2, the word �meet� is the root of the sentence and is the head to �shall�, �we�, �each-other�, �at�, �tomorrow� and �2:00 PM�. If �meet� can be identified as the root of the sentence, a dependency tree can be built for the sentence showing all the decedents (tails) of the root and subsequent dependency pairs. FIG. 3 shows a flowchart 300 describing using dependency grammar rules to extract scheduling information according to the present invention. The flowchart contains the following steps: Step 302: Wait for an incoming e-mail to arrive. When a new e-mail arrives proceed to step 304. Step 304: Parse the incoming e-mail to build a dependency tree and proceed to step 306. Step 306: Determine if the e-mail contains scheduling information by calculating a probability sum for the dependency tree. Each dependency pair in the tree has an associated probability, which represents how often this particular word pair appears in natural language e-mails concerning scheduling information. If the probability sum exceeds a predetermined value then assume the e-mail contains scheduling information and proceed to step 308, otherwise return to step 302 to wait for the next incoming e-mail. Step 308: Extract the scheduling information from the dependency tree, export the scheduling information to a calendar application, and when finished, return to step 302 to wait for the next incoming e-mail. During the parsing step 302, the dependency tree does not need to contain every dependency pair from the e-mail but only the pairs relevant to scheduling information. This requires a decision to be made of whether each word pair is relevant to scheduling information. Additionally, for a given word pair, a decision must be made to determine which word is the most likely head word. In order to make these decisions, a dependency database is used as a reference. The dependency database contains a list of dependency pairs that are frequently found in a natural language e-mail corpus, and the e-mail corpus contains many e-mails containing scheduling information. Each dependency pair in the dependency database has an associated probability that corresponds to how often the particular word pair is found in the e-mail corpus. It should be noted that, in the preferred embodiment of the present invention, this probability is stored as a log-probability to facilitate adding the probabilities of different dependency pairs together. FIG. 4 shows a flowchart 400 describing how to build the dependency database using an e-mail corpus, an associated tagged corpus, a head word list, and a set of violation rules. The e-mail corpus contains a plurality of sample natural language e-mails containing scheduling information. The tagged corpus specifies actual head words for sentences relevant to scheduling information in the e-mail corpus and contains dependencies for all other words in each sentence with respect to the head words. The head word list contains possible head words, and the violation constraints specify illegal dependency structures. Examples of possible illegal dependency structures include pronouns acting as head words to verbs, or adjectives acting as head words to nouns. The e-mail corpus, tagged corpus, head word list, and violation constraints are specified in advance and provided by the system designer. Building the dependency database is described in flowchart 400 and comprises the following steps: Step 402: Start at the first sentence. Examine each sentence one by one starting with the first sentence. Proceed to step 404. Step 404: Segment the sentence into words. Some languages use a base element other than words. For example, the Chinese language uses characters, and these characters must be grouped into words having meaning. This grouping is referred to as segmenting. Additionally, even in English, some words need to be paired with other words to form a proper meaning. For example, in FIG. 2, the word �each-other� is actually the words �each� and �other� grouped together to form a single word. As segmenting is well known to people skilled in the art, further description is hereby omitted. If segmenting is not required, step 404 can be removed from the flowchart 400, otherwise proceed to step 406 when finished. Step 406: Build word pairs for the sentence. Make a list of all combinations of words in the sentence. Proceed to step 408. Step 408: Start at the first word pair. Examine each word pair one by one starting with the first word pair. Proceed to step 410. Step 410: Does the word pair occur frequently in the e-mail corpus? If yes then proceed to step 412, otherwise skip to step 418. Step 412: Determine the head word. Check the head word list and the tagged corpus to determine which word in the word pair should be designated the head word. Proceed to step 414. Step 414: Is the resulting word pair structure a valid dependency pair? Use the violation rules to determine if the syntax of the word pair is allowable. Additionally check the dependency database to ensure the word pair is not already included in the dependency database and to determine if this word pair structure should be added as a new dependency pair, e.g. this word pair fits with an existing dependency tree in the dependency database. If the word pair is a new and valid dependency pair then proceed to step 416, otherwise skip to step 418. Step 416: Add the word pair as a dependency pair to the dependency database and proceed to step 418. Step 418: Are the word pairs finished? If yes then proceed to step 422, otherwise proceed to step 420. Step 420: Examine the next word pair and proceed to step 410. Step 422: Are the sentences finished? If yes then proceed to step 426, otherwise proceed to step 424. Step 424: Examine the next sentence and proceed to step 404. Step 426: Was at least one new dependency pair added to the dependency database? If no then the dependency database is finished being built, otherwise repeat the procedure to look for next level dependency pairs by returning to step 402. FIG. 5 is a flowchart 500 describing the parsing step 304 of FIG. 3. Once the dependency database is built using the flowchart 400 shown in FIG. 4, the parsing step 304 of FIG. 3 can be broken down into the following steps: Step 502: Start at the first sentence. Examine each sentence one by one starting with the first sentence. Proceed to step 504. Step 504: Segment the sentence into words. This step is the same as step 404 in FIG. 4 and can similarly be omitted if not required. Proceed to step 506 when finished. Step 506: Build a head word list. Use the dependency database to make a list of all words in the sentence that are possible head words. Proceed to step 508. Step 508: Start at the first possible head word. Examine each head word one by one starting with the first possible head word. Proceed to step 510. Step 510: Build word pairs for the sentence. Make a list of all two-word combinations of words in the sentence. Proceed to step 512. Step 512: Start at the first word pair. Examine each word pair one by one starting with the first word pair. Proceed to step 514. Step 514: Is the word pair in the dependency database? If yes then proceed to step 516, otherwise skip to step 518. Step 516: Add the word pair as a dependency pair to the dependency tree. Proceed to step 518. Step 518: Are the word pairs finished? If yes then proceed to step 520, otherwise proceed to step 524. Step 520: Examine the next word pair, and proceed to step 514. Step 522: Are the possible head words finished? If yes then proceed to step 526, otherwise proceed to step 524. Step 524: Examine the next possible head word and proceed to step 508. Step 526: Are the sentences finished? If yes then the parsing procedure is finished so proceed to step 306 in FIG. 3, if not then proceed to step 528. Step 528: Examine the next sentence and proceed to step 504. FIG. 6 shows a dependency tree 600 for the e-mail 100 of FIG. 1 resulting from the parsing steps described in FIG. 5. Because there are multiple scheduling events contained in the same e-mail 100, there are actually five sub-trees 602, 604, 606, 608, and 610 listed in the dependency tree 600, and each sub-tree contains only the dependency pairs that relate to scheduling information as determined from the dependency database. The first sub-tree 602 is based on the root word �reserved�, the second sub-tree 604 is based on the root word �finish�, the third sub-tree 606 is based on the root word �review�, the fourth sub-tree 608 is based on the root word �rehearsal�, and the fifth sub-tree 610 is based on the root word �meet�. FIG. 7 shows a flowchart 700 describing the determining if the e-mail contains scheduling information step 306 of FIG. 3 and contains the following steps: Step 702: Sum the log-probability of the dependency tree and proceed to step 704. Step 704: Is the log-probability sum greater than a predetermined value? If yes then assume the e-mail contains scheduling information and proceed to step 308 for extraction. If the log-probability sum is not greater than the predetermined value then assume the e-mail is unrelated to scheduling information and return to step 302 to wait for the next incoming e-mail. FIG. 8 shows a flowchart 800 describing the extract scheduling information step 308 of FIG. 3 and contains the following steps: Step 802: Start at the first dependency sub-tree in the dependency tree. Each sub-tree in the dependency tree contains scheduling information for a particular event so extract the scheduling information one by one starting with the first sub-tree. Proceed to step 804. Step 804: Start at the first dependency pair. Examine each dependency pair one by one starting with the first dependency pair. Proceed to step 806. Step 806: Does the category match a predetermined scheduling type? If yes then proceed to step 808, otherwise skip to step 812. Step 808: Compute a scheduling value according to the scheduling type and proceed to step 810. Step 810: Register the scheduling value with the application specific format required by the calendar application in an add list and proceed to step 812. Step 812: Are the word pairs finished? If yes then proceed to step 816, otherwise proceed to step 814. Step 814: Examine the next word pair and proceed to step 806. Step 816: Are the dependency sub-trees finished? If yes then proceed to step 820, otherwise proceed to step 818. Step 818: Examine the next dependency sub-tree and proceed to step 804. Step 820: Confirm the add list with the user. The user may want to modify the scheduling information in the add list before it is export to the calendar application. When the information in the add list is confirmed by the user, proceed to step 822. Step 822: Export the scheduling information contained in the add list to the calendar application. When finished, return to step 302 to wait for the next incoming e-mail. FIG. 9 shows a block diagram of a personal organization apparatus 900 for implementing the flowchart 300 of FIG. 3. A personal organization apparatus includes electronic devices that assist with scheduling and can include such devices as desktop computers, laptops computers, notebooks, personal digital assistants (PDAs), and cell phones. The personal organization apparatus 900 includes a processor 902 and a storage unit 904 connected to the processor. The storage unit 904 provides storage capability for an incoming e-mail 906, a dependency database 910, and code for a calendar application 914. Optionally, a natural language e-mail corpus 912 can also be stored in the storage unit to allow the personal organization apparatus 900 to build the dependency database 910. Additionally, a user interface 916 and a network interface 918 are connected to the processor for interfacing with a user and for receiving the incoming e-mail 906 respectively. The storage unit 904 can be implemented with a memory device such as a RAM, a storage device such as magnetic or optical media, or a combination of different types of memory and storage devices. A natural language e-mail 906 is received from the network interface 918 and stored in the storage unit 904 by the processor 902. The e-mail 906 is parsed by the processor 902 to build the dependency tree 920. The dependency tree 920 contains word pairs from the e-mail 906 that are found in the dependency database 910, and the word pairs are stored as dependency pairs in a tree structure in the dependency tree 920. Each sub-tree in the dependency tree 920 deals with word pairs that are dependent on a common root head word. For most scheduling e-mails, this means each sub-tree contains information particular to a particular scheduling event. When all the word pairs in the e-mail 906 have been checked, the processor 902 sums a log probability of the dependency pairs in the dependency tree 920. Each dependency pair has an associated probability value also stored (preferable in log probability form) in the dependency tree, the probability value corresponding to how frequently this particular word pair was found in the e-mail corpus 912. More frequently appearing word pairs are given higher probability of indicating whether or not the e-mail 906 contains scheduling information. If the log probability sum is higher than a predetermined value, the e-mail 906 is assumed to contain scheduling information. In this case the processor 902 extracts the scheduling information by recursively checking each dependency pair in each sub-tree of the dependency tree 920. For each dependency pair, the processor 902 checks to see if the dependency pair matches a scheduling category that needs conversion to a scheduling value. Examples of such values are words like �tomorrow�, or �next week�. Depending on the date of the e-mail, these words need to be converted to an actual date. Next, the processor 902 registers the value of the dependency pair with the format specific requirements for the calendar application 914. For example, if the dependency pairs are stored in the form (head, tail), given required calendar application 914 parameters of PERSON, PLACE, TIME, SUBJECT, the dependency pairs of FIG. 6 could be grouped and processed as follows: (reserved, schedule) (reserved, room)->PLACE=room (room, video-conference)->PLACE=video-conference room (finish, 6/18)->TIME=6/18 (finish, material)->SUBJECT=finish material (review, 6/23 15:00-1700)->TIME=6/23 15:00-1700 (review, material)->SUBJECT=review material (rehearsal, 06/25 10:00-12:00)->TIME=6/25 10:00-12:00 (rehearsal, the)->SUBJECT=the rehearsal (rehearsal, first)->SUBJECT=the first rehearsal (meet, tomorrow)->TIME=06/14 (meet, go-over)->SUBJECT=go-over (go-over, material)->SUBJECT=go-over material (meet, in-person)->PERSON=Nancy When each dependency pair for each sub-tree in the dependency tree 920 has been registered in an add list, the list can be confirmed with the user using the user interface 916. The user is presented with the prospective add list and given an opportunity to modify the scheduling information contained in the add list. For example, the user may wish to change the time for a meeting to an earlier time to prevent tardiness. Once confirmed by the user, the processor 902 exports the add list to the calendar application 914 using the proprietary format of the particular calendar application 914. The processor 902 may also be required to confirm the calendar application 914 is ready to receive the new scheduling information and may need to send a confirmation message to the calendar application 914. Additionally, it should be noted that using dependency grammar rules, the processor 902 could build the dependency database 910 using the plurality of natural language e-mails containing scheduling information stored in the e-mail corpus 912. In contrast to the prior art, the method and apparatus for computerized extracting of scheduling information according to the present invention can extract scheduling information from a natural language e-mail and export the extracted scheduling information to a calendar application. Dependency grammar rules are used to specifically identify and connect the words of each sentence having to do with scheduling information. The scheduling information is extracted by recursively examining word pairs having to do with the scheduling information contained in the e-mail. Additionally, although the previous detailed description deals specifically with natural language e-mails, the same method and apparatus could be directly used for any natural language texts. Those skilled in the art will readily observe that numerous modifications and alterations of the device may be made while retaining the teachings of the invention. Accordingly, that above disclosure should be construed as limited only by the metes and bounds of the appended claims. Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7669138 *Oct 27, 2006Feb 23, 2010Liaise, Inc.Interacting with a computer-based management systemUS7970600Nov 3, 2004Jun 28, 2011Microsoft CorporationUsing a first natural language parser to train a second parserUS8055707 *Nov 30, 2005Nov 8, 2011Alcatel LucentCalendar interface for digital communicationsUS8065362 *Mar 8, 2007Nov 22, 2011Promptalert Inc.System and method for processing and updating event related information using automated remindersUS8219599Oct 17, 2011Jul 10, 2012True Knowledge LimitedKnowledge storage and retrieval system and methodUS8397263 *Feb 29, 2008Mar 12, 2013Sony CorporationInformation processing apparatus, information processing method and information processing programUS8468122Nov 12, 2008Jun 18, 2013Evi Technologies LimitedKnowledge storage and retrieval system and methodUS20100017367 *Jun 21, 2006Jan 21, 2010Mikko NurmiAccessing Data Associated with One Application from Another ApplicationUS20100325227 *Jun 22, 2010Dec 23, 2010Alon NovySystems and methods for composite data messageUS20120271676 *Apr 24, 2012Oct 25, 2012Murali AravamudanSystem and method for an intelligent personal timeline assistantEP2461283A1 *Nov 4, 2011Jun 6, 2012Sony Ericsson Mobile Communications ABCalendar event creation using electronic message conversationsWO2007051227A1 *Oct 27, 2006May 10, 2007Alon R J NovyInteracting with a computer-based management system* Cited by examinerClassifications U.S. Classification1/1, 707/999.1International ClassificationG06Q10/00, G06F17/00, G06F17/30Cooperative ClassificationY10S707/99943, G06Q10/107European ClassificationG06Q10/107Legal EventsDateCodeEventDescriptionJun 16, 2010FPAYFee paymentYear of fee payment: 4Oct 2, 2003ASAssignmentOwner name: ACER INCORPORATED, TAIWANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:SHEN, CHENG-CHUNG;REEL/FRAME:014021/0507Effective date: 20030826RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google