Word Sense Discovery and Disambiguation

The work is based on the assumption that words with similar syntactic usage have similar meaning, which was proposed by Zellig S. Harris (1954,1968). We study his assumption from two aspects: Firstly, different meanings (word senses) of a word should manifest themselves in different usages (contexts), and secondly, similar usages (contexts) should lead to similar meanings (word senses). If we start with the different meanings of a word, we should be able to find distinct contexts for the meanings in text corpora. We separate the meanings by grouping and labeling contexts in an unsupervised or weakly supervised manner (Publication 1, 2 and 3). We are confronted with the question of how best to represent contexts in order to induce effective classifiers of contexts, because differences in context are the only means we have to separate word senses. If we start with words in similar contexts, we should be able to discover similarities in meaning. We can do this monolingually or multilingually. In the monolingual material, we find synonyms and other related words in an unsupervised way (Publication 4). In the multilingual material, we ?nd translations by supervised learning of transliterations (Publication 5). In both the monolingual and multilingual case, we first discover words with similar contexts, i.e., synonym or translation lists. In the monolingual case we also aim at finding structure in the lists by discovering groups of similar words, e.g., synonym sets. In this introduction to the publications of the thesis, we consider the larger background issues of how meaning arises, how it is quantized into word senses, and how it is modeled. We also consider how to define, collect and represent contexts. We discuss how to evaluate the trained context classi?ers and discovered word sense classifications, and ?nally we present the word sense discovery and disambiguation methods of the publications. This work supports Harris' hypothesis by implementing three new methods modeled on his hypothesis. The methods have practical consequences for creating thesauruses and translation dictionaries, e.g., for information retrieval and machine translation purposes. Keywords: Word senses, Context, Evaluation, Word sense disambiguation, Word sense discovery.

On the Origin of Ideas : An Abductivist Approach to Discovery

The purpose of this study is to analyze and develop various forms of abduction as a means of conceptualizing processes of discovery. Abduction was originally presented by Charles S. Peirce (1839-1914) as a "weak", third main mode of inference -- besides deduction and induction -- one which, he proposed, is closely related to many kinds of cognitive processes, such as instincts, perception, practices and mediated activity in general. Both abduction and discovery are controversial issues in philosophy of science. It is often claimed that discovery cannot be a proper subject area for conceptual analysis and, accordingly, abduction cannot serve as a "logic of discovery". I argue, however, that abduction gives essential means for understanding processes of discovery although it cannot give rise to a manual or algorithm for making discoveries. In the first part of the study, I briefly present how the main trend in philosophy of science has, for a long time, been critical towards a systematic account of discovery. Various models have, however, been suggested. I outline a short history of abduction; first Peirce's evolving forms of his theory, and then later developments. Although abduction has not been a major area of research until quite recently, I review some critiques of it and look at the ways it has been analyzed, developed and used in various fields of research. Peirce's own writings and later developments, I argue, leave room for various subsequent interpretations of abduction. The second part of the study consists of six research articles. First I treat "classical" arguments against abduction as a logic of discovery. I show that by developing strategic aspects of abductive inference these arguments can be countered. Nowadays the term 'abduction' is often used as a synonym for the Inference to the Best Explanation (IBE) model. I argue, however, that it is useful to distinguish between IBE ("Harmanian abduction") and "Hansonian abduction"; the latter concentrating on analyzing processes of discovery. The distinctions between loveliness and likeliness, and between potential and actual explanations are more fruitful within Hansonian abduction. I clarify the nature of abduction by using Peirce's distinction between three areas of "semeiotic": grammar, critic, and methodeutic. Grammar (emphasizing "Firstnesses" and iconicity) and methodeutic (i.e., a processual approach) especially, give new means for understanding abduction. Peirce himself held a controversial view that new abductive ideas are products of an instinct and an inference at the same time. I maintain that it is beneficial to make a clear distinction between abductive inference and abductive instinct, on the basis of which both can be developed further. Besides these, I analyze abduction as a part of distributed cognition which emphasizes a long-term interaction with the material, social and cultural environment as a source for abductive ideas. This approach suggests a "trialogical" model in which inquirers are fundamentally connected both to other inquirers and to the objects of inquiry. As for the classical Meno paradox about discovery, I show that abduction provides more than one answer. As my main example of abductive methodology, I analyze the process of Ignaz Semmelweis' research on childbed fever. A central basis for abduction is the claim that discovery is not a sequence of events governed only by processes of chance. Abduction treats those processes which both constrain and instigate the search for new ideas; starting from the use of clues as a starting point for discovery, but continuing in considerations like elegance and 'loveliness'. The study then continues a Peircean-Hansonian research programme by developing abduction as a way of analyzing processes of discovery.

Pentitol phosphate dehydrogenases: Discovery, characterization and use in D-arabitol and xylitol production by metabolically engineered Bacillus subtilis

The ultimate goal of this study has been to construct metabolically engineered microbial strains capable of fermenting glucose into pentitols D-arabitol and, especially, xylitol. The path that was chosen to achieve this goal required discovery, isolation and sequencing of at least two pentitol phosphate dehydrogenases of different specificity, followed by cloning and expression of their genes and characterization of recombinant arabitol and xylitol phosphate dehydrogenases. An enzyme of a previously unknown specificity, D-arabitol phosphate dehydrogenase (APDH), was discovered in Enterococcus avium. The enzyme was purified to homogenity from E. avium strain ATCC 33665. SDS/PAGE revealed that the enzyme has a molecular mass of 41 ± 2 kDa, whereas a molecular mass of 160 ± 5 kDa was observed under non-denaturing conditions implying that the APDH may exist as a tetramer with identical subunits. Purified APDH was found to have narrow substrate specificity, converting only D-arabitol 1-phosphate and D-arabitol 5-phosphate into D-xylulose 5-phosphate and D-ribulose 5-phosphate, respectively, in the oxidative reaction. Both NAD+ and NADP+ were accepted as co-factors. Based on the partial protein sequences, the gene encoding APDH was cloned. Homology comparisons place APDH within the medium chain dehydrogenase family. Unlike most members of this family, APDH requires Mn2+ but no Zn2+ for enzymatic activity. The DNA sequence surrounding the gene suggests that it belongs to an operon that also contains several components of phosphotransferase system (PTS). The apparent role of the enzyme is to participate in arabitol catabolism via the arabitol phosphate route similar to the ribitol and xylitol catabolic routes described previously. Xylitol phosphate dehydrogenase (XPDH) was isolated from Lactobacillus rhamnosus strain ATCC 15820. The enzyme was partially sequenced. Amino acid sequences were used to isolate the gene encoding the enzyme. The homology comparisons of the deduced amino acid sequence of L. rhamnosus XPDH revealed several similar enzymes in genomes of various species of Gram-positive bacteria. Two enzymes of Clostridium difficile and an enzyme of Bacillus halodurans were cloned and their substrate specificities together with the substrate specificity of L. rhamnosus XPDH were compared. It was found that one of the XPDH enzymes of C. difficile and the XPDH of L. rhamnosus had the highest selectivity towards D-xylulose 5-phosphate. A known transketolase-deficient and D-ribose-producing mutant of Bacillus subtilis (ATCC 31094) was further modified by disrupting its rpi (D-ribose phosphate isomerase) gene to create D-ribulose- and D-xylulose-producing strain. Expression of APDH of E. avium and XPDH of L. rhamnosus and C. difficile in D-ribulose- and D-xylulose-producing strain of B. subtilis resulted in strains capable of converting D-glucose into D-arabitol and xylitol, respectively. The D-arabitol yield on D-glucose was 38 % (w/w). Xylitol production was accompanied by co-production of ribitol limiting xylitol yield to 23 %.

Mass spectrometry and n-in-one analytics in early drug discovery: Combinatorial chemistry libraries, lipophilicity and absorption screening

This thesis describes current and past n-in-one methods and presents three early experimental studies using mass spectrometry and the triple quadrupole instrument on the application of n-in-one in drug discovery. N-in-one strategy pools and mix samples in drug discovery prior to measurement or analysis. This allows the most promising compounds to be rapidly identified and then analysed. Nowadays properties of drugs are characterised earlier and in parallel with pharmacological efficacy. Studies presented here use in vitro methods as caco-2 cells and immobilized artificial membrane chromatography for drug absorption and lipophilicity measurements. The high sensitivity and selectivity of liquid chromatography mass spectrometry are especially important for new analytical methods using n-in-one. In the first study, the fragmentation patterns of ten nitrophenoxy benzoate compounds, serial homology, were characterised and the presence of the compounds was determined in a combinatorial library. The influence of one or two nitro substituents and the alkyl chain length of methyl to pentyl on collision-induced fragmentation was studied, and interesting structurefragmentation relationships were detected. Two nitro group compounds increased fragmentation compared to one nitro group, whereas less fragmentation was noted in molecules with a longer alkyl chain. The most abundant product ions were nitrophenoxy ions, which were also tested in the precursor ion screening of the combinatorial library. In the second study, the immobilized artificial membrane chromatographic method was transferred from ultraviolet detection to mass spectrometric analysis and a new method was developed. Mass spectra were scanned and the chromatographic retention of compounds was analysed using extract ion chromatograms. When changing detectors and buffers and including n-in-one in the method, the results showed good correlation. Finally, the results demonstrated that mass spectrometric detection with gradient elution can provide a rapid and convenient n-in-one method for ranking the lipophilic properties of several structurally diverse compounds simultaneously. In the final study, a new method was developed for caco-2 samples. Compounds were separated by liquid chromatography and quantified by selected reaction monitoring using mass spectrometry. This method was used for caco-2 samples, where absorption of ten chemically and physiologically different compounds was screened using both single and nin- one approaches. These three studies used mass spectrometry for compound identification, method transfer and quantitation in the area of mixture analysis. Different mass spectrometric scanning modes for the triple quadrupole instrument were used in each method. Early drug discovery with n-in-one is area where mass spectrometric analysis, its possibilities and proper use, is especially important.

Essays on Market Microstructure: Price Discovery and Informed Trading

Market microstructure is “the study of the trading mechanisms used for financial securities” (Hasbrouck (2007)). It seeks to understand the sources of value and reasons for trade, in a setting with different types of traders, and different private and public information sets. The actual mechanisms of trade are a continually changing object of study. These include continuous markets, auctions, limit order books, dealer markets, or combinations of these operating as a hybrid market. Microstructure also has to allow for the possibility of multiple prices. At any given time an investor may be faced with a multitude of different prices, depending on whether he or she is buying or selling, the quantity he or she wishes to trade, and the required speed for the trade. The price may also depend on the relationship that the trader has with potential counterparties. In this research, I touch upon all of the above issues. I do this by studying three specific areas, all of which have both practical and policy implications. First, I study the role of information in trading and pricing securities in markets with a heterogeneous population of traders, some of whom are informed and some not, and who trade for different private or public reasons. Second, I study the price discovery of stocks in a setting where they are simultaneously traded in more than one market. Third, I make a contribution to the ongoing discussion about market design, i.e. the question of which trading systems and ways of organizing trading are most efficient. A common characteristic throughout my thesis is the use of high frequency datasets, i.e. tick data. These datasets include all trades and quotes in a given security, rather than just the daily closing prices, as in traditional asset pricing literature. This thesis consists of four separate essays. In the first essay I study price discovery for European companies cross-listed in the United States. I also study explanatory variables for differences in price discovery. In my second essay I contribute to earlier research on two issues of broad interest in market microstructure: market transparency and informed trading. I examine the effects of a change to an anonymous market at the OMX Helsinki Stock Exchange. I broaden my focus slightly in the third essay, to include releases of macroeconomic data in the United States. I analyze the effect of these releases on European cross-listed stocks. The fourth and last essay examines the uses of standard methodologies of price discovery analysis in a novel way. Specifically, I study price discovery within one market, between local and foreign traders.

Essays on the Role of Time in Price Discovery (summary section only)

The purpose of this thesis is to examine the role of trade durations in price discovery. The motivation to use trade durations in the study of price discovery is that durations are robust to many microstructure effects that introduce a bias in the measurement of returns volatility. Another motivation to use trade durations in the study of price discovery is that it is difficult to think of economic variables, which really are useful in the determination of the source of volatility at arbitrarily high frequencies. The dissertation contains three essays. In the first essay, the role of trade durations in price discovery is examined with respect to the volatility pattern of stock returns. The theory on volatility is associated with the theory on the information content of trade, dear to the market microstructure theory. The first essay documents that the volatility per transaction is related to the intensity of trade, and a strong relationship between the stochastic process of trade durations and trading variables. In the second essay, the role of trade durations in price discovery is examined with respect to the quantification of risk due to a trading volume of a certain size. The theory on volume is intrinsically associated with the stock volatility pattern. The essay documents that volatility increases, in general, when traders choose to trade with large transactions. In the third essay, the role of trade durations in price discovery is examined with respect to the information content of a trade. The theory on the information content of a trade is associated with the theory on the rate of price revisions in the market. The essay documents that short durations are associated with information. Thus, traders are compensated for responding quickly to information

Identification of molecules relevant for the invasiveness of fibrosarcomas and melanomas

Cancer is becoming the leading cause of deaths in the world. As 90% of all deaths from cancer are caused by metastasis, discovery of the mechanisms behind cancer cell invasion and metastasis is of utmost importance. Only new effective therapies targeting cancer progression can reduce cancer mortality rates. The aim of this study was to identify molecules that are relevant for tumor cell invasion and spreading in fibrosarcomas and melanomas, and to analyze their potential for cancer biomarkers or therapeutic targets. First, the gene expression changes of normal cells and transformed cells showing high invasiveness, S-adenosylmethionine decarboxylase (AdoMetDC)-transfected murine fibroblasts and human melanoma cells, were studied by microarray analyses. The function of the identified candidate molecules were then studied in detail in these cell lines. Finally, the physiological relevance of the identified changes was studied by immunohistochemical analyses of human sarcoma and melanoma specimens or by a mouse xenograft model. In fibrosarcoma cells, the most remarkable change detected was a dramatic up-regulation of the actin-sequestering molecule thymosin beta 4 (TB4), which was shown to be important for the transformed phenotype of the AdoMetDC-transfected cells (Amdc-s and -as). A sponge toxin latrunculin A, inhibiting the binding of TB4 to actin, was found to selectively inhibit the migration and invasion of these cells. Further, Amdc-s-induced mouse tumors and human high-grade sarcomas were found to show intense TB4 immunostaining. In addition to TB4, integrin subunits alfa 6 and beta 7 (ItgA6 and ItgB7) were found to be up-regulated in Amdc-s and -as cells. ItgA6 was shown to dimerize mainly with ItgB1 in Amdc-s. Inhibition of ItgA6 or ItgB1 function with neutralizing antibodies fully blocked the invasiveness of Amdc-s cells, and importantly also human HT-1080 fibrosarcoma cells, in three-dimensional (3D)-Matrigel mimicking tumor extracellular matrix (ECM). By immunohistochemical analyses, strong staining for ITGA6 was detected in human high-grade fibrosarcomas and other sarcomas, especially at the invasion fronts of the tumors. In the studied melanoma cell lines, the expression levels of the adhesion-related ECM proteins tenascin-C (TN-C), fibronectin (FN), and transforming growth factor beta-induced (TGFBI) were found to be highly up-regulated. By immunohistochemistry, intense TN-C and FN staining was detected in invasive and metastatic melanoma tumors, showing co-localization (together with procollagen-I) in tubular meshworks and channels around the invading melanoma cells. In vitro, TN-C and FN were further found to directly stimulate the migration of melanoma cells in 3D-collagen-I matrix. The third candidate protein, TGFBI, was found to be an anti-adhesive molecule for melanoma cells, and knockdown of its expression in metastatic melanoma cells (TGFBI-KD cells) led to dramatically impaired tumor growth in immunocompromized mice. Interestingly, the control tumors showed intense TGFBI immunostaining in the invasion fronts, showing partial co-localization with the fibrillar FN staining, whereas the small TGFBI-KD cell-induced tumors displayed amorphous, non-fibrillar FN staining. These data suggest an important role for TGFBI in FN fibrillogenesis and melanoma progression. In conclusion, we have identified several invasion-related molecules, which show potential for cancer diagnostic or prognostic markers, or therapeutic targets. Based on our previous and present fibrosarcoma studies, we propose the possibility of using ITGA6 antagonists (affecting tumor cell adhesion) in combination with TB4 inhibitors (affecting tumor cell migration) and cathepsin L inhibitors (affecting the degradation of basement membrane and ECM proteins) for the treatment of fibrosarcomas and other tumors overexpressing these molecules. With melanoma cells, in turn, we point to the importance of three secreted ECM proteins, TN-C, FN, and TGFBI, in melanoma progression. Of these, especially the potential of TN-C as a prognostic melanoma biomarker and TGFBI as a promising therapeutic target molecule are clearly worth additional studies.

Discovery of oxidative enzymes for food engineering : Tyrosinase and sulfhydryl oxidase

Enzymes offer many advantages in industrial processes, such as high specificity, mild treatment conditions and low energy requirements. Therefore, the industry has exploited them in many sectors including food processing. Enzymes can modify food properties by acting on small molecules or on polymers such as carbohydrates or proteins. Crosslinking enzymes such as tyrosinases and sulfhydryl oxidases catalyse the formation of novel covalent bonds between specific residues in proteins and/or peptides, thus forming or modifying the protein network of food. In this study, novel secreted fungal proteins with sequence features typical of tyrosinases and sulfhydryl oxidases were iden-tified through a genome mining study. Representatives of both of these enzyme families were selected for heterologous produc-tion in the filamentous fungus Trichoderma reesei and biochemical characterisation. Firstly, a novel family of putative tyrosinases carrying a shorter sequence than the previously characterised tyrosinases was discovered. These proteins lacked the whole linker and C-terminal domain that possibly play a role in cofactor incorporation, folding or protein activity. One of these proteins, AoCO4 from Aspergillus oryzae, was produced in T. reesei with a production level of about 1.5 g/l. The enzyme AoCO4 was correctly folded and bound the copper cofactors with a type-3 copper centre. However, the enzyme had only a low level of activity with the phenolic substrates tested. Highest activity was obtained with 4-tert-butylcatechol. Since tyrosine was not a substrate for AoCO4, the enzyme was classified as catechol oxidase. Secondly, the genome analysis for secreted proteins with sequence features typical of flavin-dependent sulfhydryl oxidases pinpointed two previously uncharacterised proteins AoSOX1 and AoSOX2 from A. oryzae. These two novel sulfhydryl oxidases were produced in T. reesei with production levels of 70 and 180 mg/l, respectively, in shake flask cultivations. AoSOX1 and AoSOX2 were FAD-dependent enzymes with a dimeric tertiary structure and they both showed activity on small sulfhydryl compounds such as glutathione and dithiothreitol, and were drastically inhibited by zinc sulphate. AoSOX2 showed good stabil-ity to thermal and chemical denaturation, being superior to AoSOX1 in this respect. Thirdly, the suitability of AoSOX1 as a possible baking improver was elucidated. The effect of AoSOX1, alone and in combi-nation with the widely used improver ascorbic acid was tested on yeasted wheat dough, both fresh and frozen, and on fresh water-flour dough. In all cases, AoSOX1 had no effect on the fermentation properties of fresh yeasted dough. AoSOX1 nega-tively affected the fermentation properties of frozen doughs and accelerated the damaging effects of the frozen storage, i.e. giving a softer dough with poorer gas retention abilities than the control. In combination with ascorbic acid, AoSOX1 gave harder doughs. In accordance, rheological studies in yeast-free dough showed that the presence of only AoSOX1 resulted in weaker and more extensible dough whereas a dough with opposite properties was obtained if ascorbic acid was also used. Doughs containing ascorbic acid and increasing amounts of AoSOX1 were harder in a dose-dependent manner. Sulfhydryl oxidase AoSOX1 had an enhancing effect on the dough hardening mechanism of ascorbic acid. This was ascribed mainly to the produc-tion of hydrogen peroxide in the SOX reaction which is able to convert the ascorbic acid to the actual improver dehydroascorbic acid. In addition, AoSOX1 could possibly oxidise the free glutathione in the dough and thus prevent the loss of dough strength caused by the spontaneous reduction of the disulfide bonds constituting the dough protein network. Sulfhydryl oxidase AoSOX1 is therefore able to enhance the action of ascorbic acid in wheat dough and could potentially be applied in wheat dough baking.

A Hub System for Cloud-Computing Based Business-Collaboration: Automating Ontology-Enabled Electronic Business-Service Discovery

The management and coordination of business-process collaboration experiences changes because of globalization, specialization, and innovation. Service-oriented computing (SOC) is a means towards businessprocess automation and recently, many industry standards emerged to become part of the service-oriented architecture (SOA) stack. In a globalized world, organizations face new challenges for setting up and carrying out collaborations in semi-automating ecosystems for business services. For being efficient and effective, many companies express their services electronically in what we term business-process as a service (BPaaS). Companies then source BPaaS on the fly from third parties if they are not able to create all service-value inhouse because of reasons such as lack of reasoures, lack of know-how, cost- and time-reduction needs. Thus, a need emerges for BPaaS-HUBs that not only store service offers and requests together with information about their issuing organizations and assigned owners, but that also allow an evaluation of trust and reputation in an anonymized electronic service marketplace. In this paper, we analyze the requirements, design architecture and system behavior of such a BPaaS-HUB to enable a fast setup and enactment of business-process collaboration. Moving into a cloud-computing setting, the results of this paper allow system designers to quickly evaluate which services they need for instantiationg the BPaaS-HUB architecture. Furthermore, the results also show what the protocol of a backbone service bus is that allows a communication between services that implement the BPaaS-HUB. Finally, the paper analyzes where an instantiation must assign additional computing resources vor the avoidance of performance bottlenecks.

Algorithms for Exact Structure Discovery in Bayesian Networks

Bayesian networks are compact, flexible, and interpretable representations of a joint distribution. When the network structure is unknown but there are observational data at hand, one can try to learn the network structure. This is called structure discovery. This thesis contributes to two areas of structure discovery in Bayesian networks: space--time tradeoffs and learning ancestor relations. The fastest exact algorithms for structure discovery in Bayesian networks are based on dynamic programming and use excessive amounts of space. Motivated by the space usage, several schemes for trading space against time are presented. These schemes are presented in a general setting for a class of computational problems called permutation problems; structure discovery in Bayesian networks is seen as a challenging variant of the permutation problems. The main contribution in the area of the space--time tradeoffs is the partial order approach, in which the standard dynamic programming algorithm is extended to run over partial orders. In particular, a certain family of partial orders called parallel bucket orders is considered. A partial order scheme that provably yields an optimal space--time tradeoff within parallel bucket orders is presented. Also practical issues concerning parallel bucket orders are discussed. Learning ancestor relations, that is, directed paths between nodes, is motivated by the need for robust summaries of the network structures when there are unobserved nodes at work. Ancestor relations are nonmodular features and hence learning them is more difficult than modular features. A dynamic programming algorithm is presented for computing posterior probabilities of ancestor relations exactly. Empirical tests suggest that ancestor relations can be learned from observational data almost as accurately as arcs even in the presence of unobserved nodes.