Rembrandt - a named-entity recognition framework

Rembrandt is a named entity recognition system specially crafted to annotate documents by classifying named entities and ground them into unique identifiers. Rembrandt played an important role within our research over geographic IR, thus evolving into a more capable framework where documents can be annotated, manually curated and indexed. The goal of this paper is to present Rembrandt's simple but powerful annotation framework to the NLP community.

Introduction
REMBRANDT is a named entity recognition (NER) system developed by the author, specially crafted to annotate documents by classifying named entities (NEs) and ground them into unique identifiers such as Wikipedia/DBpedia URLs (Cardoso, 2008). REMBRANDT was developed within the scope of the GREASE project, aiming to add geographic reasoning to search engines (Silva et al., 2006). GREASE required a specific tool to annotate explicit and implicit geographic content from documents, such as cities, rivers or postal codes, so they can be associated to the certain geographic area of interest for each document. As many placenames can be used on different contexts (to designate persons, organizations or even different places), REMBRANDT's goal is to recognize all kinds of NEs so they can be properlydisambiguated. REMBRANDT is also aware that some NEs are vague and/or ambiguous to the point that even humans cannot agree on a single semantic classification, so it allows NEs to have more than one classification to denote such vagueness and/or ambiguity that prevents a complete disambiguation. The REMBRANDT NER tool participated in 2008 on the Second HAREM, an evaluation contest for NER systems in Portuguese (Santos et al., 2008), it obtained an Fmeasure of 0.567 for the full NER task and ranked as the 2nd best system out of 10, and ranking first out of 8 systems for the PLACE only scenario with an F-measure of 0.625, showing good capabilities for detecting and disambiguating geographic places. REMBRANDT can also annotate English texts, although the performance of REMBRANDT for English is not yet determined. REMBRANDT played a role on the information retrieval (IR) systems that participated on GeoCLEF, a geographic information retrieval evaluation task , and in other more semantic-flavored retrieval evaluation tasks such as GikiCLEF (Cardoso et al., 2010) and NTCIR (Cardoso and Silva, 2010a). Within this evaluation environments, REMBRANDT evolved into a NER framework that also stores and indexes annotated documents, organises NEs and its grounded information in a relational database, and allows manual curation of its annotation and grounding information.
With a document collection fully annotated and curated with REMBRANDT's framework, one can query the database to extract information for a given NE (for instance, what are the most frequent NEs that appear on the same sentence with "Neil Armstrong [person]"?), and documents can be retrieved using semantic-based indexes in its document ranking procedure (as in "give me documents that contain references to Washington as a person, not the city").
The framework also provides a web interface where annotators can collaboratively curate annotated documents and all its extracted data, amending annotations for each document or for the whole collection.
The REMBRANDT is open-source code and avaliable at http://xldb.di.fc.ul.pt/Rembrandt/.  Figure 1 presents the architecture of the REMBRANDT framework, which is also described with more detail elsewhere (Cardoso and Silva, 2010b).In a nutshell, the framework is composed of i) the REMBRANDT NER tool that recognizes and grounds all entities from documents, ii) RENOIR, a semantic query reformulation module that handles query strings and performs semantic-flavored query reformulation for document retrieval, iii) SASKIA, a knowledge base for all knowledge resources and stored data, iv) an indexer that generates standard term index and semantic indexes for all extracted NEs, and v) the LGTE (Lucene with GeoTemporal Extensions), a retrieval and ranking module (Machado, 2009). As knowledge resources, REMBRANDT needs local copies of Wikipedia snapshots (article texts and SQL dumps), an access point (local or remote) to a DBpedia dataset, and access to Yahoo!'s web-service for the geographic ontology GeoPlanet TM (Yahoo!, 2010). REMBRANDT's classification strategy begins by mapping NEs to their corresponding Wikipedia and DBpedia pages, using DBpedia's ontology classes and Wikipedia categories to infer the semantic classification (Auer et al., 2007). Then, REMBRANDT applies a set of manually generated language-dependent rules, which represent the internal and external evidence for NEs for a given language, as in "city of X" or "X, Inc." This set of rules disambiguates NEs with more than one semantic classification and classifies NEs that were not mapped to a Wikipedia or DBpedia page.

User interface
RENOIR is the front-end module for document retrieval, and it can perform semantic-flavored query reformulations. The initial goal of RENOIR was to capture geographic terms in query strings, so that the query's geographic scope could be detected, and be used in the geographic information retrieval step. In a similar way as REMBRANDT, RENOIR also evolved and expanded its semantic capabilites so that the whole query string could be parsed for semantic clues for the user's intention. As such, RENOIR uses manuallyadded pattern rules to handle queries, namely query types (what, where, ...), subjects (as in "companies") and conditions (as in "founded in California" and "founded after 1980"). With the captured information, RENOIR estimates the expected answer types (EAT) and selects a reasoning strategy to reformulate the query. For example, Figure 3: SASKIA user interface RENOIR can query DBpedia for entities that match the given criteria, and add tem into the initial query string.
SASKIA stores the semantic information from the documents annotated by REMBRANDT, to prepare the index generation. Each NE is stored in a table, together with its terms and semantic classification. NEs successfully grounded to a DBpedia resource are also stored in an ENTITY table, and of those who also were grounded with a geographic place ID, into a GEOSCOPE table as well. SASKIA's data can afterwards be queried for several IE tasks; for example, indexing the geographic NEs of a document collection, to approximate the geographic area of interest of documents, and provide geographic reasoning which retrieving documents for a query with a geographic scope.
Figure presents the RENOIR interface to the LGTE search engine. In the example query "forest fires in Portugal", Portugal is recognised as a geographic entity, and such information is passed into the search engine so that documents with a geographic area of interest within the Portuguese territory have a higher ranking score. This is possible because all documents were previously annotated by REMBRANDT, their NEs stored in SASKIA, and the retrieval engine is capable of reason over the geo-graphic domain on the retrieval step, knowing for example that Porto is a city in Portugal and thus it is within the desired geographic scope.
Figure presents the SASKIA user interface showing an annotated document. Documents can be manually curated by several users, where NEs can be added or removed, change its semantic classification and its grounded information. Documents have a version control system where changes are stored in a different table. Thus, users can work simultaneously in the same document with their own changes, until the collection admin commits those changes permanently to the document. The document version control allows therefore conflict management and undo capabilities to the collection.
Changes can also be made to the stored NEs and grounded information, which impacts all document collections. For instance, if a given entity is not properly classified by REMBRANDT in every document, a single curation in the NE table will therefore trigger a document change on all affected documents. The framework also has a permission control so that users can have read, write or admin permissions to its collections, making it possible to distribute curation work among documents.

Conclusion
The REMBRANDT framework is now a mature tool, free and open source software, that can be therefore used by the NLP community on several IE-related tasks. REM-BRANDT started as a single NER tool specially crafted to be used for geographic information retrieval systems. As the GIR system evolved while participating into more semantic-flavored evaluation tasks, it also evolved as a full NER framework where rich semantic information extracted from documents is stored, grounded and organised for subsequent processing. This framework is also adapted to allow curation of its collections and extracted data by several users, in a collaborative and distributive way. With such curated information, the REMBRANDT NER tool can be further improved to take advantage of all previously annotated data and improve its performance specially on the hard, ambiguous NEs.


s2fieldsofstudy:
Computer Science
Linguistics

text:
A Ranking-based Approach to Word Reordering for Statistical Machine Translation

Long distance word reordering is a major challenge in statistical machine translation research. Previous work has shown using source syntactic trees is an effective way to tackle this problem between two languages with substantial word order difference. In this work, we further extend this line of exploration and propose a novel but simple approach, which utilizes a ranking model based on word order precedence in the target language to reposition nodes in the syntactic parse tree of a source sentence. The ranking model is automatically derived from word aligned parallel data with a syntactic parser for source language based on both lexical and syntactical features. We evaluated our approach on large-scale Japanese-English and English-Japanese machine translation tasks, and show that it can significantly outperform the baseline phrase-based SMT system.

Introduction
Modeling word reordering between source and target sentences has been a research focus since the emerging of statistical machine translation. In phrase-based models (Och, 2002;Koehn et al., 2003), phrase is introduced to serve as the fundamental translation element and deal with local reordering, while a distance based distortion model is used to coarsely depict the exponentially decayed word movement probabilities in language translation. Further work in this direction employed lexi- * This work has been done while the first author was visiting Microsoft Research Asia. calized distortion models, including both generative  and discriminative (Zens and Ney, 2006;Xiong et al., 2006) variants, to achieve finer-grained estimations, while other work took into account the hierarchical language structures in translation (Chiang, 2005;Galley and Manning, 2008).
Long-distance word reordering between language pairs with substantial word order difference, such as Japanese with Subject-Object-Verb (SOV) structure and English with Subject-Verb-Object (SVO) structure, is generally viewed beyond the scope of the phrase-based systems discussed above, because of either distortion limits or lack of discriminative features for modeling. The most notable solution to this problem is adopting syntax-based SMT models, especially methods making use of source side syntactic parse trees. There are two major categories in this line of research. One is tree-to-string model (Quirk et al., 2005; which directly uses source parse trees to derive a large set of translation rules and associated model parameters. The other is called syntax pre-reordering -an approach that re-positions source words to approximate target language word order as much as possible based on the features from source syntactic parse trees. This is usually done in a preprocessing step, and then followed by a standard phrase-based SMT system that takes the re-ordered source sentence as input to finish the translation. In this paper, we continue this line of work and address the problem of word reordering based on source syntactic parse trees for SMT. Similar to most previous work, our approach tries to rearrange the source tree nodes sharing a common parent to mimic the word order in target language. To this end, we propose a simple but effective ranking-based approach to word reordering. The ranking model is automatically derived from the word aligned parallel data, viewing the source tree nodes to be reordered as list items to be ranked. The ranks of tree nodes are determined by their relative positions in the target language -the node in the most front gets the highest rank, while the ending word in the target sentence gets the lowest rank. The ranking model is trained to directly minimize the mis-ordering of tree nodes, which differs from the prior work based on maximum likelihood estimations of reordering patterns (Li et al., 2007;Genzel, 2010), and does not require any special tweaking in model training. The ranking model can not only be used in a pre-reordering based SMT system, but also be integrated into a phrasebased decoder serving as additional distortion features.
We evaluated our approach on large-scale Japanese-English and English-Japanese machine translation tasks, and experimental results show that our approach can bring significant improvements to the baseline phrase-based SMT system in both preordering and integrated decoding settings.
In the rest of the paper, we will first formally present our ranking-based word reordering model, then followed by detailed steps of modeling training and integration into a phrase-based SMT system. Experimental results are shown in Section 5. Section 6 consists of more discussions on related work, and Section 7 concludes the paper.

Word Reordering as Syntax Tree Node Ranking
Given a source side parse tree T e , the task of word reordering is to transform T e to T e , so that e can match the word order in target language as much as possible. In this work, we only focus on reordering that can be obtained by permuting children of every tree nodes in T e . We use children to denote direct descendants of tree nodes for constituent trees; while for dependency trees, children of a node include not only all direct dependents, but also the head word itself. Figure 1 gives a simple example showing the word reordering between English and Japanese. By rearranging the position of tree nodes in the English  Figure 1: An English-to-Japanese sentence pair. By permuting tree nodes in the parse tree, the source sentence is reordered into the target language order. Constituent tree is shown above the source sentence; arrows below the source sentences show head-dependent arcs for dependency tree; word alignment links are lines without arrow between the source and target sentences.
parse tree, we can obtain the same word order of Japanese translation. It is true that tree-based reordering cannot cover all word movement operations in language translation, previous work showed that this method is still very effective in practice (Xu et al., 2009, Visweswariah et al., 2010. Following this principle, the word reordering task can be broken into sub-tasks, in which we only need to determine the order of children nodes for all non-leaf nodes in the source parse tree. For a tree node t with children {c 1 , c 2 , . . . , c n }, we rearrange the children to target-language-like order {c π(i 1 ) , c π(i 2 ) , . . . , c π(in) }. If we treat the reordered position π(i) of child c i as its "rank", the reorder-ing problem is naturally translated into a ranking problem: to reorder, we determine a "rank" for each child, then the children are sorted according to their "ranks". As it is often impractical to directly assign a score for each permutation due to huge number of possible permutations, a widely used method is to use a real valued function f to assign a value to each node, which is called a ranking function (Herbrich et al., 2000). If we can guarantee (f (i) − f (j)) and (π(i) − π(j)) always has the same sign, we can get the same permutation as π because values of f are only used to sort the children. For example, consider the node rooted at trying in the dependency tree in Figure 1. Four children form a list {I, am, trying, play} to be ranked. Assuming ranking function f can assign values {0.94, −1.83, −1.50, −1.20} for {I, am, trying, play} respectively, we can get a sorted list {I, play, trying, am}, which is the desired permutation according to the target.
More formally, for a tree node t with children {c 1 , c 2 , . . . , c n }, our ranking model assigns a rank f (c i , t) for each child c i , then the children are sorted according to the rank in a descending order. The ranking function f has the following form: where the θ j is a feature representing the tree node t and its child c i , and w j is the corresponding feature weight.

Ranking Model Training
To learn ranking function in Equation (1), we need to determine the feature set θ and learn weight vector w from reorder examples. In this section, we first describe how to extract reordering examples from parallel corpus; then we show our features for ranking function; finally, we discuss how to train the model from the extracted examples.

Reorder Example Acquisition
For a sentence pair (e, f, a) with syntax tree T e on the source side, we need to determine which reordered tree T e best represents the word order in target sentence f . For a tree node t in T e , if its children align to disjoint target spans, we can simply arrange them in the order of their corresponding target spans. Figure 2 shows a fragment of one sentence pair in our training data. Consider the subtree rooted at word "Problem". With the gold alignment, "Problem" is aligned to the 5th target word, and "with latter procedure" are aligned to target span [1, 3], thus we can simply put "Problem" after "with latter procedure". Recursively applying this process down the subtree, we get "latter procedure with Problem" which perfectly matches the target language. As pointed out by (Li et al., 2007), in practice, nodes often have overlapping target spans due to erroneous word alignment or different syntactic structures between source and target sentences. (b) in Figure 2 shows the automatically generated alignment for the sentence pair fragment. The word "with" is incorrectly aligned to the 6th Japanese word "ha"; as a result, "with latter procedure" now has target span [1, 6], while "Problem" aligns to [5,5]. Due to this overlapping, it becomes unclear which permutation of "Problem" and "with latter procedure" is a better match of the target phrase; we need a better metric to measure word order similarity between reordered source and target sentences. We choose to find the tree T e with minimal alignment crossing-link number (CLN) (Genzel, 2010) to f as our golden reordered tree. 1 Each crossing-link (i 1 j 1 , i 2 j 2 ) is a pair of alignment links crossing each other. CLN reaches zero if f is monotonically aligned to e , and increases as there are more word reordering between e and f . For example, in Figure 1, there are 6 crossing-links in the original tree: (e 1 j 4 , e 2 j 3 ), (e 1 j 4 , e 4 j 2 ), (e 1 j 4 , e 5 j 1 ), (e 2 j 3 , e 4 j 2 ), (e 2 j 3 , e 5 j 1 ) and (e 4 j 2 , e 5 j 1 ); thus CLN for the original tree is 6. CLN for the reordered tree is 0 as there are no crossing-links. This metric is easy to compute, and is not affected by unaligned words (Genzel, 2010).
We need to find the reordered tree with minimal CLN among all reorder candidates. As the number of candidates is in the magnitude exponential with respect to the degree of tree T e 2 , it is not always computationally feasible to enumerate through all candidates. Our solution is as follows.
First, we give two definitions.
• CLN (t): the number of crossing-links (i 1 j 1 , i 2 j 2 ) whose source words e i 1 and e i 2 both fall under sub span of the tree node t.
• CCLN (t): the number of crossing-links (i 1 j 1 , i 2 j 2 ) whose source words e i 1 and e i 2 fall under sub span of t's two different children nodes c 1 and c 2 respectively.
Apparently CLN of a tree T equals to CLN (root of T ), and CLN (t) can be recursively expressed as: Take the original tree in Figure 1 for example. At the root node trying, CLN(trying) is 6 because there are six crossing-links under its sub-span: (e 1 j 4 , e 2 j 3 ), (e 1 j 4 , e 4 j 2 ), (e 1 j 4 , e 5 j 1 ), (e 2 j 3 , e 4 j 2 ), (e 2 j 3 , e 5 j 1 ) and (e 4 j 2 , e 5 j 1 ). On the other hand, CCLN(trying) is 5 because (e 4 j 2 , e 5 j 1 ) falls under its child node play, thus does not count towards CCLN of trying.
From the definition, we can easily see that CCLN(t) can be determined solely by the order of t's direct children, and CLN (t) is only affected by discarded too many training instances and led to degraded reordering performance.
2 In our experiments, there are nodes with more than 10 children for English dependency trees. the reorder in the subtree of t. This observation enables us to divide the task of finding the reordered tree T e with minimal CLN into independently finding the children permutation of each node with minimal CCLN. Unfortunately, the time cost for the subtask is still O(n!) for a node with n children. Instead of enumerating through all permutations, we only search the Inversion Transduction Grammar neighborhood of the initial sequence (Tromble, 2009). As pointed out by (Tromble, 2009), the ITG neighborhood is large enough for reordering task, and can be searched through efficiently using a CKY decoder.
After finding the best reordered tree T e , we can extract one reorder example from every node with more than one child.

Features
Features for the ranking model are extracted from source syntax trees. For English-to-Japanese task, we extract features from Stanford English Dependency Tree (Marneffe et al., 2006), including lexicons, Part-of-Speech tags, dependency labels, punctuations and tree distance between head and dependent. For Japanese-to-English task, we use a chunkbased Japanese dependency tree (Kudo and Matsumoto, 2002). Different from features for English, we do not use dependency labels because they are not available from the Japanese parser. Additionally, Japanese function words are also included as features because they are important grammatical clues. The detailed feature templates are shown in Table 1.

Learning Method
There are many well studied methods available to learn the ranking function from extracted examples., ListNet (?) etc. We choose to use RankingSVM (Herbrich et al., 2000), a pair-wised ranking method, for its simplicity and good performance.
For every reorder example t with children {c 1 , c 2 , . . . , c n } and their desired permutation {c π(i 1 ) , c π(i 2 ) , . . . , c π(in) }, we decompose it into a set of pair-wised training instances. For any two children nodes c i and c j with i < j , we extract a positive instance if π(i) < π(j), otherwise we extract a negative instance. The feature vector for both positive instance and negative instance is (θ c i − θ c j ), where θ c i and θ c j are feature vectors for c i and c j E-J c l c l · dst c l · pct c l · dst · pct c l · lc l c l · rc l c l · lc l · dst c l · rc l · dst respectively. In this way, ranking function learning is turned into a simple binary classification problem, which can be easily solved by a two-class linear support vector machine.

Integration into SMT system
There are two ways to integrate the ranking reordering model into a phrase-based SMT system: the prereorder method, and the decoding time constraint method. For pre-reorder method, ranking reorder model is applied to reorder source sentences during both training and decoding. Reordered sentences can go through the normal pipeline of a phrase-based decoder.
The ranking reorder model can also be integrated into a phrase based decoder. Integrated method takes the original source sentence e as input, and ranking model generates a reordered e as a word order ref-erence for the decoder. A simple penalty scheme is utilized to penalize decoder reordering violating ranking reorder model's prediction e . In this paper, our underlying decoder is a CKY decoder following Bracketing Transduction Grammar (Wu, 1997;Xiong et al., 2006), thus we show how the penalty is implemented in the BTG decoder as an example. Similar penalty can be designed for other decoders without much effort.
Under BTG, three rules are used to derive translations: one unary terminal rule, one straight rule and one inverse rule: We have three penalty triggers when any rules are applied during decoding: • Discontinuous penalty f dc : it fires for all rules when source span of either A, A 1 or A 2 is mapped to discontinuous span in e .
• Wrong straight rule penalty f st : it fires for straight rule when source spans of A 1 and A 2 are not mapped to two adjacent spans in e in straight order.
• Wrong inverse rule penalty f iv : it fires for inverse rule when source spans of A 1 and A 2 are not mapped to two adjacent spans in e in inverse order.
The above three penalties are added as additional features into the log-linear model of the phrasebased system. Essentially they are soft constraints to encourage the decoder to choose translations with word order similar to the prediction of ranking reorder model.

Experiments
To test our ranking reorder model, we carry out experiments on large scale English-To-Japanese, and Japanese-To-English translation tasks.

Evaluation Data
We collect 3,500 Japanese sentences and 3,500 English sentences from the web. They come from a wide range of domains, such as technical documents, web forum data, travel logs etc. They are manually translated into the other language to produce 7,000 sentence pairs, which are split into two parts: 2,000 pairs as development set (dev) and the other 5,000 pairs as test set (web test).
Beside that, we collect another 999 English sentences from newswire domain which are translated into Japanese to form an out-of-domain test data set (news test).

Parallel Corpus
Our parallel corpus is crawled from the web, containing news articles, technical documents, blog entries etc. After removing duplicates, we have about 18 million sentence pairs, which contain about 270 millions of English tokens and 320 millions of Japanese tokens. We use Giza++ (Och and Ney, 2003) to generate the word alignment for the parallel corpus.

Monolingual Corpus
Our monolingual Corpus is also crawled from the web. After removing duplicate sentences, we have a corpus of over 10 billion tokens for both English and Japanese. This monolingual corpus is used to train a 4-gram language model for English and Japanese respectively.

Parsers
For English, we train a dependency parser as (Nivre and Scholz, 2004) on WSJ portion of Penn Treebank, which are converted to dependency trees using Stanford Parser (Marneffe et al., 2006). We convert the tokens in training data to lower case, and re-tokenize the sentences using the same tokenizer from our MT system.
For Japanese parser, we use CABOCHA, a chunk-based dependency parser (Kudo and Matsumoto, 2002). Some heuristics are used to adapt CABOCHA generated trees to our word segmentation.

Baseline System
We use a BTG phrase-based system with a Max-Ent based lexicalized reordering model (Wu, 1997;Xiong et al., 2006) as our baseline system for both English-to-Japanese and Japanese-to-English Experiment. The distortion model is trained on the same parallel corpus as the phrase table using a home implemented maximum entropy trainer.
In addition, a pre-reorder system using manual rules as (Xu et al., 2009) is included for the Englishto-Japanese experiment (ManR-PR). Manual rules are tuned by a bilingual speaker on the development set.

Ranking Reordering System
Ranking reordering model is learned from the same parallel corpus as phrase table. For efficiency reason, we only use 25% of the corpus to train our reordering model. LIBLINEAR (Fan et al., 2008) is used to do the SVM optimization for RankingSVM.
We test it on both pre-reorder setting (Rank-PR) and integrated setting (Rank-IT).  Table 2: BLEU(%) score on dev and test data for both E-J and J-E experiment. All settings significantly improve over the baseline at 95% confidence level. Baseline is the BTG phrase system system; ManR-PR is pre-reorder with manual rule; Rank-PR is pre-reorder with ranking reorder model; Rank-IT is system with integrated ranking reorder model.

End-to-End Result
From Table 2, we can see our ranking reordering model significantly improves the performance for both English-to-Japanese and Japanese-to-English experiments over the BTG baseline system. It also out-performs the manual rule set on English-to-Japanese result, but the difference is not significant.

Reordering Performance
In order to show whether the improved performance is really due to improved reordering, we would like to measure the reorder performance directly.
As we do not have access to a golden reordered sentence set, we decide to use the alignment crossing-link numbers between aligned sentence pairs as the measure for reorder performance.
We train the ranking model on 25% of our parallel corpus, and use the rest 75% as test data (auto). We sample a small corpus (575 sentence pairs) and do manual alignment (man-small). We denote the automatic alignment for these 575 sentences as (auto-small). From Table 3  our ranking reordering model indeed significantly reduces the crossing-link numbers over the original sentence pairs. On the other hand, the performance of the ranking reorder model still fall far short of oracle, which is the lowest crossing-link number of all possible permutations allowed by the parse tree. By manual analysis, we find that the gap is due to both errors of the ranking reorder model and errors from word alignment and parser. Another thing to note is that the crossing-link number of manual alignment is higher than automatic alignment. The reason is that our annotators tend to align function words which might be left unaligned by automatic word aligner.

Effect of Ranking Features
Here we examine the effect of features for ranking reorder model. We compare their influence on Rank-ingSVM accuracy, alignment crossing-link number, end-to-end BLEU score, and the model size. As Table 4 shows, a major part of reduction of CLN comes from features such as Part-of-Speech tags,  CLN is the crossing-link number per sentence on parallel corpus with automatically generated word alignment; BLEU is the BLEU score in percentage on web test set on Rank-IT setting (system with integrated rank reordering model); lex n means n most frequent lexicons in the training corpus.
dependency labels (for English), function words (for Japanese), and the distance and punctuations between child and head. These features also correspond to BLEU score improvement for End-to-End evaluations. Lexicon features generally continue to improve the RankingSVM accuracy and reduce CLN on training data, but they do not bring further improvement for SMT systems beyond the top 100 most frequent words. Our explanation is that less frequent lexicons tend to help local reordering only, which is already handled by the underlying phrasebased system.

Performance on different domains
From Table 2 we can see that pre-reorder method has higher BLEU score on news test, while integrated model performs better on web test set which contains informal texts. By error analysis, we find that the parser commits more errors on informal texts, and informal texts usually have more flexible translations. Pre-reorder method makes "hard" decision before decoding, thus is more sensitive to parser errors; on the other hand, integrated model is forced to use a longer distortion limit which leads to more search errors during decoding time. It is possible to use system combination method to get the best of both systems, but we leave this to future work.

Discussion on Related Work
There have been several studies focusing on compiling hand-crafted syntactic reorder rules. Collins et al. (2005), Wang et al. (2007), Ramanathan et al. (2008), Lee et al. (2010) have developed rules for German-English, Chinese-English, English-Hindi and English-Japanese respectively. Xu et al. (2009) designed a clever precedence reordering rule set for translation from English to several SOV languages. The drawback for hand-crafted rules is that they depend upon expert knowledge to produce and are limited to their targeted language pairs. Automatically learning syntactic reordering rules have also been explored in several work. Li et al. (2007) and Visweswariah et al. (2010) learned probability of reordering patterns from constituent trees using either Maximum Entropy or maximum likelihood estimation. Since reordering patterns are matched against a tree node together with all its direct children, data sparseness problem will arise when tree nodes have many children (Li et al., 2007); Visweswariah et al. (2010) also mentioned their method yielded no improvement when applied to dependency trees in their initial experiments. Genzel (2010) dealt with the data sparseness problem by using window heuristic, and learned reordering pattern sequence from dependency trees. Even with the window heuristic, they were unable to evaluate all candidates due to the huge number of possible patterns. Different from the previous approaches, we treat syntax-based reordering as a ranking problem between different source tree nodes. Our method does not require the source nodes to match some specific patterns, but encodes reordering knowledge in the form of a ranking function, which naturally handles reordering between any number of tree nodes; the ranking function is trained by well-established rank learning method to minimize the number of mis-ordered tree nodes in the training data.
Tree-to-string systems (Quirk et al., 2005; model syntactic reordering using minimal or composed translation rules, which may contain reordering involving tree nodes from multiple tree levels. Our method can be naturally extended to deal with such multiple level reordering. For a tree-tostring rule with multiple tree levels, instead of ranking the direct children of the root node, we rank all leaf nodes (Most are frontier nodes (Galley et al., 2006)) in the translation rule. We need to redesign our ranking feature templates to encode the reordering information in the source part of the translation rules. We need to remember the source side context of the rules, the model size would still be much smaller than a full-fledged tree-to-string system because we do not need to explicitly store the target variants for each rule.

Conclusion and Future Work
In this paper we present a ranking based reordering method to reorder source language to match the word order of target language given the source side parse tree. Reordering is formulated as a task to rank different nodes in the source side syntax tree according to their relative position in the target language. The ranking model is automatically trained to minimize the mis-ordering of tree nodes in the training data. Large scale experiment shows improvement on both reordering metric and SMT performance, with up to 1.73 point BLEU gain in our evaluation test.
In future work, we plan to extend the ranking model to handle reordering between multiple levels of source trees. We also expect to explore better way to integrate ranking reorder model into SMT system instead of a simple penalty scheme. Along the research direction of preprocessing the source language to facilitate translation, we consider to not only change the order of the source language, but also inject syntactic structure of the target language into source language by adding pseudo words into source sentences.


extfieldsofstudy:
Computer Science
Mathematics

s2fieldsofstudy:
Computer Science
Agricultural And Food Sciences

text:
Soil Data Analysis Using Classification Techniques and Soil Attribute Prediction

Agricultural research has been profited by technical advances such as automation, data mining. Today, data mining is used in a vast areas and many off-the-shelf data mining system products and domain specific data mining application soft wares are available, but data mining in agricultural soil datasets is a relatively a young research field. The large amounts of data that are nowadays virtually harvested along with the crops have to be analyzed and should be used to their full extent. This research aims at analysis of soil dataset using data mining techniques. It focuses on classification of soil using various algorithms available. Another important purpose is to predict untested attributes using regression technique, and implementation of automated soil sample classification.

Introduction
Data Mining is a very crucial research domain in recent research world. The techniques are useful to elicit significant and utilizable knowledge which can be perceived by many individuals. Data mining programs consists of diverse methodologies which are predominantly produced and used by commercial enterprises and biomedical researchers. These techniques are well disposed towards their respective knowledge domain. The use of standard statistical analysis techniques is both time consuming and expensive. Efficient techniques can be developed and tailored for solving complex soil data sets using data mining to improve the effectiveness and accuracy of the Classification of large soil data sets [1].
A soil test is the analysis of a soil sample to determine nutrient content, composition and other characteristics. Tests are usually performed to measure fertility and indicate deficiencies that need to be remedied [2]. The soil testing laboratories are provided with suitable technical literature on various aspects of soil testing, including testing methods and formulations of fertilizer recommendations [4]. It helps farmers to decide the extent of fertilizer and farm yard manure to be applied at various stages of the growth cycle of the crop.
In a research carried out by Leisa J. Armstrong, comparative study of current data mining techniques such as cluster analysis and statistical methods was carried out to establish the most effective technique. They used a large data set extracted from the Western Australia Department of Agriculture and Food (AGRIC) soils database to conduct this research. The experiments analyzed a small number of traits contained within the dataset to determine their effectiveness when compared with standard statistical techniques [3].
In our approach, we have developed an automated system for soil classification based on fertility . After obtaining the fertility class labels with the help of automated system, we carried out a comparative study of various classification techniques with the help of data mining tool known as WEKA. The dataset used, was collected from one of the soil testing laboratories in Pune District (Maharashtra, India).Rest of this paper focuses on the prediction of untested attributes. This research has implemented a very sound practical application of linear regression technique by forecasting an obscure property of the soil test.
The outcome of this research will result into substantial diminution in the price of these tests, which will save a lot of efforts and time of Indian soil testing laboratories.

Dataset Collection
The dataset is part of surveys which are carried out regularly in Pune District. Primary data for the soil survey are acquired by field sampling. These samples are then sent for chemical and physical analysis at the soil testing laboratories; hence this dataset was collected from a private soil testing lab in Pune. It contains information about number of soil samples taken from 3 regions of Pune district (Khed, Bhor, and Velhe). Dataset has 9 attributes and a total 1988 instances of soil samples. Table1 describes data collected for each soil sample.

Automated System
Soil classification system is essential for the identification of soil properties. Expert system can be a very powerful tool in identifying soils quickly and accurately .Traditional classification systems include use of tables, flow-charts. This type of manual approach takes a lot of time, hence quick, reliable automated system for soil classification is needed to make better utilization of technician's time [9].
We propose an automated system that has been developed for classifying soils based on fertility. Being rule-based system, it depends on facts, concepts, theories which are required for the implementation of this system. Rules for soil classification were collected from soil testing lab. The soil sample instances were classified into the fertility class labels as: Very High, High, Moderately High, Moderate, Low, and Very Low. These class labels for soil samples were obtained with the help of this system and they have been used further for comparative study of classification algorithms.

A Comparative Study Of Soil Classification
The classification of soil was considered critical to study because depending upon the fertility class of the soil the domain knowledge experts determines which crops should be taken on that particular soil and which fertilizers should be used for the same. The following section describes Naive Bayes, J48, JRip algorithms briefly.

Naive Bayes
A naive Bayes classifier is a simple probabilistic classifier based on applying Bayes' theorem with strong (naive) independence assumptions. Depending on the precise nature of the probability model, naive Bayes classifiers can be trained very efficiently in a supervised learning setting. An advantage of the naive Bayes classifier is that it only requires a small amount of training data to estimate the parameters (means and variances of the variables) necessary for classification [5].

J48 (C4.5)
J48 is an open source Java implementation of the C4.5 algorithm in the Weka data mining tool. C4.5 is a program that creates a decision tree based on a set of labeled input data. This decision tree can then be tested against unseen labeled test data to quantify how well it generalizes. This algorithm was developed by Ross Quinlan. It is an extension of Quinlan's earlier ID3 algorithm. C4.5 uses ID3 algorithm that accounts for continuous attribute value ranges, pruning of decision trees, rule derivation, and so on.
The decision trees generated by C4.5 can be used for classification, and for this reason, C4.5 is often referred to as a statistical classifier [6].

JRip
This algorithm implements a propositional rule learner, Repeated Incremental Pruning to Produce Error Reduction (RIPPER), which was proposed by William W. Cohen as an optimized version of IREP.
In this paper, three classification techniques (naïve Bayes, J48 (C4.5) and JRip) in data mining were evaluated and compared on basis of time, accuracy, Error Rate, True Positive Rate and False Positive Rate. Tenfold cross-validation was used in the experiment. Our studies showed that J48 (C4.5) model turned out to be the best classifier for soil samples.

Prediction Of Untested Attributes
Using regression algorithms like Linear Regression, Least Median Square, Simple Regression different attributes were predicted. According to these results the values of Phosphorous attribute was found to be most accurately predicted and it depends on least number of attributes.
When all attributes are numeric, linear regression is a natural and simple technique to consider for numeric prediction, but it suffers from disadvantage of linearity. If data exhibits non-linear dependency, it may not give good results .In this case, least median square technique is used. Median regression techniques incur high computational cost which often makes them infeasible for practical problems [8]. Several regression tests were carried out using WEKA data mining tool to predict untested numeric attributes. Linear-Regression test for predicting phosphor gave the best and accurate results. These predictions can be used to find out phosphor content without taking traditional chemical tests in soil testing labs, and this will eventually save a lot of time. Statistical results of these tests are given in Table3.
There were very limited variations amongst the predicted values of phosphor attribute. Though the Least Median of Squares algorithms is known to produce better results, we noticed that the accuracy of linear regression was relatively equivalent to that of least median of squares algorithm.  Here the Relative Absolute Error is nearly same for both the prediction algorithms. Even though Least Median Square regression gives better numeric predictions but the time taken to build the model is 67 times that of Linear Regression, hence computational cost used by Linear Regression is much lower than that of least median square technique.

Conclusion and Future Work
In this paper, we have proposed an analysis of the soil data using different algorithms and prediction technique. In spite the fact that the least median squares regression is known to produce better results than the classical linear regression technique, from the given set of attributes, the most accurately predicted attribute was "P" (Phosphorous content of JRip with the help of data mining tool WEKA. J48 is very simple classifier to make a decision tree, but it gave the best result in the experiment. In future, we contrive to build Fertilizer Recommendation System which can be utilized effectively by the Soil Testing Laboratories. This System will recommend appropriate fertilizer for the given soil sample and cropping pattern.


Adaptive scheduling in wireless sensor networks based on Potts model

Recent advances in wireless sensor network's technology have developed using this technology in various fields. For the importance and intense application of these networks, many efforts and researchers have been done to confront challenges. In this paper, to conquer one of the most important challenges of these networks, that is the limitation in energy resources, an adaptive scheduling algorithm based in Potts model was applied. According to this model, for every element of a system, q different states are considered. Each element converts its state to a new state or remains in that state due to its current state and its adjacent neighbours and with the effect of environment. In this project, this model was used in wireless sensor networks such that each sensor node is considered as an element of sensor network system and three active, inactive and standby states are defined for that node, which it selects one of these three states according to its current state and neighbours and environment effect and adapts its activity with the environment in a way that the least energy to be consumed. By comparing this algorithm and similar algorithm (with two states), it is observed that in identical conditions, Potts model with three states represents better results and more lifetimes for network.

INTRODUCTION
Wireless Sensor Networks (WSNs) [1] consist of the limited resources constrained devices, called sensor node, which communicate wirelessly to each other. These nodes are able to recognize changes of states occur in their impact domain and to report processed obtained data to respective centres. This property causes usage of this technology various applications. One of them is to tracking a target which is used for different applications in benign environments and also harsh ones. As mentioned previously, these networks are composed of nodes with limited energy resources; therefore, one of the most important challenges of these networks is energy limitation and attempt to increase the operational lifetime of network.
To use effectively of sensor networks, requires resourceaware operation and takes care of resource as much as possible; this is because sensor nodes are distributed only once and resources of sensor nodes are hardly ever rechargeable. To decrease energy consumption of network, it is usually tried to reduce node's duty cycles, but in such applications of Sensor networks for event detection and tracking, it is impossible to use a fixed rule to decrease node's duty cycles because events of interest are often rare and unpredictable. So if operational cycles of nodes are reduced, when nodes are not active, an event may occur, which its incorrect detection and tracking led to serious consequences and irreparable losses. Many researches were done due to wireless sensor Networks challenges and energy saving of these Networks, particularly in application of target tracking and various algorithms has been designed. One of these algorithms is A-SAS algorithm [2].
According to this algorithm, node's activities are scheduled such that network nodes could be able to detect targets all the time and determine target's path correctly. The main goal of this paper is to develop the algorithm such that in addition to detect objective correctly, nodes to be scheduled in a way that to consume the least energy. In the proposed algorithm, Potts model was used to develop the algorithm. This paper is organized as following: in section II, Ising model and Potts model will be introduced. The proposed algorithm will be studied in section III. In section IV, after evaluating algorithm efficiency, the algorithm will be compared with Ising model with the same conditions, and in the last section, conclusions will be given.

II. INTRODUCING ISING MODEL AND POTTS MODEL
The Potts model studies long term behaviour of complex systems. The model is able to investigate how the internal elements of the system react with one another based on certain characteristics that each element has. As these reactions take place macroscopic properties of the system will evolve. The Potts model has proven to be a very useful tool for simulating real systems. This model is used in the area of mathematical modelling so called statistical mechanics. In this model, the system is mapped to a graph such that graph nodes are the composing elements of the system, and its edges are the connections between these elements. For many applications it is expedient to assume that the graph has a regular structure, such as a lattice. On the vertices of these graphs anything can be considered, like atom, human, liquids and cells and even sensor node. Potts model, models how the nearest elements with different spins are related with other elements in the lattice [3].
This model is the extended of Ising model. In Ising model, two states are considered for each vertex, but in Potts model, q different states can be considered for every vertex. one another depending on their position on the lattice and their specific spins, there will be some measure of overall energy of the system. The function which measures the overall energy of a complex is the Hamiltonian [4].
Where, J is the interaction energy between adjacent elements of the system, and R i R is the spin value assigned to vertex i in the state , and a 1 is placed on edges between neighbours with like spins and a 0 on edges with elements which have different spins. p

A. 4 B The Potts Model Partition Function
For a graph with n vertices which its vertex can have q different spins, there are qP n P states. In fact, Potts model studies these states. The Potts model probability function is the function which calculates the probability of finding the lattice in a particular state. This function is dependent on Boltzmann distribution in statistical mechanics. Equation 2 shows above function with exponential distribution. This equation computes the probability of finding a particular state =1/ kT, T represents the temperature of the system, and k = 1.38 × 10P -23 P "joules/Kelvin" is the Boltzmann constant. However computing the partition function is only tractable for small lattices and small values of q. In general, this function is NPhard to compute.
Mathematicians explore properties of the Potts model partition function in a variety of ways. One way is to interpret it as an evaluation of the Tutte polynomial [5]. Another is to approximate the function using a simulation technique such as the Metropolis Algorithm [6]. This calculation is not exact; however, it allows researchers to use the Potts model to investigate complex applications.

III. 2 B THE PROPOSED METHOD
The idea of using Potts model in wireless sensor networks was expressed in an algorithm called A-SAS [2]. This algorithm is a distributed algorithm for wireless sensor networks to be able to detect and track rare and random events. However, in this algorithm, Ising model was used, that is for sensor node, just two active and inactive states were considered.
The algorithm which is represented here is extended of A-SAS algorithm using Potts model. Therefore, instead of two states for nodes, three states are considered and the third state as standby is added. The sensor nodes are assumed to be equipped with relevant sensing transducers and data processing algorithms as needed for detection and tracking of events under consideration. Node's task is that until resources are available, they detect and track rare events. Problem assumptions: (1) the network only deployed once. (2) Sensor nodes are static. The neighbours are fixed and predetermined. (3) Sensor node connected to its nearest neighbours through a short single-hop wireless communication.
Sensor network is considered as a weighted graph. If G is the set of all nodes of the sensor network and E is the set of all edges of graph G which each edge specifies the distance between two nodes of S that are connected together with single-hop and is determined by an edge (sR i R, sR j R) E. Function W expresses the weight of the graph's edges and has the value W((sR i R, sR j R)) = wR ij R. The strength of interaction this function is dictated by factors such as physical distance between the sensor nodes.
To describe the problem, some definitions have to be stated: (1) Markov Random Field: suppose R i R}R si RR S R be the neighbour set for a node sR i R. Then, with respect to , a random field is called a Markov Random Field (MRF) if and only if hold the Markov properties (I.e. P(wR i R KR R) = P(wR i R KR S\{i RR } R)) [7]. where, K R S\{i} R and KR R are configurations specified for node set S\{i} and R i R, respectively; P is the probability of random field F. This condition of Markov property ensures that the probability of a node being in a state depends only on its neighbours. (2) a set of nodes, c, which is a subset of S or equal to S(c S) is called clique, If a graph which has been induced on c by G is complete (that is each two nodes in G have mutual neighborhood with each other) [8]. (3) The Hamiltonian or energy function for a configuration K is defined as:

A. 5 B Formulating Potts model for a sensor network
In this section, Potts model of a sensor network, which was introduced as a Markov random field on graph G, is formulated. The base of this formulation is that the behaviour of each sensor node is strongly dependent on its nearest neighbours would be relatively distance nodes do not influence the behaviour of the desired node. Sensor nodes introduce as binary random variables and the potential of each clique is determined. This potential is used for modelling the behaviour of nodes. The objective here is to 1 DELTA EQUAL TO: equal to by definition. achieve the desired activity of the sensor network with a distributed probabilistic approach as explained below. The State (or label) set is selected as active, inactive, standby}, to be a discrete set. Random field F is defined as: And the clique potentials are defined as: Where |c| is the basis for determining the potential; is the time -dependent value of the node s i dependent on time ; is as a defined function ; and is the expected value of j . It should be noted that V c ( i j ) V c ( j i ). In the Potts-model, corresponds to the external magnetic field and wR ij Rto the coupling constant [9] and has positive values. Cliques of size more than two would require to investigate of neighbours of neighbours, which become cumbersome for a large |c|. Therefore, from the implementation vision, cliques with size greater than 2 are not raised in the formulation and the potential value will be considered as zero. The Hamilton that shows the energy of the K configuration is now written in terms of the potentials VR c RR Ras: According to equation (4), for supposed configuration K, conditional probability P(wR i R KR S\{i} R) is expressed as: Where, CR i Ris the set of all cliques containing node sR i R; and KP ' P is a configuration of K in which node sR i R is labeled with wP ' P R i R. Assume that H ( R i R) be node sR i R energy changes with its state change from one state into another. For node sR i R, the probability of activeness via equation (8) is stated as: Obtained results show that the probability of being active , is a function of current state of node sR i R and expecting behavior of its neighbours. In the absence of magnetic-field indicating the external effect in the sense of a function of , the node probabilities is only dependent on its neighbours. Sensor network system would have a fixed point at PP * P = 0.5. The fixed point of the system determines when there is no event in the sensor field, system's operations properties to be usual and natural ( R i R=0 i). Therefore, in order to apply a sensor network, selection potential of P* has to be defined and 0< P*<1. Let clique potentials be defined as: Where, And be the change in expecting spin of the neighbor. For considered P*, Therefore, And according equations (11) and (12), it is obtained that: Due to these equations, for the moment that node sR i R senses an event around itself, According to the state of node sR i R and its neighbours, delta calculated, and it is placed in equation (9) to obtain the probability of being active. The formulation that presented here essentially follows a hybrid model [10] where the clique potentials and the probabilities are functions of two variables, a discrete variable ( R i R) and a continuous variable . To adapt the dynamic operational environment, sensor nodes recursively calculate their probabilities based on their interactions of neighbours and most recently sensed data.

B. 6 B Implementing the algorithm
To implement this algorithm, OPNET simulating software was used [11]. Sensor network is simulated with two-dimensional of sensor nodes (like [12] or [13]). Sensor network was formed with nodes 35 (7*5) that exposure in the uniform network. Each node has at most four neighbours which are orthogonally adjacent to each other and the distance between each two adjacent nodes is about 2.5 units. Note that with nearest orthogonal neighbors, cliques of order 3 or more are not present. the measurable value R i Ris taken to balanced (normalized) the signal intensity that detected by the sensor node sR i R." Fig. 1" illustrates this network. Each node of it is considered as a Markov random field with three states. " Fig. 2" represents a node of sensor network.  For each sensor node can be considered four different Modes: (1) active (Sensing and snaffing for messages from neighbors); (2) inactive (neither sensing nor receiving); (3) standby (neither sensing nor receiving, in fact this mode is a status of inactive mode that sensors work in low power but wake up with a speed about 5 to 10 microseconds [14]) and; (4) transition (sending new p a to neighbours).
Each pair of sensor nodes can Exchange the information only if any two nodes are in active state and communication mode. Activity of a sensor network is scheduling with a random update of node states, which is shown in " Fig. 3". In a discrete scheduling, node s i compute based on current in each time step, and identified neighbours probabilities and broadcasts them to neighbours (note that in each broadcasting, sending packet is sent to those neighbour nodes, which are in distance w from node s i ). Nodes broadcast new only when it changes with by . This is done so that insignificant changes in P a are not broadcasted. Then, a sensor node assigns a state active inactive or standby in this time step with aprobability of for active state and ½-½ for inactive and standby states to itself. The stochastic local decision is to adapt to environment. To change the state of nodes, each node acts as following; if is greater than ½-½ , node s i assigns active state to itself and otherwise, since the probabilities of inactive and standby states are the same, it generates a random number. If generated number is greater than P*, node goes into standby state, otherwise converts into inactive one. Suppose that the network of " Fig. 1" was embedded in a border region to track enemy infiltration and it wants to pass a path which is determined on the scheme. Sensor nodes detect considered target along the path and declare obtained results from their detection to data sink. In the proposed algorithm, neighbourhood interaction enables a sensor node to schedule its activity for an event occurring in its vicinity. To show the effects of neighbourhood interaction, the event is simulated to be detected by only one sensor node.With respect to " Fig. 1", in initial moments, the first the only node which detects the target is s 29 , this condition will be shown in p a computation by setting 29 =1 for s 29 and i =0 for all nodes Si that i . Other parameters P*, ,w and BR 1 Rare set 0.3, 0.2, 2.5 and 10, respectively. in this algorithm for change in the activity probability to broadcast pP a P to all neighbors, pP a P considered to be equal to 0.02. In " Fig. 3", TR act R, TR inact R, TR standby Rwhich are time durations of active, inactive and standby states, respectively, are taken values 1, 2 and 1 second, here. Also, the ratio of energy consumption in each state and node state conversion into active one are defined as: ER Inactive R<ER standby R<ER standby_to_active R< ER Inactive_to_active R<ER active Table I [ 15] is used for pattern of energy consumption of sensor nodes.

IV. 3 B EVALUATING ALGORITHM EFFICIENCY
To evaluate the above algorithm efficiency, both algorithms were simulated and the results were recorded. Table II shows network lifetime (in terms of second) in Potts and Ising models.  Figure 4. Comparing network lifetime of Potts and Ising models.
According obtained results, it is observed that Potts model has longer lifetime than Ising model, in the same conditions. However, in both algorithms, by increasing w, network lifetime decreases. This is for that increasing w is increase the radius of broadcast and more nodes are in active state that causes more energy consumption and consequently, network lifetime reduction. In presented Figure, the counts of active nodes were shown at each instant of simulation. " Fig. 5" indicate that in this algorithm, which was simulated by Potts model, the count of nodes in standby state in terms of time is more than active nodes, i.e., when no event is detected around nodes, instead of becoming inactive that in case of need to become active with consuming high energy, nodes become standby that consume low energy and in case of need to become active, they consume very low energy. Figure 6. 1 T Energy changes diagram for a node of the wireless network in Potts and Ising model.
1 0 B ACKNOWLEDGMENT In this paper, Potts model was utilized to increase wireless sensor network lifetime and to enhance objective tracking. Due to this model, three states are considered for each sensor node: active, inactive and standby. Each node is scheduled such that if a sensor node detects a target or becomes informed of passing a target by receiving a signal from its neighbours, it becomes active and informs other neighbours around itself of this event. Otherwise, if no event exists around the node, first it becomes standby and after passing some time, if no event occurs, it become inactive. The advantage of standby state is that when a node is in this state, not only it consumes less energy than active state, but also changes its state into active state much faster and with less energy than inactive state in case of an event occurrence. Therefore, it saves energy. In diagrams, it is observed that the number of standby states is more than of active states. But, with increasing w, that is by increasing the radius of sending packets, network lifetime decreases because of communication Increase in both models.