A content reference identifier or CRID is a concept from the standardization work done by the TV-Anytime forum. It is or closely matches the concept of the Uniform Resource Locator, or URL, as used on the World-Wide Web: A unit of content, in a broadcast stream, can be referred to by its globally unique CRID in the same way that a webpage can be referred to by its globally unique URL on the web. The concept of CRID permits referencing contents unambiguously, regardless of their location, i.e., without knowing specific broadcast information (time, date and channel) or how to obtain them through a network, for instance, by means of a streaming service or by downloading a file from an Internet server. The receiver must be capable of resolving these unambiguous references, i.e. of translating them into specific data that will allow it to obtain the location of that content in order to acquire it. This makes it possible for recording processes to take place without knowing that information, and even without knowing beforehand the duration of the content to be recorded: a complete series by a simple click, a program that has not been scheduled yet, a set of programs grouped by a specific criterion... This framework allows for the separation between the reference to a given content (the CRID) and the necessary information to acquire it, which is called a “locator”. Each CRID may lead to one or more locators which will represent different copies of the same content. They may be identical copies broadcast in different channels or dates, or cost different prices. They may also be distinct copies with different technical parameters such as format or quality. It may also be the case that the resolution process of a CRID provides another CRID as a result (for example, its reference in a different network, where it has an alternative identifier assigned by a different operator) or a set of CRIDs (for instance, if the original CRID represents a TV series, in which case the resolution process would result in the list of CRIDs representing each episode). From the above it can be concluded that provided that a given content can belong to many groups (each possibly defined by distinctive qualities), it is possible that many CRIDs carry the same content. That is, several CRIDs may be resolved into the same locator. A CRID is not exactly a universal, unique and exclusive identifier for a given content. It is closely related to the authority that creates it, to the resolution service provider, and to the content provider in such a way that the same content may have different CRIDs depending on the field in which they are used (for example, a different one for each television operator that has the rights to broadcast the content). == Format == A CRID is specified much like URLs. In fact, a CRID is a so-called URI. Typically, the content creator, the broadcaster or a third party will use their DNS-names in a combination with a product-specific name to create globally unique CRIDs. That is, the syntax of a CRID is: crid://authority/data The authority field represents the entity that created the CRID and its format is that of a DNS name. The data field represents a string of characters that will unambiguously identify the content within the authority scope (it is a string of characters assigned by the authority itself). As an example, let's assume that BBC wanted to make a CRID for (all the programs of) the Olympics in China. It may have looked something like this crid://bbc.co.uk/olympics/2008/ This would be a group CRID, that is, a CRID representing a group of contents. Then, to refer to a specific event – such as the women's shot-put final – they could have used the following inside their metadata. crid://bbc.co.uk/olympics/2008/final/shotput/women Currently, four types of CRIDs are playing a major role in some unidirectional television networks: programme CRID, series CRID, group CRID, and recommendation CRID. One of the most important applications of CRIDs is the so-called series link recording function (SL) of modern digital video recorders (DVR, PVR). In turn, a locator is a string of characters that contains all the necessary information for a receiver to find and acquire a given content, whether it is received through a transport stream, located in local storage, downloaded as a file from an Internet server, or through a streaming service. For example, a DVB locator will include all the necessary parameters to identify a specific content within a transport stream: network, transport stream, service, table and/or event identifiers. The locators' format, as established in TV-Anytime, is quite generic and simple, and corresponds to: [transport-mechanism]:[specific-data] The first part of the locator's format (the transport mechanism) must be a string of characters that is unique for each mechanism (transport stream, local file, HTTP Internet access...). The second part must be unambiguous only within the scope of a given transport mechanism and will be standardized by the organism in charge of the regulation of the mechanism itself. For instance, a DVB locator to identify a content within the transport stream of networks that follow this standard would be: dvb://112.4a2.5ec;2d22~20121212T220000Z—PT01H30M which would indicate a content (identified by the string “2d22”) that airs on a channel available on a DVB network identified by the address “112.4a2.5ec” (network “112”, transport stream “4a2” and service “5ec”), on 12 December 2012 at 10 p.m. and with a duration of 90 minutes. == The location resolution process == The location resolution process is the procedure by which, starting from the CRID of a given content, one or several locators of that content are obtained. Resolving a CRID can be a direct process, which leads immediately to one or many locators, or it may also happen that in the first place one or many intermediate CRIDs are returned, which must undergo the same procedure to finally obtain one or several locators. This procedure involves some information elements, among which we find two structures named resolving authority record (RAR) and ContentReferencingTable, respectively. Consulting them repeatedly will take the receiver from a CRID to one or many locators that will allow it to acquire the content. The RAR table The RAR table is one or many data structures that provide the receiver, for each authority that submits CRIDs, information on the corresponding resolution service provider. Among other things, it informs about which mechanism is used to provide information to resolve the CRIDs from each authority. That is, one or many RAR records must exist for each authority that indicate the receiver where it has to go to resolve the CRIDs of that particular authority. For example, in the record of the figure (expressed by means of a XML structure, according to the XML Schema defined in the TV-Anytime) there is an authority called “tve.es”, whose resolution service provider is the entity “rtve.es”, available on the URL "http://tva.rtve.es/locres/tve", which means there is resolution information in that URL. These RAR records will have reached the receiver in an indefinite form, unimportant for the TV-Anytime specification, which will depend on the specific transport mechanism of the network to which the receiver is connected. Each family of standards that regulates distribution networks (DVB, ATSC, ISDB, IPTV...) will have previously defined such procedure, which will be used by devices certified according to those standards. The ContentReferencingTable table The second structure involved in the location resolution process is a proper resolution table which, given a content's CRID, returns one or several locators that enable the receiver to access an instance of that content, or one or many CRIDs that allow it to move forward in the resolution process. The figure shows an example of this second structure, an XML document according to the specifications of the XML Schema defined in TV-Anytime. In it, several sections are included (
Image translation
Image translation is the machine translation of images of printed text (posters, banners, menus, screenshots etc.). This is done by applying optical character recognition (OCR) technology to an image to extract any text contained in the image, and then have this text translated into a language of their choice, and the applying digital image processing on the original image to get the translated image with a new language. == General == Machine translation made available on the internet (web and mobile) is a notable advance in multilingual communication eliminating the need for an intermediary translator/interpreter, translating foreign texts still poses a problem to the user as they cannot be expected to be able to type the foreign text they wish to translate and understand. Manually entering the foreign text may prove to be a difficulty especially in cases where an unfamiliar alphabet is used from a script which user can't read, e.g. Cyrillic, Chinese, Japanese etc. for an English speaker or any speaker of a Latin-based language or vice versa. The technical advancements in OCR made it possible to recognize text from images. The possibility to use one's mobile device's camera to capture and extract printed text is also known as mobile OCR and was first introduced in Japanese manufactured mobile telephones in 2004. Using the handheld's camera one could take a picture of (a line of) text and have it extracted (digitalized) for further manipulation such as storing the information in their contacts list, as a web page address (URL) or text to use in an SMS/email message etc. Presently, mobile devices having a camera resolution of 2 megapixels or above with an auto-focus ability, often feature the text scanner service. Taking the text scanning facility one step further, image translation emerged, giving users the ability to capture text with their mobile phone's camera, extract the text, and have it translated in their own language. More and more applications emerged on this technology including Word Lens. After getting acquired by Google, it was made a part of Google Translate mobile app. Another simultaneous advancement in Image Processing, has also made it possible now to replace the text on the image with the translated text and create a new image altogether. == History == The development of the image translation service springs from the advances in OCR technology (miniaturization and reduction of memory resources consumed) enabling text scanning on mobile telephones. Among the first to announce mobile software capable of “reading” text using the mobile device's camera is International Wireless Inc. who in February 2003 released their “CheckPoint” and “WebPoint” applications. “CheckPoint” reads critical symbolic information on checks and is aimed at reducing losses that mobile merchants suffer from “bounced” checks by scanning the MICR number on the bottom of a check, while “WebPoint” enables the visual recognition and decoding of printed URL's, which are then opened by the device's web browser. The first commercial release of a mobile text scanner, however, took place in December 2004 when Vodafone and Sharp began selling the 902SH mobile which was the first to feature a 2 megapixel digital camera with optical zoom. Among the device's various multimedia features was the built-in text/bar code/QR code scanner. The text scanner function could handle up to 60 alphabetical characters simultaneously. The scanned text could be then sent as an email or SMS message, added as a dictionary entry or, in the case of scanned URLs, opened via the device's web browser. All subsequent Sharp mobiles feature the text scanner functionality. In September 2005, NEC Corporation and the Nara Institute of Science and Technology in Japan (NAIST) announced new software capable of transforming cameraphones into text scanners. The application differs substantially from similarly equipped mobile telephones in Japan (able to scan businesscards and small bits of text and use OCR to convert that to editable text or to URL addresses) by it ability to scan a whole page. The two companies, however, said they would not release the software commercially before the end of 2008. Combining the text scanner function with machine translation technology was first made by US company RantNetwork who in July 2007 started selling the Communilator, a machine translation application for mobile devices featuring the Image Translation functionality. Using the built-in camera, the mobile user could take a picture of some printed text, apply OCR to recognize the text and then translate it into any one of over 25 language available. In April 2008 Nokia showcased their Shoot-to-Translate application for the N73 model which is capable of taking a picture using the device's camera, extracting the text and then translating it. The application only offers Chinese to English translation, and does not handle large segments of text. Nokia said they are in the process of developing their Multiscanner product which, besides scanning text and business cards, would be able to translate between 52 languages. Again in April 2008, Korean company Unichal Inc. released their handheld Dixau text scanner capable of scanning and recognizing English text and then translating it into Korean using online translation tools such as Wikipedia or Google Translate. The device is connected to a PC or a laptop via the USB port. In February 2009, Bulgarian company Interlecta presented at the Mobile World Congress in Barcelona their mobile translator including image recognition and speech synthesis. The application handles all European languages along with Chinese, Japanese and Korean. The software connects to a server over the Internet to accomplish the image recognition and the translation. In May 2014, Google acquired Word Lens to improve the quality of visual and voice translation. It is able to scan text or picture with one's device and have it translated instantly. Since the OCR has been improving many companies or website started combining OCR and translation, to read the text from an image and show the translated text. In August 2018, an Indian company created ImageTranslate. It is able to read, translate and re-create the image in another language. As of late 2018, the tool added 13 new languages, including Arabic, Thai, Vietnamese, Hindi, and Bengali, significantly increasing its utility in Asia and the Middle East. This helps users translate photos already stored in their phone's gallery, not just live, real-time views. Currently, image translation is offered by the following companies: Google Translate app with camera ImageTranslate Yandex
Cristóbal Valenzuela
Cristóbal Valenzuela (born 1989) is a Chilean-born technologist, software developer, and CEO of Runway. In 2018, Valenzuela co-founded the AI research company Runway in New York City with Anastasis Germanidis and Alejandro Matamala. == Education == Valenzuela graduated from Adolfo Ibáñez University (AIU), a research private university in Chile. From there, Valenzuela obtained a bachelor's degree in economics and business management, along with a master's degree in arts in design in 2012. In 2018, he graduated with a media arts degree from ITP NYU's Tisch School of the Arts. == Career and recognition == One of Valenzuela's first jobs was as a teaching and research assistant at the Adolfo Ibáñez University School of Design, and later an adjunct professor in the same department. In 2018, he became a researcher at NYU's Tisch School of the Arts ITP program, where he worked with Daniel Shiffman. He contributes to open-source software projects, including ml5.js, an open-source machine learning software. He co-founded Runway with two colleagues from ITP, Anastasis Germanidis, and Alejandro Matamala. The goal of Runway is to create new tools for human imagination using generative AI. In recent years, Valenzuela's work has been sponsored by Google and the Processing Foundation and his projects have been exhibited throughout Latin America and the US, including the Santiago Museum of Contemporary Art, Lollapalooza, NYC Media Lab, New Latin Wave, Inter-American Development Bank, Stanford University and New York University. In September 2023, Valenzuela was named as one of the TIME 100 Most Influential People in AI (TIME100 AI).
Partial-order planning
Partial-order planning is an approach to automated planning that maintains a partial ordering between actions and only commits ordering between actions when forced to, that is, ordering of actions is partial. Also this planning doesn't specify which action will come out first when two actions are processed. By contrast, total-order planning maintains a total ordering between all actions at every stage of planning. Given a problem in which some sequence of actions is needed to achieve a goal, a partial-order plan specifies all actions that must be taken, but specifies an ordering between actions only where needed. Consider the following situation: a person must travel from the start to the end of an obstacle course. The course is composed of a bridge, a see-saw, and a swing-set. The bridge must be traversed before the see-saw and swing-set are reachable. Once reachable, the see-saw and swing-set can be traversed in any order, after which the end is reachable. In a partial-order plan, ordering between these obstacles is specified only when needed. The bridge must be traversed first. Second, either the see-saw or swing-set can be traversed. Third, the remaining obstacle can be traversed. Then the end can be traversed. Partial-order planning relies upon the principle of least commitment for its efficiency. == Partial-order plan == A partial-order plan or partial plan is a plan which specifies all actions that must be taken, but only specifies the order between actions when needed. It is the result of a partial-order planner. A partial-order plan consists of four components: A set of actions (also known as operators). A partial order for the actions. It specifies the conditions about the order of some actions. A set of causal links. It specifies which actions meet which preconditions of other actions. Alternatively, a set of bindings between the variables in actions. A set of open preconditions. It specifies which preconditions are not fulfilled by any action in the partial-order plan. To keep the possible orders of the actions as open as possible, the set of order conditions and causal links must be as small as possible. A plan is a solution if the set of open preconditions is empty. A linearization of a partial order plan is a total order plan derived from the particular partial order plan; in other words, both order plans consist of the same actions, with the order in the linearization being a linear extension of the partial order in the original partial order plan. === Example === For example, a plan for baking a cake might start: go to the store get eggs; get flour; get milk pay for all goods go to the kitchen This is a partial plan because the order for finding eggs, flour and milk is not specified, the agent can wander around the store reactively accumulating all the items on its shopping list until the list is complete. == Partial-order planner == A partial-order planner is an algorithm or program which will construct a partial-order plan and search for a solution. The input is the problem description, consisting of descriptions of the initial state, the goal and possible actions. The problem can be interpreted as a search problem where the set of possible partial-order plans is the search space. The initial state would be the plan with the open preconditions equal to the goal conditions. The final state would be any plan with no open preconditions, i.e. a solution. The initial state is the starting conditions, and can be thought of as the preconditions to the task at hand. For a task of setting the table, the initial state could be a clear table. The goal is simply the final action that needs to be accomplished, for example setting the table. The operators of the algorithm are the actions by which the task is accomplished. For this example there may be two operators: lay (tablecloth), and place (glasses, plates, and silverware). === Plan space === The plan space of the algorithm is constrained between its start and finish. The algorithm starts, producing the initial state and finishes when all parts of the goal have been achieved. In the setting a table example, two types of actions exist that must be addressed: the put-out and lay operators. Four unsolved operators also exist: Action 1, lay-tablecloth, Action 2, Put-out (plates), Action 3, Put-out (silverware), and Action 4, Put-out (glasses). However, a threat arises if Action 2, 3, or 4 comes before Action 1. This threat is that the precondition to the start of the algorithm will be unsatisfied as the table will no longer be clear. Thus, constraints exist that must be added to the algorithm that force Actions 2, 3, and 4 to come after Action 1. Once these steps are completed, the algorithm will finish and the goal will have been completed. === Threats === As seen in the algorithm presented above, partial-order planning can encounter certain threats, meaning orderings that threaten to break connected actions, thus potentially destroying the entire plan. There are two ways to resolve threats: Promotion Demotion Promotion orders the possible threat after the connection it threatens. Demotion orders the possible threat before the connection it threatens. Partial-order planning algorithms are known for being both sound and complete, with sound being defined as the total ordering of the algorithm, and complete being defined as the capability to find a solution, given that a solution does in fact exist. == Partial-order vs. total-order planning == Partial-order planning is the opposite of total-order planning, in which actions are sequenced all at once and for the entirety of the task at hand. The question arises when one has two competing processes, which one is better? Anthony Barret and Daniel Weld have argued in their 1993 book, that partial-order planning is superior to total-order planning, as it is faster and thus more efficient. They tested this theory using Korf’s taxonomy of subgoal collections, in which they found that partial-order planning performs better because it produces more trivial serializability than total-order planning. Trivial serializability facilitates a planner’s ability to perform quickly when dealing with goals that contain subgoals. Planners perform more slowly when dealing with laboriously serializable or nonserializable subgoals. The determining factor that makes a subgoal trivially or laboriously serializable is the search space of different plans. They found that partial-order planning is more adept at finding the quickest path, and is therefore the more efficient of these two main types of planning. == The Sussman anomaly == Partial-order plans are known to easily and optimally solve the Sussman anomaly. Using this type of incremental planning system solves this problem quickly and efficiently. This was a result of partial-order planning that solidified its place as an efficient planning system. == Disadvantages to partial-order planning == One drawback of this type of planning system is that it requires a lot more computational power for each node. This higher per-node cost occurs because the algorithm for partial-order planning is more complex than others. This has important artificial intelligence implications. When coding a robot to do a certain task, the creator needs to take into account how much energy is needed. Though a partial-order plan may be quicker it may not be worth the energy cost for the robot. The creator must be aware of and weigh these two options to build an efficient robot.
Historical Thesaurus of English
The Historical Thesaurus of English (HTE) is the largest thesaurus in the world. It is called a historical thesaurus as it arranges the whole vocabulary of English, from the earliest written records in Old English to the present, according to the first documented occurrence of a word in the entire history of the English language. The HTE was conceived and begun in 1965 by the English Language & Linguistics department of the University of Glasgow, who have ever since continued to compile the thesaurus. From the 1980s onwards the project was moved from paper-based records to a computer database. Today, the HTE is available to the public online, but a print version, the Historical Thesaurus of the Oxford English Dictionary (HTOED), was published in 2009. == Main project: The Historical Thesaurus of English (HTE) == The Historical Thesaurus of English (HTE) is a complete database of all the words in the Oxford English Dictionary and other dictionaries (including Old English), arranged by semantic field and date. In this way, the HTE arranges the whole vocabulary of English, from the earliest written records in Old English to the present, alongside dates of use. It is the first historical thesaurus to be compiled for any of the world's languages and contains 800,000 meanings for 600,000 words, within 230,000 categories. As the HTE website states, "in addition to providing hitherto unavailable information for linguistic and textual scholars, the Historical Thesaurus online is a rich resource for students of social and cultural history, showing how concepts developed through the words that refer to them." === Structure === The work is divided into three main sections: the External World, the Mind, and Society. These are broken down into successively narrower domains. The text eventually discriminates more than 236,000 categories. The second order categories are: === History === The ambitious project was announced at a 1965 meeting of the Philological Society by its originator, Michael Samuels. Work on the HTE started in the same year. In 2017, the University of Glasgow was awarded the Queen's Anniversary Prize for Higher Education for the HTE. A second edition of the online HTE is currently in progress and is expected to be launched in late 2020. Work is released on the freely-available HTE website when available. == Print edition: Historical Thesaurus of the Oxford English Dictionary (HTOED) == On 22 October 2009, after 44 years of work, version 1.0 of the HTE was published by Oxford University Press in a two-volume slipcased set as the Historical Thesaurus of the Oxford English Dictionary (HTOED). The two hardcover volumes together total nearly 4,500 pages.
Rule-based machine translation
Rule-based machine translation (RBMT) is a classical approach of machine translation systems based on linguistic information about source and target languages. Such information is retrieved from (unilingual, bilingual or multilingual) dictionaries and grammars covering the main semantic, morphological, and syntactic regularities of each language. Having input sentences, an RBMT system generates output sentences on the basis of analysis of both the source and the target languages involved. RBMT has been progressively superseded by more efficient methods, particularly neural machine translation. == History == The first RBMT systems were developed in the early 1970s. The most important steps of this evolution were the emergence of the following RBMT systems: Systran Japanese MT systems Today, other common RBMT systems include: Apertium GramTrans == Types of RBMT == There are three different types of rule-based machine translation systems: Direct Systems (Dictionary Based Machine Translation) map input to output with basic rules. Transfer RBMT Systems (Transfer Based Machine Translation) employ morphological and syntactical analysis. Interlingual RBMT Systems (Interlingua) use an abstract meaning. RBMT systems can also be characterized as the systems opposite to Example-based Systems of Machine Translation (Example Based Machine Translation), whereas Hybrid Machine Translations Systems make use of many principles derived from RBMT. == Basic principles == The main approach of RBMT systems is based on linking the structure of the given input sentence with the structure of the demanded output sentence, necessarily preserving their unique meaning. The following example can illustrate the general frame of RBMT: A girl eats an apple. Source Language = English; Demanded Target Language = German Minimally, to get a German translation of this English sentence one needs: A dictionary that will map each English word to an appropriate German word. Rules representing regular English sentence structure. Rules representing regular German sentence structure. And finally, we need rules according to which one can relate these two structures together. Accordingly, we can state the following stages of translation: 1st: getting basic part-of-speech information of each source word: a = indef.article; girl = noun; eats = verb; an = indef.article; apple = noun 2nd: getting syntactic information about the verb "to eat": NP-eat-NP; here: eat – Present Simple, 3rd Person Singular, Active Voice 3rd: parsing the source sentence: (NP an apple) = the object of eat Often only partial parsing is sufficient to get to the syntactic structure of the source sentence and to map it onto the structure of the target sentence. 4th: translate English words into German a (category = indef.article) => ein (category = indef.article) girl (category = noun) => Mädchen (category = noun) eat (category = verb) => essen (category = verb) an (category = indef. article) => ein (category = indef.article) apple (category = noun) => Apfel (category = noun) 5th: Mapping dictionary entries into appropriate inflected forms (final generation): A girl eats an apple. => Ein Mädchen isst einen Apfel. == Ontologies == An ontology is a formal representation of knowledge that includes the concepts (such as objects, processes etc.) in a domain and some relations between them. If the stored information is of linguistic nature, one can speak of a lexicon. In NLP, ontologies can be used as a source of knowledge for machine translation systems. With access to a large knowledge base, rule-based systems can be enabled to resolve many (especially lexical) ambiguities on their own. In the following classic examples, as humans, we are able to interpret the prepositional phrase according to the context because we use our world knowledge, stored in our lexicons:I saw a man/star/molecule with a microscope/telescope/binoculars.Since the syntax does not change, a traditional rule-based machine translation system may not be able to differentiate between the meanings. With a large enough ontology as a source of knowledge however, the possible interpretations of ambiguous words in a specific context can be reduced. === Building ontologies === The ontology generated for the PANGLOSS knowledge-based machine translation system in 1993 may serve as an example of how an ontology for NLP purposes can be compiled: A large-scale ontology is necessary to help parsing in the active modules of the machine translation system. In the PANGLOSS example, about 50,000 nodes were intended to be subsumed under the smaller, manually-built upper (abstract) region of the ontology. Because of its size, it had to be created automatically. The goal was to merge the two resources LDOCE online and WordNet to combine the benefits of both: concise definitions from Longman, and semantic relations allowing for semi-automatic taxonomization to the ontology from WordNet. A definition match algorithm was created to automatically merge the correct meanings of ambiguous words between the two online resources, based on the words that the definitions of those meanings have in common in LDOCE and WordNet. Using a similarity matrix, the algorithm delivered matches between meanings including a confidence factor. This algorithm alone, however, did not match all meanings correctly on its own. A second hierarchy match algorithm was therefore created which uses the taxonomic hierarchies found in WordNet (deep hierarchies) and partially in LDOCE (flat hierarchies). This works by first matching unambiguous meanings, then limiting the search space to only the respective ancestors and descendants of those matched meanings. Thus, the algorithm matched locally unambiguous meanings (for instance, while the word seal as such is ambiguous, there is only one meaning of seal in the animal subhierarchy). Both algorithms complemented each other and helped constructing a large-scale ontology for the machine translation system. The WordNet hierarchies, coupled with the matching definitions of LDOCE, were subordinated to the ontology's upper region. As a result, the PANGLOSS MT system was able to make use of this knowledge base, mainly in its generation element. == Components == The RBMT system contains: a SL morphological analyser - analyses a source language word and provides the morphological information; a SL parser - is a syntax analyser which analyses source language sentences; a translator - used to translate a source language word into the target language; a TL morphological generator - works as a generator of appropriate target language words for the given grammatica information; a TL parser - works as a composer of suitable target language sentences; Several dictionaries - more specifically a minimum of three dictionaries: a SL dictionary - needed by the source language morphological analyser for morphological analysis, a bilingual dictionary - used by the translator to translate source language words into target language words, a TL dictionary - needed by the target language morphological generator to generate target language words. The RBMT system makes use of the following: a Source Grammar for the input language which builds syntactic constructions from input sentences; a Source Lexicon which captures all of the allowable vocabulary in the domain; Source Mapping Rules which indicate how syntactic heads and grammatical functions in the source language are mapped onto domain concepts and semantic roles in the interlingua; a Domain Model/Ontology which defines the classes of domain concepts and restricts the fillers of semantic roles for each class; Target Mapping Rules which indicate how domain concepts and semantic roles in the interlingua are mapped onto syntactic heads and grammatical functions in the target language; a Target Lexicon which contains appropriate target lexemes for each domain concept; a Target Grammar for the target language which realizes target syntactic constructions as linearized output sentences. == Advantages == No bilingual texts are required. This makes it possible to create translation systems for languages that have no texts in common, or even no digitized data whatsoever. Domain independent. Rules are usually written in a domain independent manner, so the vast majority of rules will "just work" in every domain, and only a few specific cases per domain may need rules written for them. No quality ceiling. Every error can be corrected with a targeted rule, even if the trigger case is extremely rare. This is in contrast to statistical systems where infrequent forms will be washed away by default. Total control. Because all rules are hand-written, you can easily debug a rule-based system to see exactly where a given error enters the system, and why. Reusability. Because RBMT systems are generally built from a strong source language analysis that is fed to a transfer step and target language generator, the source language analysis and targe
Stanford Research Institute Problem Solver
The Stanford Research Institute Problem Solver, known by its acronym STRIPS, is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International. The same name was later used to refer to the formal language of the inputs to this planner. This language is the base for most of the languages for expressing automated planning problem instances in use today; such languages are commonly known as action languages. This article only describes the language, not the planner. == Definition == A STRIPS instance is composed of: An initial state; The specification of the goal states – situations that the planner is trying to reach; A set of actions. For each action, the following are included: preconditions (what must be established before the action is performed); postconditions (what is established after the action is performed). Mathematically, a STRIPS instance is a quadruple ⟨ P , O , I , G ⟩ {\displaystyle \langle P,O,I,G\rangle } , in which each component has the following meaning: P {\displaystyle P} is a set of conditions (i.e., propositional variables); O {\displaystyle O} is a set of operators (i.e., actions); each operator is itself a quadruple ⟨ α , β , γ , δ ⟩ {\displaystyle \langle \alpha ,\beta ,\gamma ,\delta \rangle } , each element being a set of conditions. These four sets specify, in order, which conditions must be true for the action to be executable, which ones must be false, which ones are made true by the action and which ones are made false; I {\displaystyle I} is the initial state, given as the set of conditions that are initially true (all others are assumed false); G {\displaystyle G} is the specification of the goal state; this is given as a pair ⟨ N , M ⟩ {\displaystyle \langle N,M\rangle } , which specify which conditions are true and false, respectively, in order for a state to be considered a goal state. A plan for such a planning instance is a sequence of operators that can be executed from the initial state and that leads to a goal state. Formally, a state is a set of conditions: a state is represented by the set of conditions that are true in it. Transitions between states are modeled by a transition function, which is a function mapping states into new states that result from the execution of actions. Since states are represented by sets of conditions, the transition function relative to the STRIPS instance ⟨ P , O , I , G ⟩ {\displaystyle \langle P,O,I,G\rangle } is a function succ : 2 P × O → 2 P , {\displaystyle \operatorname {succ} :2^{P}\times O\rightarrow 2^{P},} where 2 P {\displaystyle 2^{P}} is the set of all subsets of P {\displaystyle P} , and is therefore the set of all possible states. The transition function succ {\displaystyle \operatorname {succ} } for a state C ⊆ P {\displaystyle C\subseteq P} , can be defined as follows, using the simplifying assumption that actions can always be executed but have no effect if their preconditions are not met: The function succ {\displaystyle \operatorname {succ} } can be extended to sequences of actions by the following recursive equations: succ ( C , [ ] ) = C {\displaystyle \operatorname {succ} (C,[\ ])=C} succ ( C , [ a 1 , a 2 , … , a n ] ) = succ ( succ ( C , a 1 ) , [ a 2 , … , a n ] ) {\displaystyle \operatorname {succ} (C,[a_{1},a_{2},\ldots ,a_{n}])=\operatorname {succ} (\operatorname {succ} (C,a_{1}),[a_{2},\ldots ,a_{n}])} A plan for a STRIPS instance is a sequence of actions such that the state that results from executing the actions in order from the initial state satisfies the goal conditions. Formally, [ a 1 , a 2 , … , a n ] {\displaystyle [a_{1},a_{2},\ldots ,a_{n}]} is a plan for G = ⟨ N , M ⟩ {\displaystyle G=\langle N,M\rangle } if F = succ ( I , [ a 1 , a 2 , … , a n ] ) {\displaystyle F=\operatorname {succ} (I,[a_{1},a_{2},\ldots ,a_{n}])} satisfies the following two conditions: N ⊆ F {\displaystyle N\subseteq F} M ∩ F = ∅ {\displaystyle M\cap F=\varnothing } == Extensions == The above language is actually the propositional version of STRIPS; in practice, conditions are often about objects: for example, that the position of a robot can be modeled by a predicate A t {\displaystyle At} , and A t ( r o o m 1 ) {\displaystyle At(room1)} means that the robot is in Room1. In this case, actions can have free variables, which are implicitly existentially quantified. In other words, an action represents all possible propositional actions that can be obtained by replacing each free variable with a value. The initial state is considered fully known in the language described above: conditions that are not in I {\displaystyle I} are all assumed false. This is often a limiting assumption, as there are natural examples of planning problems in which the initial state is not fully known. Extensions of STRIPS have been developed to deal with partially known initial states. == A sample STRIPS problem == A monkey is at location A in a lab. There is a box in location C. The monkey wants the bananas that are hanging from the ceiling in location B, but it needs to move the box and climb onto it in order to reach them. Initial state: At(A), Level(low), BoxAt(C), BananasAt(B) Goal state: Have(bananas) Actions: // move from X to Y _Move(X, Y)_ Preconditions: At(X), Level(low) Postconditions: not At(X), At(Y) // climb up on the box _ClimbUp(Location)_ Preconditions: At(Location), BoxAt(Location), Level(low) Postconditions: Level(high), not Level(low) // climb down from the box _ClimbDown(Location)_ Preconditions: At(Location), BoxAt(Location), Level(high) Postconditions: Level(low), not Level(high) // move monkey and box from X to Y _MoveBox(X, Y)_ Preconditions: At(X), BoxAt(X), Level(low) Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X) // take the bananas _TakeBananas(Location)_ Preconditions: At(Location), BananasAt(Location), Level(high) Postconditions: Have(bananas) == Complexity == Deciding whether any plan exists for a propositional STRIPS instance is PSPACE-complete. Various restrictions can be enforced in order to decide if a plan exists in polynomial time or at least make it an NP-complete problem. == Macro operator == In the monkey and banana problem, the robot monkey has to execute a sequence of actions to reach the banana at the ceiling. A single action provides a small change in the game. To simplify the planning process, it make sense to invent an abstract action, which isn't available in the normal rule description. The super-action consists of low level actions and can reach high-level goals. The advantage is that the computational complexity is lower, and longer tasks can be planned by the solver. Identifying new macro operators for a domain can be realized with genetic programming. The idea is, not to plan the domain itself, but in the pre-step, a heuristics is created that allows the domain to be solved much faster. In the context of reinforcement learning, a macro-operator is called an option. Similar to the definition within AI planning, the idea is, to provide a temporal abstraction (span over a longer period) and to modify the game state directly on a higher layer.