Probabilistic Tree-Adjoining Grammar as a Framework for Statistical Natural Language Proces

Mining probabilistic tree patterns in a medicaldatabaseAmaury Habrard,Marc Bernard,and Fran¸c ois Jacquenet EURISE–Universit´e de Saint-Etienne–23,rue du Dr Paul Michelon42023Saint-Etienne cedex2–France{Amaury.Habrard,Marc.Bernard,Francois.Jacquenet}@univ-st-etienne.fr Abstract.We propose a contribution to the PKDD-2002discovery chal-lenge on the hepatitis dataset.This challenge aims at discovering regu-larities over patients strucked down by chronic hepatitis.Our approachaddresses the problem of multi-relational Data Mining,extracting proba-bilistic tree patterns from a database using Grammatical Inference tech-niques.We propose to use a representation of the database by trees inorder to extract these patterns.They provide a natural way to representstructured information taking into account the statistical distributionof the data.In this work we try to show how they can be useful forinterpreting knowledge in medical domain.1IntroductionThe main objective of Data Mining techniques is to extract regularities from a large amount of data.For this purpose some efficient techniques have been pro-posed like the apriori algorithm[2].However these techniques are closely related to data stored in aflat representation even though more and more structured data(like relational databases)are used in all domains of activity.Thus to deal with algorithms working onflatten data some pre-processing steps are required that unfortunately lead to lose some valuable information.Over the last years,several attempts have been made to extract regulari-ties directly from databases without having toflatten data.That has led to the emergence of an activefield of research,called multi-relational Data Mining[8]. For example,the ILP system WARMR[9]defines a generic framework to learn from a datalog representation of a database,keeping the structuring of data.[7] propose an algorithm for mining decentralized data exploiting the inter-tables relationships to extract frequent itemsets on separate tables.In this paper we present a method allowing to extract some knowledge from data structured as trees.Trees are natural candidates for representing structured information of multi-relational databases.Mining some probabilistic knowledge in this context leads to mining tree patterns that respect the statistical distribution observed over the data.A tree pattern can be viewed as an abstraction from trees and thus provides an interesting way to represent regularities observed in large amount of data.The concept of tree patterns has received a lot of interest during thepast two years.In the machine learningfield,learning of tree patterns has been studied for example in[3,13].More recently,data mining approaches have been proposed to extract these patterns[4,10,16–18].In this paper we are interested in statistical learning methods which may improve the Data Mining task.Indeed these methods are interesting for Data Mining because they provide a quantita-tive approach to weighting the evidence supporting alternative hypotheses.They are known to perform well with noisy data and may discover some knowledge from positive examples only.The method we present follows several steps.First we have to define the table containing data we want to focus on.From the rows of this table we generate a set of trees.Indeed,for each row,a tree is generated recursively using the relationships defined between various tables by foreign ing some probabilistic grammatical inference techniques we learn a probabilistic tree grammar on the database.The tree grammar is represented with a stochastic tree automaton.Then we use a level wise search approach to generalize transition rules of the automaton.These generalized rules arefinally used to produce a set of probabilistic tree patterns.Each step of our method will be described in the remaining of the paper.We propose to contribute to the discovery challenge on chronic hepatitis by extracting probabilistic tree patterns from the relational database provided for the challenge1.So we tackle this challenge with the goal of extracting new kind of knowledge.We focus our work on the relations between the level of liverfibrosis and laboratory examinations made on patients.The level of liverfibrosis is often closely related to the stage of hepatitis C,a disease which may lead to develop liver cirrhosis or hepatocarnocima.Thefinal objective is to point out laboratory examinations that can predict the level of liverfibrosis.The work presented in this paper can be view as a preliminary work on the extraction of probabilistic tree patterns in relational database on medical data. The objective is to see how these patterns can be useful in multi-relational data mining tasks and how they can model structured data in relational databases. 2Converting the database into a set of treesThe relational schema of a database may be defined as a graph,so the represen-tation of the data as trees may lose some information.The method we propose in this paper can be view as a bias to look for regularities from structured data represented in a tree structure.The idea is to use the system in order to learn a model from an entity,that is a concept stored in the database.Thus an instance of this concept is a tuple of a particular table(denoted as the root table).A tree is constructed to store information about each instance of the concept to learn.Each record of the root table is represented as a tree to be used by the system.Trees are generated using foreign keys relationships in the database to develop branches of trees.To give the structure of trees we use a structure function.This function is defined by 1http://lisp.vse.cz/challenge/ecmlpkdd2002/inference rules describing the construction of nodes relatively to preconditions taking into account foreign key relationships.In order to present inference rules that define the generation of trees we introduce some notations.We consider a database T with n tables T1,...,T n.Each table is made up of a set of attributes A(T i)={a i1,...,a in(i)}where n(i)is the number of attributes of the table T i.We denote T i.a ik the attribute a ikofthe table T i.We define the set of foreign keys F(T i)={a i1,...,a im}such thatF(T i)⊆A(T i)and each a ik ∈F(T i)is a reference to an attribute T j.a jl(whatwe denote T i.a ik :T j.a jl).For example,if we consider the table T r for the root table.For each tuple <v1,...,v n(r)>stored in the root table T r,we call the structure function as:structure(T r(v1,...,v n(r)))The structure function is defined by the following rules.a ij∈F(T i)structure(v ij )=v ija ij ∈F(T i)T i.a ij :T k.a kl<v1,...,v n(k)>=SELECT*FROM T k WHERE T k.a kl =v ijSv ij=structure(T k(v1,...,v n(k)))structure(v ij )=Sv ij∀k,1≤k≤n(i),Sv k=structure(v k)structure(T i(v1,...,v n(i)))=T i(Sv1,...,Sv n(i)) The definition of the structure function provides a bias language which allows to generate a set of trees.This language allows to select attributes of the tables, to bound the depth of trees.In case of foreign keys defining a1−n relation,we construct a list.All the records are listed to represent a comb in the tree.3Stochastic tree automataA tree automaton[12,6]defines a regular tree language as afinite automaton defines a regular language on strings.Stochastic tree automata are an extension of tree automata and define a statistical distribution on the tree language recog-nized by the automata.Learning tree automata has received attention for some years.For example[11]and[15]have proposed some algorithms for learning tree automata.In the probabilistic framework,[5]proposed an efficient algorithm to learn stochastic tree automata and[1]dealt with learning stochastic tree gram-mars to predict protein secondary structure.In this section we mainly describe stochastic tree automata,which are the core of the system.In fact we consider an extension of stochastic tree automata which takes sorts into account.Thus we consider many-sorted stochastic tree automata.Wefirst define the concept of signature,which represents the set of constructible trees.Definition1A signatureΣis a4-tuple(S,X,α,σ).S is afinite set whose elements are called sorts.X is afinite set whose elements are called function symbols.αis a mapping from X into I N.α(f)will be called the arity of f.σis a mapping from X into S.σ(s)will be called the sort of s.Definition2A stochastic many-sorted tree automaton(SMTA)is a5-tuple (Σ,Q,r,δ,p).Σis a signature(S,X,α,σ).Q=∪s∈S Q s is afinite set of states, each state having a sort in S.r:Q−→[0,1]is the probability for the state to be an accepting state.δ:X×Q∗−→Q is the transition function.p:X×Q∗−→[0,1]is the probability of a transition.We denote R A,g,q the set of all rules of the form g(q1,...,q n)→q of a tree automaton A.Note that we assume we do not allow overloading of function symbols.A SMTA parses a tree using a bottom-up strategy.A state and a probability are associated with each node of the tree.The labelling of each node is defined by the transition function.The tree is accepted if the probability of its root node is strictly positive.Given a SMTA A,the probability of a tree t is computed as follows:p(t|A)=r(δ(t))×π(t)whereπ(f(t1,...,t n))is recursively computed by:π(t)=p(f,δ(t1),...,δ(t n))×π(t1)×···×π(t n)Example The automaton A defined by the following transition rules is able to recognize,for instance,the tree g(f(c,b,a))with an associated probability of0.15.1.0:a→q11.0:b→q21.0c→q50.6:f(q1,q2,q4)→q30.15:f(q5,q2,q1)→q30.15:f(q1,q4,q3)→q3 0.1:f(q1,q2,q3)→q31.0:g(q3)→q4Final state:r(q4)=1.0The inference of a tree automata is made from a sample of trees defining a dataset.We do not detail the procedure here,the interested reader may con-sult[5,14].The structure of the automaton is iteratively constructed using a state merging procedure.The probabilities are then computed from the train sample,taking into account the distribution of the data.We generalize rules of the automaton,looking for frequent regularities in the database,relatively to the distribution of the dataset.This step of generalization allows to generate probabilistic tree patterns,modeling concepts stored in the database.4Generalization of a SMTAWe have proposed in[14]a technique to generalize SMTA relatively to a thresh-oldγ.The idea is to generalize the transition rules of the automaton using alevel wise algorithm.The generalization algorithm is local,that is it considers generalization of a SMTA locally to a given arrival state and a given symbol.The generalization process considers rules containing variables,these rules are called generalized rules.The score of a generalized rule is computed by adding probabilities of the transition rules of the SMTA subsumed by the generalized rule.The algorithm looks for the most specific generalized rules having a score greater thanγ.Algorithm presented in[14]extracts generalized rules from all the sets R A,f,q definable in the SMTA.Definition3Let V a set of variables and Q a set of states.Let r1and r2be two rules:r1=f(x1,...,x n)→q and r2=f(x′1,...,x′n)→q′such that x i∈Q∪V and x′i∈Q∪V.r1is more general than r2(we note r1>r2)if and only if there exists a substitutionθsuch that f(x1,...,x n)θ=f(x′1,...,x′n).We say that r1 subsumes r2.Definition4A rule r is called a generalized rule if there exists a rule r′in R A,f,q such that r>r′.For example,consider the following set of rules R A,f,q3from a SMTA A:0.10:f(q1,q2,q3)→q30.15:f(q1,q4,q3)→q30.60:f(q1,q2,q4)→q30.15:f(q5,q2,q3)→q3If wefix theγparameter to0.6,the generalization algorithm will extract the following generalized rules:0.6:f(q1,,q4),0.7:f(q1,q2,)and0.6:f(,q2,q4)In this work we are interested in extracting probabilistic tree patterns.These tree patterns give a probabilistic representation of the rmally a tree pattern is a tree whose leaves can be either variables or symbols of arity zero.Formally we define tree patterns as terms infirst order logic.Definition5LetΣ=(S,X,α,σ)a signature and V a set of variables.A tree pattern,onΣ∪V,is defined recursively as follows:–a symbol s∈X,such thatα(s)=0,is a tree pattern–a variable v∈V is a tree pattern–if t1,...,t n are tree patterns,then f(t1,...,t n)is a tree pattern for any symbol f∈X such thatα(f)=nDefinition6A probabilistic tree pattern is a couple(t,p)where t is a tree pattern and p a probability(0≤p≤1).To extract these patterns we use a depthfirst search on the generalized rules of the SMTA.The idea is to start from thefinal states of the generalized SMTA(that is states with a probability greater than zero to be afinal state)and to construct the tree patterns recognized by the automaton.This process is recursive using the generalized rules of the automaton.The rules are chosen in function of their arrival state,when many rules can be used,we generated tree patterns for each possibility.The probability of a tree pattern is the product of the probabilities of the rules used in the depthfirst search process.5Challenge taskWe focus our work on data about chronic hepatitis.These data were prepared in collaboration with the Shimane Medical University,School of Medicine and Chiba University Hospital.The database stores771patients with hepatitis B and C who took examinations in the period1982-2001.Hepatitis A,B and C are virus infections that affect the liver of the patient.Hepatitis B and C are espe-cially important because they have a potential risk of developing liver cirrhosis or hepatocarcinoma.An indicator that can be used to know the risk of cirrhosis or hepatocarcinoma isfibrosis of hepatocyte.For instance liver cirrhosis is char-acterized as the terminal stage of liverfibrosis.One way to evaluate the stage of liverfibrosis is to make a biopsy,but this examination is invasive to patients, thus it could be interesting to use laboratory examinations as substitutes for biopsy.In this work we propose to extract probabilistic tree patterns trying to link the stage of liverfibrosis and in-hospital and out-hospital laboratory examina-tions.For this purpose we focus on four levels on thefive described in biopsy examinations,that are levels F1,F2,F3and F4which is the most severe stage. Then we construct a sample for each level,each sample is made up of trees taking into account laboratory examinations.The following section presents prepara-tion of the data.5.1Data preparationData are organized in a relational database made up of six tables.One table gives information about patients(PT E table),another one gives results of biopsy on patients(BIO E table)while information on interferon therapy are stored in the IFN E table.Two tables give results of in-hospital and out-hospital exam-inations(ILAB E and OLAB E tables),the last table(LABN E table)gives information about measurements in in-hospital examinations.We store the data in a relational database,using the RDBMS postgresql7.1.3.For each level of liverfibrosis,we choose the table PT E for the root ta-ble and we select tuples corresponding to patients having a biopsy with the considered level of liverfibrosis.The structure function considers only the at-tribute MID for table P T E.The attribute MID is duplicated to define two foreign keys:one on table OLAB E,the second on table ILAB E.For table OLAB E the structure function considers the attributes OLAB Exam Name, OLAB Exam Result,OLAB Evaluation and OLAB Eval SubCode.In table ILAB E the structure function considers the attributes ILAB Exam Nameand ILAB Exam Result .To construct the subtrees corresponding to the for-eign keys on tables ILAB E and OLAB E ,the structure function considers only records so that the time between the date of examination and the date of the biopsy of the patient doesn’t exceed two days.Values of attributes ILAB Exam Result and OLAB Exam Result are dis-cretized taking into account information of table LABN E .If an examination has an entry in this table,we consider the value as normal if it is between the up-per and lower bound,otherwise we measure its level in function of a discretized step.For other examinations,we compute a mean to define lower and upper bounds,then we apply the same policy.The tree of figure 1is an example of tree produced for a patient at level F2.This patient has no out-hospital examinations,and has two in-hospital examina-tions:one on activated partial thromboplastin time (APTT)which has a normal value and one on prothrombin time (PT)which has also a normal value.APTT cons_ILAB_E cons_ILAB_E ILAB_Eend_cons_ILAB_EPT APTT_|0|UNKNOWN_OLAB_EPT_|0|PT_EILAB_EFig.1.Tree associated with patient with MID=4145.2Experimentation on level of liver fibrosisWe generate a sample of trees for each level of liver fibrosis (F1to F4).Then,for each sample we learn a generalized SMTA with different levels of generalization.Let us recall that the level of generalization depends on the γparameter (0≤γ≤1)and the higher this parameter is,the more we generalize.Thus,if this parameter is high we extract very few patterns which are often too general.On the other hand,if it is low,a lot of patterns are extracted which are very specific.For example,we extract 768320patterns with γ=0.15and only 4with γ=0.85on patients at level F3.So this parameter may be used to define the specialization of the extracted knowledge.For this purpose we learned generalized SMTA using the γparameter from 0.1to 0.85.Then for each generalized model,we extract probabilistic tree patterns.To illustrate the extracted knowledge,we give some examples of tree patterns and their probabilities.As discussed in a previous section,some leaves of trees correspond to discretized attributes of the database,and thus the number of the interval of values for such attributes is denoted between two vertical lines.Figure 2shows a general pattern,of probability 0.66,extracted with γ=0.7from patients at level rmally this pattern says that patients,at level F2,may have at least one in-hospital examination with probability 0.66.cons_ILAB_EILAB_E_ __ _ PT_E0.66:Fig.2.Tree pattern of level F2extracted with γ=0.7Figure 3shows a less general pattern saying that 20%of patients at level F1generally have at least two in-hospital examinations with one albumin (ALB).cons_ILAB_EILAB_EALB _ _ _PT_E0.20:Fig.3.Tree pattern of level F1with extracted with γ=0.55Figure 4shows a very specific pattern of probability 0.0004.This pattern says that 0.04%patients at level F3often have at least one out-hospital examination on “D inshi”with no evaluation and a subcode equals to F504and at least one in-hospital examination on albumin (ALB).OLAB_ED inshi _ F504_ cons_OLAB_Econs_ILAB_E ILAB_E ALB _ _ PT_E 0.0004:Fig.4.Tree pattern of level F3extracted with γ=0.1Figure 5shows a less specific pattern.It says that 6.9%of patients at level F4may have one in-hospital examination on albumin (ALB)with value between 0and 3.9g/dl.PT_E cons_ILAB_E_ ILAB_E _ ALB_|−1|_0.069:Fig.5.Tree pattern of level F4extracted with γ=0.1We now sum up on figure 6of the influence of the γparameter on the number of extracted tree patterns.For small values of γ,we expect a weak generalization and thus a high number of patterns with a priori small probabilities.When γtends to 1,we expect overfitting and so a small number of patterns.Note that if too general patterns are not very interesting,patterns with low probabilities can be useful because they can point out rare events.1101001000100001000001e+061e+070.10.20.30.40.50.60.70.8N u m b e r o f p a t t e r n s Gamma parameter F1F2F3F4Fig.6.Number of patterns relatively to γWe now give a summary of the probabilistic tree patterns extracted by our system.Note that in our work we only consider examinations made in the sameperiod of the biopsy examination.Thus a larger study seems necessary to inter-pret these results.–patients at level F1For in-hospital examinations we extract that20%of patients have ALB examinations.We also extract patterns saying that17%of patients at level F1have normal values for this examination.For out-hospital examinations, the examination“ABO shiki ketsuekigata kensa”concerns about50%of the patients.20%of them have“O kata”and15%have“B kata”as result for this examination.–patients at level F2The out-hospital examination“ABO shiki ketsuekigata kensa”is present for30%of patients.For in-hospital examinations we notice the presence of albumin(ALB)(20%)and alkaline phosphatase(ALP)(20%).–patients at level F3The out-hospital examination“ABO shiki ketsuekigata kensa”is also present for18%of patients.We also notice the presence of“D inshi”examination for 17%of patients.These two examinations are both linked with the following subcodes(uniformally distributed):E499,E500,E501,E502,F503,F504and F505.The albumin(ALB)examination is also present for in-hospital tests for26%of patients.–patients at level F4We notice the examination albumin(ALB)for20%of the patients,direct bilirubin(D-BIL)and cholinesterase(CHE)for7%of patients in in-hospital examinations.Note that for albumin exams,the patients have a probability of12%to have a result lower than the normal range.6ConclusionIn this paper we have experimented a new method to extract probabilistic tree patterns from a relational database.This method is based on a representation of the database by a set of trees and the inductive phase consists infirst learning a SMTA and generalizing this model relatively to a parameter.In the context of the challenge,we are able to link data from many relations of the database,like out-hospital and in-hospital examinations.The knowledge extracted seems to be comprehensible in the context of a medical database.The medical interest of the extracted patterns is not clear for us.However the number of hospital examinations seems not be sufficient to validate our results.One interesting perspective for the challenge is to define a language bias (maybe with medical experts)to embed all the relevant information in trees. Then we may try to use the method on other goals of the challenge.Another perspective is to see how probabilistic tree patterns can be used as a condensed representation of the database.References1.N.Abe and H.Mamitsuka.Predicting protein secondary structure using stochastictree grammars.Machine Learning,29:275–301,1997.2.R.Agrawal and R.Srikant.Fast algorithms for mining association rules.In Jorge B.Bocca,Matthias Jarke,and Carlo Zaniolo,editors,Proc.20th Int.Conf.Very Large Data Bases,VLDB,pages487–499.Morgan Kaufmann,12–151994.3.T.R.Amoth,P.Cull,and P.Tadepalli.On exact learning of unordered treepatterns.Machine Learning,44(3):211,2001.4.H.Arimura,H.Sakamoto,and S.Arikawa.Efficient learning of semi-structureddata from queries.In12th International Conference on Algorithmic Learning The-ory,volume2225of Lecture Notes in Computer Science,pages315–331,2001. 5.R.C.Carrasco,J.Oncina,and J.Calera.Stochastic Inference of Regular TreeLanguages.Machine Learning,44(1/2):185–197,2001.on,M.Dauchet,R.Gilleron,F.Jacquemard,D.Lugiez,S.Tison,andM.Tommasi.Tree Automata Techniques and Applications.Available on: http://www.grappa.univ-lille3.fr/tata,1997.7.V.Crestana-Jensen and N.Soparkar.Frequent itemset counting across multipletables.In4th Pacific-Asian conference on Knowledge Discovery and Data Mining (PAKDD2000),pages49–61,April2000.8.L.De Raedt.Data mining in multi-relational databases.In4th European Confer-ence on Principles and Practice of Knowledge,2000.Invited talk.9.L.Dehaspe and H.Toivonen.Discovery of frequent DATALOG patterns.DataMining and Knowledge Discovery,3(1):7–36,1999.10.J.Ganascia.Extraction of recurrent patterns from stratified ordered trees.In12thEuropean Conference on Machine Learning(ECML’01),volume2167of LNCS, pages167–178,Freiburg,Germany,2001.Springer.11.P.Garc´ıa and J.Onc´ina.Inference of recognizable tree sets.Research Report DSIC-II/47/93,Departamento de Sistemas Inform´a ticos y Computaci´o n,Universidad Polit´e cnica de Valencia,1993.12. F.G´e cseg and M.Steinby.Tree Automata.Akad´e miai Kiad´o,Budapest,1984.13.S.A.Goldman and S.S.Kwek.On learning unions of pattern languages and treepatterns.In10th Algorithmic Learning Theory conference,volume1720of Lecture Notes in Artificial Intelligence,pages347–363,1999.14. A.Habrard,M.Bernard,and F.Jacquenet.Generalized stochastic tree automatafor multi-relational data mining.In Proceedings of the Sixth International Collo-quium on Grammatical Inference(ICGI2002),2002.To appear.15.T.Knuutila and M.Steinby.Inference of tree languages from afinite sample:analgebraic approach.Theoretical Computer Science,129:337–367,1994.16.T.Miyahara,Y.Suzuki,T.Shoudai,T.Uchida,K.Takahashi,and H.Ueda.Dis-covery of frequent tag tree patterns in semistructured web documents.In sixth Pa-cific Asia Conference on Knowledge Discovery and Data mining(PAKDD2002), Taipei,Taiwan,May2002.17.M.Bruynooghe R.Kosala,J.Bussche and rmation extraction instructured documents using tree automata induction.In6th European Conference on Principles and Practise of Knowledge Discovery in Databases(PKDD’02),2002.To appear.18.M.Zaki.Efficiently mining frequent trees in a forest.In Proceedings of the eighthACM SIGKDD International Conference on Knowledge Discovery and Data Min-ing(KDD),2002.To appear.。

博树英语语法资料Grammar is an essential component of any language, including English. It provides a set of rules and structures that enable effective communication. In this document, we will explore various aspects of English grammar, from basic sentence structure to more complex concepts.1. Sentence Structure。

A sentence is the fundamental unit of communication. It consists of a subject, a verb, and sometimes an object. The subject is the person or thing performing the action, the verb is the action itself, and the object is the recipient of the action. For example, "John eats an apple." In this sentence, John is the subject, eats is the verb, and apple is the object.2. Parts of Speech。

English has eight parts of speech: nouns, pronouns, verbs, adjectives, adverbs, prepositions, conjunctions, and interjections. Nouns are words that represent people, places, things, or ideas. Pronouns replace nouns in a sentence. Verbs express actions or states of being. Adjectives describe or modify nouns. Adverbs modify verbs, adjectives, or other adverbs. Prepositions show relationships between words. Conjunctions connect words, phrases, or clauses. Interjections express strong emotions.3. Verb Tenses。

Robust Matching of3D Lung Vessel Trees Dirk Smeets ,Pieter Bruyninckx,Johannes Keustermans,Dirk Vandermeulen,and Paul SuetensK.U.Leuven,Faculty of Engineering,ESAT/PSIMedical Imaging Research Center,UZ Gasthuisberg,Herestraat49bus7003,B-3000Leuven,BelgiumAbstract.In order to study ventilation or to extract other functionalinformation of the lungs,intra-patient matching of scans at a different in-spiration level is valuable as an examination tool.In this paper,a methodfor robust3D tree matching is proposed as an independent registrationmethod or as a guide for other,e.g.voxel-based,types of registration.Forthefirst time,the3D tree is represented by intrinsic matrices,referenceframe independent descriptions containing the geodesic or Euclidean dis-tance between each pair of detected bifurcations.Marginalization of pointpair probabilities based on the intrinsic matrices provides soft assign cor-respondences between the two trees.This global correspondence modelis combined with local bifurcation similarity models,based on the shapeof the adjoining vessels and the local gray value distribution.As a proofof concept of this general matching approach,the method is applied formatching lung vessel trees acquired from CT images in the inhale andexhale phase of the respiratory cycle.1IntroductionThe pulmonary ventilation,i.e.the inflow and outflow of air between the lungs and atmosphere,is the result of the movement of the diaphragm or the ribs leading to small pressure differences between the alveoli and the atmosphere. Quantification of pulmonary ventilation is a clinically important functional com-ponent in lung diagnosis.Pulmonary ventilation can be studied using several CT images in one breathing cycle(4D CT)[1].In radiotherapy treatment,extraction of the lung deformation is important for correction of tumor motion,leading to a more accurate irradiation.Matching,i.e.spatially aligning images(also referred as registration),inspi-ration and expiration scans is a challenging task because of the substantial, locally varying deformations during respiration[2].To capture these deforma-tions,a non-rigid registration is required,which can be image-based,surface-based and/or landmark-based.Generally,a non-rigid registration algorithm re-quires three components:a similarity measure,a transformation model and an optimization process.Corresponding author:dirk.smeets@uz.kuleuven.beIn image registration,common voxel similarity measures are sum of square differences(SSD),correlation coefficient(CC)and mutual information(MI)[3, 4].To regularize the transformation,popular transformation models are elastic models,viscousfluid models,spline-based techniques,finite element models or opticalflow techniques[3].Voxel-similarity based techniques have been applied to lung matching in[5–7].They have the advantage that dense and generally accurate correspondences are obtained.Disadvantages are the sensitivity to the initialization and the computational demands.Surface-based registration meth-ods use a similarity measure that is a function of the distances between points on the two surfaces.Thin-plate splines are popular for regularization of the transfor-mation.A combination of an voxel-similarity based and surface based registra-tion for lung matching is presented in[8].Generally,landmark-based non-rigid registration algorithms allow large deformations.Because of their sparsity,they are very efficient.In[9]bifurcations of lung vessels arefirst detected after which these landmarks are matched by comparing the3D local shape context of each pair of bifurcations with theχ2-distance.In this paper,we present a robust registration method for matching vessel trees.After detecting candidate bifurcations(Sec.2.1),correspondences are es-tablished by combining a global and a local bifurcation similarity model.For the novel global model(Sec.2.3),the tree is represented by two reference frame inde-pendent,hence intrinsic,matrices:the Euclidean(rigid transformation invariant) and geodesic(isometric deformation invariant)distance matrix.Marginalization of point pair probabilities provides soft(not binary)correspondences between the detected bifurcations of the two trees.The local bifurcation similarity model reflects correspondences based on local intensities and is explained in Sec.2.3. The optimization to obtain hard correspondences is done using a spectral de-composition technique(Sec.2.4).The proof of concept of the general matching approach is shown in Sec.3.Finally we draw some conclusions.2MethodThe goal of the proposed matching framework is to establish correspondences between characteristic points in the image,independent of the reference frame (translation and rotation invariant)and,for characteristic points in structures that are assumed to deform isometrically,invariant for isometric deformations. Isometries are defined as distance-preserving isomorphisms between metric spaces, which generally means that structures only bend without stretching.The bifur-cations,the splittings of the vessels in two or more parts,are chosen as charac-teristic points,although their detection is not the main goal of this paper.We then assume the vessel tree to deform isometrically.This assumption of nearly constant vessel length has been made before in a.o.[10]and[11].2.1Bifurcation detectionBifurcations are locations where a blood vessel splits into two smaller vessels.A subset of the bifurcations that involves only major vessels can be detected in a robust way by analyzing the skeletonization of the segmented vessels.As preprocessing,the lungs are segmented by keeping the largest connected component of all voxels with an intensity lower than -200HU.A morphological closing operator includes the lung vessels to the segmentation and a subsequent erosion operation removes the ribs from the segmentation.Then,a rough seg-mentation of the major blood vessels within the lung is obtained by thresholding at -200HU.Cavities in binary segmentation smaller than 10voxels are closed.The skeletonization of the segmentation localizes the major bifurcations and is obtained through a 3D distance transformation by homotopic thinning [12].Since bifurcations are locations where three vessels join,they are characterized as skeleton voxels having three different neighbors belonging to the skeleton.After-wards,bifurcations are discarded that have a probability lower than 0.5/√2πσ2according to a statistical intensity model.The vessel intensities I k are assumed to be Gaussian distributed P (c vessel |I k )=1√2πσ2exp −(I k −μ)2σ2 ,(1)with experimentally determined parameters (μ=−40HU and σ=65HU).2.2Global correspondence modelAfter the vessel bifurcations are detected,soft correspondences are established based on a global and a local correspondence model,both independent of rigid and isometric deformations of the considered vessel trees.Intrinsic vessel tree representation.Each tree is intrinsically represented by a Euclidean distance matrix E =[d R 3,ij ](EDM),containing Euclidean dis-tances between each pair of bifurcations,and a geodesic distance matrix G =[g ij ](GDM).Each element g ij corresponds to the geodesic distance between the bi-furcations i and j .This distance is the distance between i and j along the vessels and is computed with the fast marching method in an image containing a soft segmented vessel tree using Eq.(1).Isometric vessel deformations,by defini-tion,leave these geodesic distances unchanged.Therefore,the GDM is invariant to the bending of the vessels.On the other hand,the EDM is only invariant to rigid transformations (and,when normalized,invariant to scale variations)of the vessel tree.However,Euclidean distance computation is expected to be more robust against noise than geodesic distance computation since the error accumu-lates along the geodesic,i.e.the shortest path.Both the EDM and the GDM are symmetric and uniquely defined up to an arbitrary simultaneous permutation of their rows and columns due to the arbitrary sampling order of the bifurcations.An example of a lung vessel tree,represented by a GDM and a EDM,is shown in Fig.1.(a)10203040506010203040506050100150200250300350400(b)102030405060102030405060020406080100120(c)Fig.1.A lung vessel tree with detected bifurcations (a)is represented by a geodesic (b)and a Euclidean (c)distance matrix,containing the geodesic or Euclidean distance between each pair of bifurcations.Soft correspondences of the global model.A probabilistic framework is used to estimate the probability that a bifurcation i of one tree corresponds with a bifurcations k of the other tree.It is applied twice,once for the EDM and once for the GDM.We will explain the framework using the GDM.Given two lung vessel trees,represented by GDMs,the probability that the pair of bifurcations (i,j )of the first tree G 1correponds with the pair (k,l )of the second tree G 2is assumed to be normally distributed,P (C (i,j ),(k,l ))=1√2exp −(g 1,ij −g 2,kl )2σ2 ,(2)with σchosen to be 1and g 1,ij an element of the GDM representing the first tree.It reflects the assumption that geodesic distances between pairs of bifur-cations are preserved,obeying an isometric deformation.The probability that abifurcation i corresponds with k is then given byP(C i,k)=jlP(C(i,j),(k,l))=m G,ik,(3)from which the soft correspondence matrix,M G=[m G,ik],is constructed.The same procedure is followed to obtain an assignment matrix M E based on the EDM as intrinsic tree representation.This matrix is expected to be more robust against noise,but varies under isometric deformations of the vessel tree, contrary to M G.2.3Local correspondence modelComplementary to the global bifurcation similarity model,a local model based on intensities is implemented.In the computer vision literature a large number of local image descriptors are proposed,see for example[13].In this paper,the n-SIFT(scale invariant feature transform)image descrip-tor is used[14],which summarizes a cubic voxel region centered at the feature location,in casu the bifurcation location.The cube is divided into64subre-gions,each using a60bin histogram to summarize the gradients of the voxels in the subregion.This results in a3840-dimensional feature vector f by com-bining the histograms in a vector after weighting by a Gaussian centered at the feature location.The probability that a bifurcation i corresponds with k is then proportional toP(C i,k)∝exp(− f i−f k 2)=m L,ik,(4) 2.4Spectral matchingThe combined match matrix M C is found as the pointwise product of the match matrices of the separate models,m C,ik=m G,ik.m E,ik.m L,ik(i.e.product of the corresponding probabilities).To establish hard correspondences(one-to-one mapping),the algorithm proposed by Scott and Longuet-Higgins[15]is used. It applies a singular value decomposition to M C(M C=UΣV T)and computes the orthogonal matrix M C=U˜I n V T,with˜I n a pseudo-identity matrix.Two bifurcations i and k match if m C,ik is both the greatest element in its row and the greatest in its column.3Experimental resultsThe described matching framework is evaluated using a publicly available4D CT thorax dataset of the L´e on B´e rard Cancer Center&CREATIS lab(Lyon, France),called“POPI-model”.It contains103D volumes representing the dif-ferent phases of the average breathing cycle,with an axial resolution of0.976562 mm×0.976562mm and a slice thickness of2mm.Also,3D landmarks,indi-cated by medical experts,and vectorfields describing the motion of the lung, are available[16].3.1Matching manually indicated landmarksFirst,the matching framework is evaluated using manually indicated landmarks to examine the performance independent of the bifurcation detection step.For this purpose,all 40landmarks are used in one CT image (end-inhalation phase),while varying the number of landmarks in the other image.The result of this experiment,expressed as the percentage of correct correspondences in function of the percentage outliers of the total number of landmarks,is shown in Fig.2for different images in the respiratory cycle.Since not all landmarks are located in the vessels and therefore geodesic distances are not meaningful,M G is not computed.% outliers of total no. landmarks % c o r r e c t c o r r e s p o n d e n c e s Fig.2.Results of the framework for matching manually indicated landmarks expressed as the percentage of correct correspondences in function of the percentage outliers.The three curves correspond with different scans in the respiratory cycle,in which scan no.1is end-inhale and scan no.6end-exhale.These results show that even for a large number of outliers good correspon-dences are still found.Consequently,it can be expected that not all bifurcations detected in one image must be present in the other image.Also,a small decrease in performance can be noticed when more lung deformation is present (end-exhale vs.end-inhale),probably because the Euclidean distance matrix (used in the global correspondence model)is not invariant for these deformations.Second,the robustness against landmark positioning errors is examined.Therefore,we add uniform distributed noise in each direction to one set of landmarks and vary the maximum amplitude of the noise.Fig.3shows the percentage of correct correspondences in function of this maximum amplitude,averaged over 15runs per noise level.These results show that indication errors of more than 5mm (±5voxels in x and y direction and 2.5voxels in z di-rection)decrease the matching performance.It is therefore expected that the localization of bifurcations during automatic bifurcation detection must not be extremely accurate in order to still obtain good correspondences.maximum noise amplitude in each direction [mm]% c o r r e c t c o r r e s p o n d e n c e s Fig.3.Indication error dependence,expressed as the percentage of correct correspon-dences in function of the maximum amplitude of the added uniform noise.The three curves correspond with different scans in the respiratory cycle,in which scan no.1is end-inhale and scan no.6end-exhale.3.2Matching automatically detected bifurcationsNext,the framework is evaluated for the task of matching 3D vessel trees by means of automatically detected bifurcations.The result of matching the end-inhale with the end-exhale vessel tree is shown in Fig.4,clarifying that most correspondence pairs are correct.It is also clear that simple thresholding has resulted in oversegmentation in one of the two images.This,however,did not affect the automatic matching.The performance of matching automatically detected bifurcations is quan-tified using the dense deformation field that is available in the public dataset (POPI-model).This deformation field is obtained using a parametric image-based registration [17,18,16].The average target registration error in the manual landmarks is 1.0mm with a standard deviation of 0.5mm.Fig.4.Qualitative evaluation for matching3D vessel trees by means of automatically detected bifurcations.Fig.5illustrates the accuracy of the matching of the end-inhale scan with all other scans.It shows histograms of the registration error(in each direction and in absolute value)for all bifurcations.The average registration error is2.31mm,the median1.84mm and the maximum24.0mm.Only for0.21%of the bifurcation matches the absolute registration error is larger than1.5cm,demonstrating the robustness of the matching algorithm.4ConclusionA robust matching framework is proposed,combining two global and one local landmark similarity model.The results of matching manually indicated land-marks demonstrate the potential of the proposed method for matching land-marks in unimodal medical images independent of the translation and rotation between both images.A high number of outliers is allowed when the landmarks−10−50510020406080100120error in x−direction [mm]f r e q u e n t y −10−50510error in y−direction [mm]f r e q u e n t y−10−50510error in z−direction [mm]f r e q u e n t y 051015absolute error [mm]f r e q u e n t y Fig.5.Histograms of the registration error (in each direction and in absolute value)for all bifurcations give an impression of the matching accuracy.in the image are well located.Moreover,we demonstrated that the matching framework can also be used for automatically detected landmarks,in this case lung bifurcations extracted from CT data.As future work,we see some applications of the soft correspondences for ro-bust initialization of an iterative non-rigid,e.g.voxel-based,registration method.References1.Guerrero,T.,Sanders,K.,Castillo,E.,Zhang,Y.,Bidaut,L.,Pan,T.,Komaki,R.:Dynamic ventilation imaging from four-dimensional computed tomography.Phys.Med.Biol.51(2006)777–7912.Sluimer,I.,Schilham,A.,Prokop,M.,van Ginneken,B.:Computer analysis ofcomputed tomography scans of the lung:a survey.IEEE Trans.Med.Imaging25(4)(2006)385–4053.Crum,W.R.,Hartkens,T.,Hill,D.L.G.:Non-rigid image registration:theory andpractice.Br J Radiol 77Spec No 2(2004)S140–534.Pluim,J.P.W.,Maintz,J.B.A.,Viergever,M.A.:Mutual information based reg-istration of medical images:A survey.IEEE Trans.Med.Imaging 22(8)(2003)986–10045.Dougherty,L.,Asmuth,J.C.,Gefter,W.B.:Alignment of ct lung volumes with anopticalflow method.Academic Radiology10(3)(2003)249–2546.Stancanello,J.,Berna,E.,Cavedon,C.,Francescon,P.,Loeckx,D.,Cerveri,P.,Ferrigno,G.,Baselli,G.:Preliminary study on the use of nonrigid registration for thoraco-abdominal radiosurgery.Med Phys.32(12)(2005)3777–857.Loeckx, D.:Automated Nonrigid Intra-Patient Image Registration Using B-Splines.PhD thesis,K.U.Leuven(2006)8.Kaus,M.,Netsch,T.,Kabus,S.,Pekar,V.,McNutt,T.,Fischer,B.:Estimationof organ motion from4D CT for4D radiation therapy planning of lung cancer.In: MICCAI.Volume3217of LNCS.(2004)1017–10249.Hilsmann,A.,Vik,T.,Kaus,M.,Franks,K.,Bissonette,J.P.,Purdie,T.,Beziak,A.,Aach,T.:Deformable4DCT lung registration with vessel bifurcations.In:CARS.(2007)10.Klabunde,R.E.:Determinants of resistance toflow./Hemodynamics/H003.htm(august2008)11.Groher,M.,Zikic,D.,Navab,N.:Deformable2D-3D registration of vascular struc-tures in a one view scenario.IEEE Trans Med Imaging28(6)(2009)847–60 12.Selle,D.:Analyse von gef¨a ssstrukturen in medizinischen schichtdatens¨a tzen f¨u rdie computergest¨u tzte operationsplanung.PhD thesis,Aachen(2000)13.Mikolajczyk,K.,Schmid,C.:A performance evaluation of local descriptors.IEEETrans.Pattern Anal.Mach.Intell.27(10)(2005)1615–163014.Cheung,W.,Hamarneh,G.:n-sift:n-dimensional scale invariant feature transform.Trans.Img.Proc.18(9)(2009)2012–202115.Scott,G.L.,Longuet-Higgins,H.C.:An algorithm for associating the features oftwo images.Proc.R.Soc.Lond.B244(1991)21–2616.Vandemeulebroucke,J.,Sarrut, D.,Clarysse,P.:The POPI-model,a point-validated pixel-based breathing thorax model.In:Conference on the Use of Com-puters in Radiation Therapy.(2007)17.Rueckert,D.,Sonoda,L.I.,Hayes,C.,Hill,D.L.G.,Leach,M.O.,Hawkes,D.J.:Nonrigid registration using free-form deformations:Application to breast mr im-ages.IEEE Transactions on Medical Imaging18(1999)712–72118.Delhay,B.,Clarysse,P.,Magnin,I.E.:Locally adapted spatio-temporal deforma-tion model for dense motion estimation in periodic cardiac image sequences.In: FIMH’07:Proceedings of the4th international conference on Functional imaging and modeling of the heart,Berlin,Heidelberg,Springer-Verlag(2007)393–402。

Probabilistic Logic LearningLuc De RaedtInstitut f¨ur Informatik,Albert-Ludwigs-University, Georges-Koehler-Allee,Building079,D-79110Freiburg,Germanyderaedt@informatik.uni-freiburg.deKristian KerstingInstitut f¨ur Informatik,Albert-Ludwigs-University, Georges-Koehler-Allee,Building079,D-79110Freiburg,Germanykersting@informatik.uni-freiburg.deABSTRACTThe past few years have witnessed an significant interest in probabilistic logic learning,i.e.in research lying at the in-tersection of probabilistic reasoning,logical representations, and machine learning.A rich variety of different formalisms and learning techniques have been developed.This paper provides an introductory survey and overview of the state-of-the-art in probabilistic logic learning through the identi-fication of a number of important probabilistic,logical and learning concepts.Keywordsdata mining,machine learning,inductive logic program-ming,multi-relational data mining,uncertainty,probabilis-tic reasoning1.INTRODUCTIONOne of the central open questions in data mining and ar-tificial intelligence,concerns probabilistic logic learning,i.e. the integration of relational or logical representations,prob-abilistic reasoning mechanisms with machine learning and data mining principles.In the past few years,this ques-tion has received a lot of attention and various different ap-proaches have been developed,cf.[82;41;88;66;73;45;60; 61;57;81;52;77;2;55;87].This paper provides an intro-ductory survey and overview of those developments that lie at the intersection of logical(or relational)representations, probabilistic reasoning and learning,cf.Figure1.While do-ing so,we identify some of the key concepts and techniques underlying probabilistic logic learning.This,in turn,we hope,should allow the reader to appreciate the differences and commonalities between the various approaches and at the same time provide insight into some of the remaining challenges in probabilistic logic learning.Before starting our survey,let us specify what we mean by probabilistic logic learning.The term probabilistic in our context refers to the use of probabilistic representations and reasoning mechanisms grounded in probability theory,such as Bayesian networks[78;10;47],hidden Markov models[85; 84;22]and stochastic grammars[22;64].Such representa-tions have been successfully used across a wide range of ap-plications and have resulted in a number of robust models for reasoning about uncertainty.Application areas include ge-netics,computer vision,speech recognition andunderstand-Figure1:Probabilistic Logic Learning as the intersection of Probability,Logic,and Learning.ing,diagnostic and troubleshooting,information retrieval, software debugging,data mining and user modelling.The term logic in the present overview refers tofirst order logical and relational representations such as those studied within thefield of computational logic.The primary advan-tage of usingfirst order logic or relational representations is that it allows one to elegantly represent complex situa-tions involving a variety of objects as well as relations be-tween the objects.Consider e.g.the problem of building a logical troubleshooting system of a set of -puters are complex objects which are themselves composed of several complex objects.Furthermore,assume that even though the overall structure of the computers can be the same,their individual components can be highly different. Such situations can be elegantly modelled using relational orfirst order logic representations. E.g.,we could use the relation ram(r1,c1)to specify that computer c1has a RAM component of type r1,and cpu(p2,c1)and cpu(p3,c1)to de-note that c1is a multi-processor machine with two cpu’s p2 and p3.In addition to these base(or extensional)relations, one can also add virtual(or intensional)relations to describe generic knowledge about the domain.E.g.,consider the rule multiprocessor(C):−cpu(P1,C),cpu(P2,C),P1=P2 which defines the concept of a multi-processor machine(as a machine that possesses two different cpu’s).Representing the same information employing a propositional logic would require one to specify for each machine a separate model. The term learning in the context of probabilistic logic refers to deriving the different aspects of the probabilistic logic on the basis of data.Typically,one distinguishes various learning algorithms on the basis of the given data(fully or partially observable variables)or on the aspect being learned (the parameters of the probabilistic representation or its log-ical structure).The motivation for learning is that it is of-SIGKDD Explorations.Volume2,Issue2-page1ten easier to obtain data for a given application domain and learn the model than to build the model using traditional knowledge engineering techniques.So,probabilistic logic learning aims at combining its three underlying constituents:learning and probabilistic reason-ing withinfirst order logic representations.The recent inter-est in probabilistic logic learning may be explained by the growing body of work that has addressed pairwise intersec-tions of these domains:-Indeed,various techniques for probabilistic learning such as gradient-based methods,the family of EM algorithms or Markov Chain Monte Carlo methods have been devel-oped and exhaustively investigated in different commu-nities,such as in the Uncertainty in AI community for Bayesian networks and in the Computational Linguistic community for Hidden Markov Models.These techniques are not only theoretically sound,they have also resulted in entirely new technologies for,and revolutionary novel products in computer vision,speech recognition,medical diagnostics,troubleshooting systems,etc.Overviews of and introductions to probabilistic learning can be found in[20;84;44;8;48;22;64].-Inductive Logic Programming and multi-relational data mining studied logic learning,i.e.learning and data min-ing withinfirst order logical or relational representations. Inductive Logic Programming has significantly broadened the application domain of data mining especially in bio-and chemo-informatics(cf.the other papers in this vol-ume)and now represent some of the best-known exam-ples of scientific discovery by AI systems in the literature. Overviews of inductive logic learning and multi-relational data mining can be found in this volume and in[69;23]. -Early work on incorporating probabilities into logic pro-grams was done by Clark and McCabe[9]and by Shapiro[97].Subsequently,researchers such as Nils-son[75],Halpern[43],Ng and Subrahmanian[71],and Poole[82]have studied probabilistic logics from a knowl-edge representational perspective.The aim of this re-search is more a probabilistic characterization of logic than suitable representations for learning.Finally,in the past few years there have been some impor-tant attempts that address the full problem of probabilistic logic learning[59;30;67;31;14;53;51;92;68].The goal of this paper is to provide an introduction and overview to these works.In doing so,we restrict our atten-tion to those developments that address the intersection of probabilistic logic learning,cf.Figure1.Consequently,we will not discuss interesting work lying on boundaries such as Flach and Lachiche’s work on Na¨ıve Bayes for structured terms[27;62]and Craven and Slattery’s work on combining Na¨ıve Bayes with a relational rule learner[11].Giving an overview of the pairwise intersections(let alone the under-lying domains)would lead us too far(as it would require a book instead of a paper)and is therefore beyond the scope of this paper.Because probabilistic logic learning involves three domains,one can approach this topic from various directions.In this paper,motivated by the topic of this special issue,we start from a multi-relational and induc-tive logic programming perspective.The terminology and notation employed throughout this paper is based on com-putational logic rather than on relational databases becausealarm:−burglary,earthquake.johncalls:−alarm.marycalls:−alarm.Figure2:The alarm program.the relational model is not expressive enough to model the logical component of many of the probabilistic logical rep-resentations(e.g.,[88;66;90;52]).Nevertheless,we have attempted to be self-contained and to reduce the required logical machinery and background as much as possible. The paper is organized as follows:Sections2and3introduce the key concepts underlying computational logic and prob-abilistic reasoning formalisms,respectively;Section4then studiesfirst-order probabilistic logics,i.e.,how probabilistic reasoning and computational logic can be combined;after-wards,Section5then surveys various approaches to learning within those probabilistic logics,and,finally,in Section6, we conclude.2.INTRODUCTION TO LOGICAs logic programs will be used throughout this paper as the underlying knowledge representation framework,we now briefly introduce their key concepts.Afterwards,we show how state-of-the-art probabilistic representations em-ploy these concepts.2.1LogicThe choice of logic programs as the underlying represen-tation is motivated by its expressive power and general-ity.Indeed,logic programs allow us to represent relational databases,grammars and also programs.This will turn out to be useful when discussing commonalities and differences in the probabilistic relational or logical representations later on.In addition,logic programs are well-understood,have a clear semantics and are wide-spread.Three example logic programs are given in Figures2,3 and4.b.Thefirst one specifies some regularities in the alarm program(inspired on Judea Pearl’s famous example for Bayesian networks).The genetic program is a simple model of Mendel’s law applied to the color of plants.Finally, the grammar example encodes a context-free grammar.The corresponding type of logic program is known under the term ”definite clause grammar”.Let us now introduce some terminology.The predicates in the above examples include alarm/0,burglary/0,earthquake/0,...,pc/2,mc/2,pt/2, mother/2,father/2,s/2,vp/2,...Their arity(i.e.,the num-ber of arguments)has been listed explicitly.Predicates with arity0,such as alarm/0are sometimes called propositions. Furthermore,1,1m,1mf,...,g,green,...,dog,barks,...are constants and P,M,X,C,S,T,...are variables.Constants and variables are also terms.In addition,there exist structured terms such as[barks],shorthand for[](barks,nil),which contains the list functor[]/2,and the terms barks and nil(the empty list).Constants are often considered as functors of arity0.Atoms are predicate symbols followed by the necessary number of terms,e.g.,v([barks|T],T)and pt(P,white).We are now able to define the key concept of a definite clause.Definite clauses are formulas of the form A:−B1,...,B m where A and the B i are atoms and where all variables are understood to be universally quantified. E.g.,SIGKDD Explorations.Volume2,Issue2-page2mc(P,X):−mother(P,M),mc(M,X),pc(M,Y). mc(P,X):−mother(P,M),mc(M,Y),pc(M,X). pc(P,X):−father(P,F),mc(F,X),pc(F,Y). pc(P,X):−father(P,F),mc(F,Y),pc(F,X). mc(1mf,r).mother(1,1m).pc(1mf,g).father(1,1f).mc(1mm,g).mother(1m,1mm).pc(1mm,r).father(1m,1mf).mc(1f,g).pc(1f,g).pt(P,green):−mc(P,g),pc(P,g).pt(P,red):−mc(P,r).pt(P,red):−pc(P,r).Figure3:The genetic program.S→NP,VP. VP→V.NP→Det,Noun. Det→[the]. Noun→[dog].V→[barks].s(S,T):−np(S,S1),vp(S1,T).vp(S,T):−v(S,T).np(S,T):−det(S,S1),noun(S1,T). det([the|T],T).noun([dog|T],T).v([barks|T],T).(a)(b)Figure4:Context-free grammars:(a)A context-free gram-mar and(b)the corresponding grammar program.the definite clause pt(P,green):−mc(P,g),pc(P,g)can be read as“the phenotype of P is green if the m-chromosome of P contains the gene g and the p-chromosome of P contains the gene g.Because we will restrict attention to definite clauses only in the present paper,we will omit the term“definite”as long as no ambiguities arise.We call pt(P,green)the head of the clause,and mc(P,g),pc(P,g)the body.Clauses with an empty body,such as v([barks|T],T) are called facts.A clause program(or logic program for short)consists of a set of clauses.For a more thorough introduction to logic programming we refer to[63;26]. Within logic,two types of semantics can be distinguished: a model-theoretic and a proof-theoretic one.Because this distinction will also be useful from a probabilistic point of view,let us briefly introduce these two concepts.2.2A Model Theoretic ViewConsider the alarm program in Figure2.In this exam-ple,there arefive propositions that occur,i.e.{alarm, earthquake,marycalls,johncalls,burglary}.This is the so-called Herbrand base HB.It consists of all facts that one can construct with the predicate,constant and function symbols in the program.The Herbrand base–in a sense –specifies the set of all possible worlds described by the program.Indeed,for the alarm program,there are25=32 possible assignments of truth-values to the Herbrand base. These assignments are sometimes called(Herbrand)inter-pretations and they each describe a world.From a model-theoretic point of view,a logic program re-stricts the set of possible worlds.Indeed,if we interpret the clause alarm:−burglary,earthquake as an implica-tion,then the interpretations in which both burglary and earthquake are true,but alarm is not,do not satisfy this clause.The idea is that if we accept the clause as an axiom, then such worlds are impossible.More formally,we have that a(Herbrand)interpretation I satisfies a clause c if and only if for all substitutionsθsuch that body(c)θ⊆I also head(c)θ∈I.The interpretation I is called a model of c if it satisfies c.A substitutionθ={V1/t1,...,V n/t n},e.g.θ1= {P/1mm},is an assignment of terms t i to variables V i.Apply-ing a substitutionθto a term,atom or clause e yields the in-stantiated term,atom,or clause eθwhere all occurrences of the variables V i are simultaneously replaced by the term t i. Consider e.g.the clause c pt(P,green):−mc(P,g),pc(P,g) and the substitutionθ1.Applyingθ1to c yields the instan-tiated clause cθ1pt(1mm,green):−mc(1mm,g),pc(1mm,g). Furthermore,the reader may want to verify that the inter-pretation{mc(1m,g),pc(1m,g)}is not a model for the clause c.Finally,let us remark that an interpretation satisfies a set of clauses if it satisfies all the clauses in the set.The most important point about model theory–for our purposes–is that it specifies which worlds(i.e.,interpre-tations)are possible with respect to(i.e.,satisfy)a given logical theory.2.3A Proof Theoretic ViewAnother way of looking at logic programs comes from proof theory.From this perspective,a logic program can be used to prove that certain atoms,goals(see below)or clauses are logically entailed by the program.Consider,e.g.,the genetic program in Figure3.In this program,the fact pt(P,C)will be provable for any P and C whenever C is one of the possible colors for the plant P according to the axioms encoded in the program.Proofs are typically constructed using SLD-resolution pro-cedure,which we now briefly introduce.More formally, given a goal:−G1,...,G n and a clause G:−L1,...,L m such that G1θ=Gθ,applying resolution results in the goal :−L1θ,...,L mθ,G2θ,...,G nθ.A(successful)resolution refuta-tion of a goal:−G is then a sequence of resolution steps that leads to the empty goal:−.A failure does not end in the empty goal.For instance,in the genetic example,one can prove that pt(1f,green)is true,because of the following resolution derivation:−pt(1f,green).:−mc(1f,g),pc(1f,g).:−pc(1f,g).:−Resolution is employed by many theorem provers(such as Prolog).Indeed,when given the goal:−pt(1f,green),Pro-log would compute the above resolution derivation and an-swer yes.Furthermore,when given the goal:−pt(1f,X), Prolog would answer with the substitutions that make the goal true,i.e.,{X/green}.The set of possible resolution steps for a given goal is captured in an SLD-tree.Two ex-amples,one in the genetic domain,and one in the grammar domain are shown in Figure5.At this point it is impor-tant to see the connection between an SLD-derivation for the grammar domain and a traditional derivation using the context free grammar.Indeed,there is a one to one mapping between these two concepts for our grammar.SIGKDD Explorations.Volume2,Issue2-page3:- np([the,dog,barks],S1),vp(S1,[]).:- det([the,dog,barks],S1’),noun(S1’,S1),vp(S1,[]):- noun([dog,barks],S1),vp(S1,[]):- vp([barks,[]):- v([barks,[]):-:- mc(1mm,r). :- pc(1mm,r).mc(M,r),pc(M,Y).mc(F,r), pc(F,Y).mc(F,Y),pc(F,r)).:-Figure5:Examples of SLD trees.Root nodes are shaded. The upper tree is the SLD tree of querying the grammar program with:−s([the,dog,barks],[]).The lower tree is the SLD tree of querying the genetic program with :−pt(1mm,red).In both cases,there is only one refutation, i.e.successful derivation.There are thus two ways of viewing a logic program. Thefirst view,illustrated by the alarm program,is the model-theoretic view.It determines what the possible worlds(i.e.interpretations)are that satisfy the program. The second view,illustrated by the genetic program,is the proof-theoretic view.It determines what the possible proofs are with respect to a given goal.Of course,these two views are intimately connected.Indeed,for clause programs,we have that a(ground)fact has a resolution refutation if and only if it belongs to all(Herbrand)models of the program.3.PROBABILISTIC LOGICSThe model theoretic and proof theoretic views of logic are also useful from a probabilistic perspective.Indeed,many of the present probabilistic representations can be regarded as defining probabilities on possible worlds(e.g.,Bayesian networks)or on proofs(e.g.,stochastic context free gram-mars).As these probabilistic representations form the ba-sis for the probabilistic logics,we will now provide a short overview to these.We will use P to denote a probabil-ity distribution,e.g.P(X),and P to denote a probability Figure6:The graphical structure of the alarm Bayesian network.value,e.g.P(X=x).3.1Probabilities on Possible WorldsThe most popular formalism for defining probabilities on possible worlds is that of Bayesian networks.As an ex-ample of a Bayesian network,consider Judea Pearl’s fa-mous alarm network graphically illustrated in Figure 6. Formally speaking,a Bayesian network[78;10;47]is an augmented,directed acyclic graph,where each node corre-sponds to a random variable X i(e.g.,{alarm,earthquake, marycalls,johncalls,burglary})and each edge indicates a direct influence among the random variables.We will denote the set of parents of a node X i by Pa(X i), e.g., Pa(alarm)={earthquake,burglary}.A Bayesian network specifies a joint probability distribution P(X1,...,X n)over afixed,finite set{X1,...,X n}of random variables.As we will–for simplicity–assume that the random variables are all boolean,i.e.,they can have the domain{true,false}1, this actually amounts to specifying a probability distribu-tion on the set of all possible interpretations.Indeed,in our alarm example,the Bayesian network defines a probability distribution over truth-assignments to{alarm,earthquake, marycalls,johncalls,burglary}.A Bayesian network stipulates the following conditional in-dependency assumption:Each node X i in the graph is conditionally inde-pendent of any subset A of nodes that are notdescendants of X i given a joint state of Pa(X i),i.e.P(X i|A,Pa(X i))=P(X i|Pa(X i)).For example,marycalls is conditionally independent of earthquake and of burglary given a joint state of alarm.Be-cause of the conditional independence assumption,we can write down the joint probability density asP(X1,...,X n)=ni=1P(X i|Pa(X i))by applying the independency assumption to the chain rule expression of the joint probability distribution.There-fore,we associate with each node X i of the graph the conditional probability distribution P(X i|Pa(X i)), denoted as cpd(X i).The conditional probability distributions in our alarm examples would include P(alarm|earthquake,burglary),P(earthquake),etc. They are illustrated in Table1.So,Bayesian networks define a probability distribution on the possible worlds,i.e.,the interpretations.Furthermore, 1In general,the domains of a random variable can be con-tinuous or discrete as well,cf.[25].SIGKDD Explorations.Volume2,Issue2-page4P(burglary) (0.001,0.999)P(earthquake) (0.002,0.998)burglary earthquake P(alarm) true true(0.95,0.05) true false(0.94,0.06) false true(0.29,0.71) false false(0.001,0.999)alarm P(johncalls) true(0.90,0.10) false(0.05,0.95)alarm P(marycalls) true(0.70,0.30) false(0.01,0.99)Table1:The conditional probability distributions associ-ated with the nodes in the alarm network,cf.Figure6.The distributions are specified over{true,false}.When viewing the child-parents pairs as clauses,the clauses in the alarm program,cf.Figure2,specify some regularities of the alarm network.The corresponding conditional probability distri-butions can be associated with the clauses.the resulting probabilities induce a probability distribution at the level of propositions and propositional formulae.In-deed,reconsider the alarm example,and assume that we are interested in the probability of P(alarm=true).This probability can be obtained by marginalizing over the other variables,i.e.,P(a=t)=x i∈{t,f}P(a=t,b=x1,e=x2,m=x3,j=x4)where we have abbreviated the variables and states appro-priately.The probability of a propositional formula can be obtained similarly,it is simply the sum of the probabilities of the interpretations that are a model for the formula. The key limitation of Bayesian networks is that they lack the notion of an object.The possible worlds considered are ing Bayesian networks,it is impossible to model relations between objects,i.e.,relational or logical worlds.This problem is similar to that with traditional propositional mining and learning systems.3.2Probabilities on ProofsBecause of the closeness of proofs of logical formulae and derivations in grammar,we will start by discussing stochastic grammars,see e.g.[1;64].Consider therefore the stochastic context free grammar in Figure7(adapted from[1]),where we have omitted many of the terminal sym-bols for brevity.This context-free grammar is stochastic in that every grammar rule has a probability associated to it.Moreover,for every non-terminal symbol T the sum of the probabilities of the rules with T on the left hand side equals1.0,e.g.,for NP:0.2+0.8=1.0.Stochastic context-free grammars define probabilities on derivations(or,when mapped onto logic programs,on proofs).Indeed,one of the proofs(with associated probabilities)of the sentence”Rice flies like sand”goes as follows::−S.1.0:−NP VP.1.0:−N N VP.0.2:−Rice N VP.0.2·0.01:−Rice flies VP.0.2·0.01·0.01(1.0)S→NP,VP.(0.2)NP→N,N.(0.8)NP→N.(0.6)VP→V,NP.(0.4)VP→V,PP.(1.0)PP→P,NP.(0.01)N→[Rice].(0.01)N→[flies]....(0.02)V→[like].(0.02)V→[flies]....(0.05)P→[like]....Figure7:An example of a stochastic context-free gram-mar.The numbers associated with the grammar rules de-note probability values.Note that[Rice]does not denote a variable but the string Rice.:−Rice flies V NP.0.2·0.01·0.01·0.6:−Rice flies like NP.0.2·0.01·0.01·0.6·0.02:−Rice flies like N.0.2·0.01·0.01·0.6·0.02·0.8:−Rice flies like sand.0.2·0.01·0.01·0.6·0.02·0.8·0.1 Each time a rule is applied in a proof,the probability of the rule is multiplied with the overall probability.It is easy to verify that this induces a probability distribution over all possible proofs or successful derivations for the same non-terminal symbols.Failures(if any)are only due to non-matching terminals which can be considered to have0.0as probability label.Furthermore,the probabilities over the proofs induce a probability over the accepted sentences for each of the non-terminals.Indeed,consider again the sen-tence”Riceflies like sand”for which there are two proofs, one with probability p1(as illustrated above)and another one with probability p2.The sum of these probabilities spec-ifies the probability that a random sentence generated by the non-terminal symbol S is indeed”Riceflies like sand”. These distributions are useful for various purposes.For in-stance,in natural language processing,one may be inter-ested in either the most likely parse tree(or derivation)when dealing with ambiguity,or the total probability that a par-ticular sentence is derived.Also,in bioinformatics,there are numerous applications of stochastic grammars,most no-tably of(hidden)Markov models[84],which are essentially stochastic regular grammars.These are ed to deter-mine how likely it is that a given protein belongs to some fold[22].From a computational and logical perspective,the key lim-itation of stochastic context free grammars concerns their expressive power.Indeed,context free grammars(and therefore stochastic context free grammars)are not Turing-equivalent,i.e.they cannot be used as a programming lan-guage.Thus it is useful to lift the underlying grammar rep-resentation to that of logic programs,a Turing equivalent language,cf.[66].SIGKDD Explorations.Volume2,Issue2-page54.FIRST ORDER PROBABILISTICLOGICSBy now,everything is in place to introduce the key repre-sentational frameworks that combine probabilistic reasoning with logical or relational representations.Furthermore,in the spirit of the above presentation,we can distinguish them according to whether they define probabilities on interpre-tations or on proofs.4.1Probabilistic Logical ModelsThefirst class of representations extends Bayesian networks with abilities to define probabilities onfirst order logical or relational interpretations,cf.[82;41;73;45;57;81;31;52]. Important predecessors of these logical Bayesian networks discussed below,include the work by Breese,Charniak, Bacchus,Goldman,Poole and Wellmann[40;6;4;7;39]. These predecessors were largely based on the idea of knowl-edge based model construction(KBMC).In knowledge based model construction,a knowledge base(sometimes in the form of an annotated logic program)is used to describe sets of probabilistic models.A query then results in construct-ing a particular model that can be used to answer the query. Many of these approaches can represent Bayesian networks. However,they are not direct upgrades of Bayesian networks in the same way that the work by e.g.Haddawy[41]is.This may also explain why–to the authors’knowledge–Bayesian network learning techniques have not been applied to these representations.A central contribution in combining clausal logic with Bayesian networks is due to Peter Haddawy[41].It is based on the observation that the structure of a Bayesian network can essentially be represented as a set of(propositional) clauses,where there will be one clause for each node in the graph,cf.the alarm program and Bayesian network.This observation allows one to upgrade Bayesian networks toward first order logic by upgrading the corresponding proposi-tional clauses towards definite clauses.These clauses will specify the so-called intensional part I,i.e.the overall reg-ularities.In addition,we will need an extensional part E, which specifies the specific objects and situations under con-sideration.The distinction between extensional and inten-sional is akin to that made in database theory and compu-tational logic. E.g.,in the genetic program,the extension corresponds to the facts and the intension to the non-fact clauses.Given an extensional part E and an intensional part I,the central ideas are then-to view the atoms in the Herbrand interpretation as ran-dom variables2;they will constitute the nodes in the in-duced Bayesian network,-to view the instantiated clauses H:−B1,...,B m as defining the probabilistic dependencies,i.e.the B i will correspond to parents of the node H;therefore,a conditional probabil-ity distribution cpd needs to be associated to each clause. Before continuing to discuss some problems and extensions, let usfirst illustrate these ideas on our genetic example.In doing,so let us slightly redefine the predicates pc/2,mc/22More specifically,it only makes sense to talk about the atoms that are logically entailed by the program,i.e.that are true in all possible Herbrand interpretations,that is the atoms belonging to the so-called least Herbrand model.mc(P):−mother(P,M),mc(M),pc(M).pc(P):−father(P,F),mc(F),pc(F).mc(1mf).mother(1,1m).pc(1mf).father(1,1f).mc(1mm).mother(1m,1mm).pc(1mm).father(1m,1mf).mc(1f).pc(1f).pt(P):−mc(P),pc(P).Figure8:The truncated genetic program.Figure9:The structure of the Bayesian network induced by the truncated genetic program,see Figure8.All nodes nodes(with a non-empty set of parents)for the same pred-icate share the same associated cpds.and pt/2.We will now turn these two-place predicates into predicates of arity1,the idea being that pt(P)will be(in state)true if and only if the phenotype of the person P is green.The other predicates are dealt with in a similar way. Together with the facts for mother/2and father/2(listed in Figure3),the truncated facts for mc/1and pc/1result in the truncated genetic program as shown in Figure8.This program then induces a Bayesian network with the graphical structure shown in Figure9.All nodes(with a non-empty set of parents)for the same predicate(i.e.,mc/1,pc/1and pt/1)share the same local probability model.So,the cpd’s for mc(1m)and mc(1mm)are the same.There are some problems with this approach.Let us dicuss the most notable ones.First,the Bayesian network obtained is required to be acyclic.This is required because the se-mantics of cyclic Bayesian networks are not well-defined. Therefore,virtually all approaches require acyclicity or en-force other restrictions that guarantee acyclicity. Second,the domains of the random variables may not be boolean,i.e.,they may have more than two possible val-ues,or even be continuous.There are two ways to realize this.First,one could simply allow the domains of the ran-dom variables to be arbitrary,cf.[41;52].One side-effect is that boolean or logical random variables get mixed up withSIGKDD Explorations.Volume2,Issue2-page6。

2024年外研版英语小学五年级上学期复习试卷与参考答案一、听力部分（本大题有12小题，每小题2分，共24分）1、听力材料：A. Hello, are you Mr. Wang?B. Yes, I am. How can I help you?C. I’m looking for the science classroom.Question: Who is the speaker asking for Mr. Wang?A. The science teacher.B. The principal.C. The librarian.Answer: AExplanation: The speaker is asking for Mr. Wang because they are looking for the science classroom, indicating that Mr. Wang is the science teacher.2、听力材料：A. I have a red ball.B. I have two blue balls.C. I have three yellow balls.Question: How many balls does the second speaker have?A. One.B. Two.C. Three.Answer: BExplanation: The second speaker explicitly states that they have “two blue balls,” which is option B.3、What does the boy want to do this weekend?A. Go to the parkB. Visit a museumC. Watch a movieAnswer: C. Watch a movieExplanation: In the dialogue, you can hear the boy saying, “I would like to watch a new movie that’s coming out this weekend.” The other options are not mentioned in the conversation, making C the correct choice.4、Where is the girl going after school?A. To her friend’s houseB. To the libraryC. To the music clubAnswer: B. To the libraryExplanation: The girl states, “I need to go to the library after school to return some books and borrow a few more for my project.” This indicates she has plans to visit the library, which makes B the right answer. The otherlocations are not referenced in the audio clip.5、Listen to the conversation between two friends and answer the question.A. What is the weather like today?B. Where are they going for the weekend?C. What is the name of the museum?Answer: BExplanation: The question asks about the destination for the weekend. The conversation mentions, “We’re going to the Science Museum this weekend,” indicating the friends are planning to visit the Science Museum.6、Listen to the short dialogue and choose the correct answer.A. The girl wants to go to the park.B. The boy is not interested in the library.C. They are planning to do some reading.Answer: CExplanation: The dialogue goes something like this: “Do you want to go to the park?” “I think we should go to the library instead, we need to finish our reading for school.” The b oy suggests going to the library to do some reading, which means they are planning to read.7、Listen to the dialogue and choose the correct answer. (答案: B)A. The boy is going to the park.B. The girl is going to the library.Explanation: In the dialogue, the girl mentions she has books to return to thelibrary, indicating that her destination is the library, not the park.8、Listen to the conversation and choose the correct answer. (答案: A)A. They will meet at 3 PM.B. They will meet at 4 PM.Explanation: During the conversation, one person confirms the meeting time by saying, “See you at three,” which shows they have agreed to meet at 3 PM, not 4 PM.9.A: What is the weather like today?B: It’s sunny, but it will rain in the afternoon.Questions: What will the weather be like in the afternoon?A) SunnyB) RainyC) CloudyD) WindyAnswer: BExplanation: In the dialogue, B mentioned that “it will rain in the afternoon,” so the correct answer is B) Rainy.10.A: I saw a movie last night. It was really interesting.B: What was the name of the movie?A: It was called “The Magic Forest.”Questions: What was the name of the movie?A) The Magic ForestB) The Lost WorldC) The Secret GardenD) The Friendly DragonAnswer: AExplanation: In the dialogue, A explicitly said the name of the movie was “The Magic Forest,” so the correct answer is A) The Magic Forest.11、What does the boy want to do after school?A. Play footballB. Go swimmingC. Visit the libraryAnswer: C. Visit the libraryExplanation: In the dialogue, the boy mentions he has finished all his homework and wants to borrow some books about animals for his project.12、Where did the girl lose her backpack?A. At the parkB. In the classroomC. On the busAnswer: A. At the parkExplanation: The girl in the recording says she was playing with her friends at the park yesterday and realized her backpack was missing when she got home.二、选择题（本大题有12小题，每小题2分，共24分）1、What is the capital city of China?A. New YorkB. LondonC. BeijingD. TokyoAnswer: C. BeijingExplanation: Beijing is the capital city of China. The other options are the capitals of other countries.2、Which of the following is not a fruit?A. AppleB. BananaC. WatermelonD. TomatoAnswer: D. TomatoExplanation: Tomato is often considered a vegetable in culinary contexts, even though botanically it is classified as a fruit. The other options are all types of fruit.3、Choose the correct form of the verb to fill in the blank:“She_______her homework yesterday.”A. doesB. didC. doD. doneAnswer: B. didExplanation: The sentence is in the simple past tense, which describes a completed action in the past. The correct past tense form of the verb “do” is “did.”4、Select the appropriate preposition to complete the sentence:“The children are playing_______the playground.”A. onB. atC. inD. underAnswer: A. onExplanation: When referring to someone playing in an open area like a playground, the preposition “on” is typically used to indicate location.5.Choose the correct word to complete the sentence.The cat was_______on the mat.A. layingB. liesC. layD. laidAnswer: A. layingExplanation: The sentence is in the present continuous tense, which is used to describe an action happening at the moment of speaking. The correct form of the verb to be for the third person singular subject “The cat” is “is,” and the past participle form for the verb “lay” (to lie down) is “lying.” Therefore, “laying” is the correct choice.6.Read the sentence and choose the best word to fill in the blank.The sun_______up and the birds started singing.A. roseB. raisedC. raisingD. riseAnswer: A. roseExplanation: The sentence requires the simple past tense to describe an action that has already happened in the past. The correct past tense form of the verb “rise” (to go up) is “rose.” Therefore, “rose” is the correct choice. The other options are not in the correct tense or are not the correct form of the verb.7、Which of the following words has a different pronunciation for the underlined part?A. bikeB. busC. climbAnswer: C. climbExplanation: In this question, we are looking at the pronunciation of the letter ‘b’ or similar-sounding clusters in each word. Options A, B, and D all have the /b/ sound at the beginning, but in option C, “climb,” the ‘b’ is silent, making it the word with a different pronunciation for the underlined part.8、What will you say to your friend when you meet him in the afternoon?A. Good morning!B. Good afternoon!C. Good evening!D. Good night!Answer: B. Good afternoon!Explanation:This question tests the appropriate greeting based on the time of day. Since the scenario specifies that you meet your friend in the afternoon, the correct and polite way to greet them would be with “Good afternoon!” Other options are used at different times: “Good morning!” before noon, “Good evening!” in the late afternoon or early night, and “Good night!” when going to sleep or saying goodbye at night.9.Choose the correct word to complete the sentence.The cat is sitting under the tree, looking _______.A. happyC. angryD. quietAnswer: B. sadExplanation: The sentence describes a cat sitting under a tree, which implies a calm or possibly contemplative state. “Sad” fits the context as it suggests the cat might be in a thoughtful or melancholic mood.10.Select the word that best completes the sentence.My mother always says that eating vegetables is_______for my health.A. importantB. difficultC. boringD. expensiveAnswer: A. importantExplanation: The sentence is about the importance of eating vegetables for health. The word “important” correctly completes the sentence, emphasizing the value of vegetables in maintaining good health. The other options do not convey the same meaning in the context of health advice.11、The children are playing________the playground.A. atB. inC. onAnswer: C. onExplanation: The correct preposition to use here is “on” because “the playground” is an outdoor area where children play. The preposition “on” indicates that the action is taking place upon the surface of the playground.12、Which of these sentences uses the correct verb form?A. She go to school by bus.B. They goes to the park every weekend.C. He plays soccer after school.Answer: C. He plays soccer after school.Explanation: In option C, the verb “plays” correctly agrees with the singular subject “He”. Options A and B have subject-verb agreement errors; “go” s hould be “goes” for the third person singular in option A, and “goes” should be “go” for the plural subject “They” in option B.三、完型填空（10分）Passage:The sun was setting over the small town. The children were playing in the park, laughing and running around. Suddenly, a loud noise came from the direction of the old factory.1.The children were (A) happy (B) sad (C) angry (D) tired (E) scared when they heard the loud noise.2.The noise came from (A) the park (B) the school (C) the old factory (D)the hospital (E) the library.3.The children (A) ran to the factory (B) ran away from the factory (C) hid behind the trees (D) climbed the fence (E) ignored the noise.4.The old factory had been (A) closed for a long time (B) recently renovated(C) a popular tourist attraction (D) a place for children to play (E) a secret hideout.5.The noise was caused by (A) a fire (B) a storm (C) a construction project(D) a wildlife rescue (E) a special event in town.Answer:1.E2.C3.B4.A5.A四、阅读理解（26分）Reading ComprehensionPassage:The sun was setting over the small town of Willow Creek. The streets were empty, and the sky was painted with shades of orange, pink, and purple. It was a beautiful evening, and everyone was enjoying the peacefulness of the town.Alice was walking home from school with her friends, Sarah and Tom. Theyhad just finished their exams for the day and were feeling happy and relaxed. As they walked along, they noticed a small dog sitting by the side of the road. The dog was shivering and looked very hungry.“Let’s help the dog,” Alice suggested. Sarah and Tom agreed, and they continued to walk towards the dog. They found a house nearby and knocked on the door. The door opened, and an old man with a kind face looked out at them.“Is this your dog?” Alice ask ed.The old man shook his head. “No, I don’t think so. Maybe someone will come looking for it soon.”The children thanked the old man and continued their walk home. As they got closer to their houses, they saw a little girl running towards them. She was crying and holding a picture of a dog.“This is my dog, Max,” the girl said. “He got lost this afternoon. I’m so worried about him!”The children realized that the dog they had found was Max. They took the girl back to the old man’s house and showed him the picture of the dog. The old man smiled and said, “Thank you, children. I’ll take Max to his owner.”Max’s owner came out of the hou se, looking relieved and happy. She hugged the children and thanked them for helping her find Max.As the sun continued to set, the children felt a sense of joy and satisfaction. They had made a difference in someone’s life that day.Questions:1.What time of day is it when the story begins?A. MorningB. AfternoonC. EveningD. Night2.Why did Alice, Sarah, and Tom stop to help the dog?A. They wanted to play with the dog.B. They saw a picture of the dog and wanted to adopt it.C. They found the dog looking hungry and cold.D. They wanted to train the dog.3.What did the children do to help Max’s owner find Max?A. They put up a poster with Max’s picture in the town.B. They called the police to report a lost dog.C. They took Max back to the old man’s hou se and showed him the picture of the dog.D. They gave Max to the old man to take care of until Max’s owner was found.Answers:1.C. Evening2.C. They found the dog looking hungry and cold.3.C. They took Max back to the old man’s house and showed him the picture of the dog.五、写作题（16分）WritingTask: Write a short passage describing your favorite school subject and explain why you enjoy it so much. Use at least three reasons to support your answer. Remember to use proper grammar and punctuation.Example:My favorite school subject is Mathematics. There are several reasons why I enjoy it so much. Firstly, I find it challenging. Solving complex problems makes me feel proud of my intelligence. Secondly, Mathematics helps me in real-life situations. For instance, it helps me calculate budgets and make informed decisions. Lastly, I love the sense of accomplishment I get when I solve a problem that seems impossible. In conclusion, Mathematics is not only interesting but also beneficial for my personal growth.Analysis:1.Thematic Clarity: The passage clearly states the writer’s favorite subject, which is Mathematics, and proceeds to explain the reasons.2.Reasons Provided: The writer gives three specific reasons for enjoying Mathematics: the challenge, practical application, and the feeling of accomplishment.3.Supporting Details: Each reason is supported by a detail (e.g., solving complex problems, using Mathematics in real-life situations, solving seemingly impossible problems).4.Coherence: The passage flows logically from the introduction to the conclusion, maintaining a clear structure.5.Grammar and Punctuation: The passage uses correct grammar and punctuation, making it easy to read and understand.。

【关键字】学期安徽省宣城市四校2016-2017学年高二英语上学期期中联考试题本试卷分第I卷（选择题）和第II卷（非选择题）两部分（全卷满分150分，考试时间120分钟。

）第I卷第一部分听力（共两节，满分30分）第一节（共5 小题；每小题1.5 分）听下面5段对话，每段对话后有一个小题，从题中所给的A、B、C三个选项中选出最佳选项；听完每段对话后，你有10秒钟时间来回答有关小题和阅读下一小题；每段对话仅读一遍。

1. When does the office open?A. At 7:45.B. At 8:15.C. At 8:00.2. How much does the woman know about planting flowers?A. Only a little.B. Quite a lot.C. Nothing.3. Where does the conversation probably take place?A. At a train station.B. In a travel agency.C. In a park.4. What does the woman want to drink?A. White coffee without sugar.B. Black coffee with some sugar.C. White coffee with some sugar.5. What will the two speakers probably do first?A. Have breakfast.B. Visit the art museum.C. Read the guidebook.第二节（共15小题；每小题1.5分）听下面5段对话或独白,每段对话或独白后有几个小题,从题中所给的A、B、C三个选项中选出最佳选项,并标在试卷的相应位置。

听每段对话或独白前，你将有时间阅读各个小题，每小题5秒钟；听完后，各小题将给出5秒钟的作答时间。

multilingual processing system 多语讯息处理系统multilingual translation 多语翻译multimedia 多媒体multi-media communication 多媒体通讯multiple inheritance 多重继承multistate logic 多态逻辑mutation 语音转换mutual exclusion 互斥mutual information 相互讯息nativist position 语法天生假说natural language 自然语言natural language processing (nlp) 自然语言处理natural language understanding 自然语言理解negation 否定negative sentence 否定句neologism 新词语nested structure 崁套结构network 网络neural network 类神经网络neurolinguistics 神经语言学neutralization 中立化n-gram n-连词n-gram modeling n-连词模型nlp (natural language processing) 自然语言处理node 节点nominalization 名物化nonce 暂用的non-finite 非限定non-finite clause 非限定式子句non-monotonic reasoning 非单调推理normal distribution 常态分布noun 名词noun phrase 名词组np (noun phrase) completeness 名词组完全性object 宾语{语言学}/对象{信息科学}object oriented programming 对象导向程序设计[面向对向的程序设计]official language 官方语言one-place predicate 一元述语on-line dictionary 线上查询词典 [联机词点]onomatopoeia 拟声词onset 节首音ontogeny 个体发生ontology 本体论open set 开放集operand 操作数 [操作对象]optimization 最佳化 [最优化]overgeneralization 过度概化overgeneration 过度衍生paradigmatic relation 聚合关系paralanguage 附语言parallel construction 并列结构parallel corpus 平行语料库parallel distributed processing (pdp) 平行分布处理paraphrase 转述 [释意;意译;同意互训]parole 言语parser 剖析器 [句法剖析程序]parsing 剖析part of speech (pos) 词类particle 语助词part-of relation part-of 关系part-of-speech tagging 词类标注pattern recognition 型样识别p-c (predicate-complement) insertion 述补中插pdp (parallel distributed processing) 平行分布处理perception 知觉perceptron 感觉器 [感知器]perceptual strategy 感知策略performative 行为句periphrasis 用独立词表达perlocutionary 语效性的permutation 移位petri net grammar petri 网语法philology 语文学phone 语音phoneme 音素phonemic analysis 因素分析phonemic stratum 音素层phonetics 语音学phonogram 音标phonology 声韵学 [音位学;广义语音学] phonotactics 音位排列理论phrasal verb 词组动词 [短语动词]phrase 词组 [短语]phrase marker 词组标记 [短语标记]pitch 音调pitch contour 调形变化pivot grammar 枢轴语法pivotal construction 承轴结构plausibility function 可能性函数pm (phrase marker) 词组标记 [短语标记] polysemy 多义性pos-tagging 词类标记postposition 方位词pp (preposition phrase) attachment 介词依附pragmatics 语用学precedence grammar 优先级语法precision 精确度predicate 述词predicate calculus 述词计算predicate logic 述词逻辑 [谓词逻辑]predicate-argument structure 述词论元结构prefix 前缀premodification 前置修饰preposition 介词prescriptive linguistics 规定语言学 [规范语言学] presentative sentence 引介句presupposition 前提principle of compositionality 语意合成性原理privative 二元对立的probabilistic parser 概率句法剖析程序problem solving 解决问题program 程序programming language 程序设计语言 [程序设计语言] proofreading system 校对系统proper name 专有名词prosody 节律prototype 原型pseudo-cleft sentence 准分裂句psycholinguistics 心理语言学punctuation 标点符号pushdown automata 下推自动机pushdown transducer 下推转换器qualification 后置修饰quantification 量化quantifier 范域词quantitative linguistics 计量语言学question answering system 问答系统queue 队列radical 字根 [词干;词根;部首;偏旁]radix of tuple 元组数基random access 随机存取rationalism 理性论rationalist (position) 理性论立场 [唯理论观点]reading laboratory 阅读实验室real time 实时real time control 实时控制 [实时控制]recursive transition network 递归转移网络reduplication 重叠词 [重复]reference 指涉referent 指称对象referential indices 指针referring expression 指涉词 [指示短语]register 缓存器[寄存器]{信息科学}/调高{语音学}/语言的场合层级{社会语言学}regular language 正规语言 [正则语言]relational database 关系型数据库 [关系数据库]relative clause 关系子句relaxation method 松弛法relevance 相关性restricted logic grammar 受限逻辑语法resumptive pronouns 复指代词retroactive inhibition 逆抑制rewriting rule 重写规则rheme 述位rhetorical structure 修辞结构rhetorics 修辞学robust 强健性robust processing 强健性处理robustness 强健性schema 基朴school grammar 教学语法scope 范域 [作用域;范围]script 脚本search mechanism 检索机制search space 检索空间searching route 检索路径 [搜索路径]second order predicate 二阶述词segmentation 分词segmentation marker 分段标志selectional restriction 选择限制semantic field 语意场semantic frame 语意架构semantic network 语意网络semantic representation 语意表征 [语义表示] semantic representation language 语意表征语言semantic restriction 语意限制semantic structure 语意结构semantics 语意学sememe 意素semiotics 符号学sender 发送者sensorimotor stage 感觉运动期sensory information 感官讯息 [感觉信息]sentence 句子sentence generator 句子产生器 [句子生成程序]sentence pattern 句型separation of homonyms 同音词区分sequence 序列serial order learning 顺序学习serial verb construction 连动结构set oriented semantic network 集合导向型语意网络 [面向集合型语意网络]sgml (standard generalized markup language) 结构化通用标记语言shift-reduce parsing 替换简化式剖析short term memory 短程记忆sign 信号signal processing technology 信号处理技术simple word 单纯词situation 情境situation semantics 情境语意学situational type 情境类型social context 社会环境sociolinguistics 社会语言学software engineering 软件工程 [软件工程]sort 排序speaker-independent speech recognition 非特定语者语音识别spectrum 频谱speech 口语speech act assignment 言语行为指定speech continuum 言语连续体speech disorder 语言失序 [言语缺失]speech recognition 语音辨识speech retrieval 语音检索speech situation 言谈情境 [言语情境]speech synthesis 语音合成speech translation system 语音翻译系统speech understanding system 语音理解系统spreading activation model 扩散激发模型standard deviation 标准差standard generalized markup language 标准通用标示语言start-bound complement 接头词state of affairs algebra 事态代数state transition diagram 状态转移图statement kernel 句核static attribute list 静态属性表statistical analysis 统计分析statistical linguistics 统计语言学statistical significance 统计意义stem 词干stimulus-response theory 刺激反应理论stochastic approach to parsing 概率式句法剖析 [句法剖析的随机方法]stop 爆破音stratificational grammar 阶层语法 [层级语法]string 字符串[串；字符串]string manipulation language 字符串操作语言string matching 字符串匹配 [字符串]structural ambiguity 结构歧义structural linguistics 结构语言学structural relation 结构关系structural transfer 结构转换structuralism 结构主义structure 结构structure sharing representation 结构共享表征subcategorization 次类划分 [下位范畴化] subjunctive 假设的sublanguage 子语言subordinate 从属关系subordinate clause 从属子句 [从句;子句] subordination 从属substitution rule 代换规则 [置换规则] substrate 底层语言suffix 后缀superordinate 上位的superstratum 上层语言suppletion 异型[不规则词型变化] suprasegmental 超音段的syllabification 音节划分syllable 音节syllable structure constraint 音节结构限制symbolization and verbalization 符号化与字句化synchronic 同步的synonym 同义词syntactic category 句法类别syntactic constituent 句法成分syntactic rule 语法规律 [句法规则]syntactic semantics 句法语意学syntagm 句段syntagmatic 组合关系 [结构段的;组合的] syntax 句法systemic grammar 系统语法tag 标记target language 目标语言 [目标语言]task sharing 课题分享 [任务共享] tautology 套套逻辑 [恒真式;重言式;同义反复] taxonomical hierarchy 分类阶层 [分类层次] telescopic compound 套装合并template 模板temporal inference 循序推理 [时序推理] temporal logic 时间逻辑 [时序逻辑] temporal marker 时貌标记tense 时态terminology 术语text 文本text analyzing 文本分析text coherence 文本一致性text generation 文本生成 [篇章生成]text linguistics 文本语言学text planning 文本规划text proofreading 文本校对text retrieval 文本检索text structure 文本结构 [篇章结构]text summarization 文本自动摘要 [篇章摘要] text understanding 文本理解text-to-speech 文本转语音thematic role 题旨角色thematic structure 题旨结构theorem 定理thesaurus 同义词辞典theta role 题旨角色theta-grid 题旨网格token 实类 [标记项]tone 音调tone language 音调语言tone sandhi 连调变换top-down 由上而下 [自顶向下]topic 主题topicalization 主题化 [话题化]trace 痕迹trace theory 痕迹理论training 训练transaction 异动 [处理单位]transcription 转写 [抄写;速记翻译]transducer 转换器transfer 转移transfer approach 转换方法transfer framework 转换框架transformation 变形 [转换]transformational grammar 变形语法 [转换语法] transitional state term set 转移状态项集合transitivity 及物性translation 翻译translation equivalence 翻译等值性translation memory 翻译记忆transparency 透明性tree 树状结构 [树]tree adjoining grammar 树形加接语法 [树连接语法] treebank 树图数据库[语法关系树库]trigram 三连词t-score t-数turing machine 杜林机 [图灵机]turing test 杜林测试 [图灵试验]type 类型type/token node 标记类型/实类节点type-feature structure 类型特征结构typology 类型学ultimate constituent 终端成分unbounded dependency 无界限依存underlying form 基底型式underlying structure 基底结构unification 连并 [合一]unification-based grammar 连并为本的语法 [基于合一的语法] universal grammar 普遍性语法universal instantiation 普遍例式universal quantifier 全称范域词unknown word 未知词 [未定义词]unrestricted grammar 非限制型语法usage flag 使用旗标user interface 使用者界面 [用户界面]valence grammar 结合价语法valence theory 结合价理论valency 结合价variance 变异数 [方差]verb 动词verb phrase 动词组 [动词短语]verb resultative compound 动补复合词verbal association 词语联想verbal phrase 动词组verbal production 言语生成vernacular 本地话v-o construction (verb-object) 动宾结构vocabulary 字汇vocabulary entry 词条vocal track 声道vocative 呼格voice recognition 声音辨识 [语音识别]vowel 元音vowel harmony 元音和谐 [元音和谐]waveform 波形weak verb 弱化动词whorfian hypothesis whorfian 假说word 词word frequency 词频word frequency distribution 词频分布word order 词序word segmentation 分词word segmentation standard for chinese 中文分词规范word segmentation unit 分词单位 [切词单位]word set 词集working memory 工作记忆 [工作存储区]world knowledge 世界知识writing system 书写系统x-bar theory x标杠理论 ["x"阶理论]zipf's law 利夫规律 [齐普夫定律]。

Grammar—Non-restrictive relative clauses语法感知感知以下课文原句，完成方框下的小题1．This year’s Nobel Prize for Physiology or Medicine has been awarded to Tu Youyou (co-winner)，whose research led to the discovery of artemisinin，a crucial new treatment for malaria.2．In the beginning，Tu Youyou went to Hainan，where malaria was more common，to study malaria patients.3．From their research，they discovered and tested 380 distinct ancient Chinese medical treatments that showed promise in the fight against malaria.4．Using a lower temperature to draw out the extract，she found a substance that worked. 5．Later，the medicine was tested on malaria patients，most of whom recovered.6．This medicine，which was called artemisinin，soon became a standard treatment for malaria.(1)句1、2、5、6是非限制性定语从句，句3、4是限制性定语从句。

(2)句1中的关系词在定语从句中作定语。

(3)句2中的关系词在定语从句中作地点状语。