Towards Building Open Knowledge Base From Programming Question-Answering Communities

Abstract

In this paper, we propose the rst system, so-called Open Programming Knowledge Extraction (OPKE), to automatically extract knowledge from programming Question-Answering (QA) communities. OPKE is the rst step of building a programming-centric knowledge base. Data mining and Natural Language Processing techniques are leveraged to identify duplicate questions and construct structured information. Preliminary evaluation shows the e ectiveness of OPKE.

Introduction

lead to high computation cost. Instead, we propose to use features of posts themselves to identify the duplicates. Speci cally, we transform every post title to a numerical vector and perform clustering on a set of vectors. Then we consider the posts that are closest to a master post (i.e., the original post) as the duplicate posts. After identifying and removing duplicate posts, we extract the key information from master posts and rewrite them to the \question" component of knowledge triples. This can be done by using NLP techniques. Finally, triples are constructed by given question and answer, as well as the tags. 2

Building Programming Knowledge Base The input of OPKE is the post contents of programming QA communities and the output is a set of triples. Figure 1 illustrates the extraction process which contains three main steps: Preprocessing, Question-answer Extraction and Triple Generation described as following.

Preprocessing

• Extract web page contents • Prune invalid posts • Obtain language specific tag

Question-Answer

Extraction

• Identify paraphrased questions • Select answer

Triple

Generation • Form triples with questions and answers <Q1; A1; “java”,”casting”,..> <Q2; A2; “java”,’’string”,..> <Q3; A3; “java”,..> … In the preprocessing step, OPKE parses the post content of the target programming community and extracts all the questions and answers. Invalid posts which have no accepted answers are pruned. For SO, post contents can be retrieved through Stack Exchange API2. The accepted answer and tags can be obtained by considering two parameters `AcceptedAnswerId ' and `Tags' respectively. 2 https://api.stackexchange.com/

Building Programming Community Knowledge Base { Parse master questions. We parse the master questions and rewrite it to capture the meaning of the questions. Our method is inspired by Open IE work [ 6 ], where dependency parsing has been applied to detect query meaning. We discuss OPKE parsing process using an example question \Java How do I convert from int to String?": i) remove language speci c words if exist (e.g. Java), ii) parse dependencies of questions (using method in [ 3 ], see Figure 2(a)), iii) identify subject (I ), if subject is rst person pronoun, then parse object part under the root in following steps (see the circled part in Figure 2(a)), iv) identify root action (covert ), v) identify relationship (hconvert; f romint; tostringi) and vi) rewrite question (\convert int to string"). For more details, please refer to [ 6 ].

convert How do

I from p o b j int to p o b j string

Final Triple for “Java - How do I convert int to string”: <“convert int to string”; “Normal ways would be Integer.toString(i) or String.valueOf(i)…….”; “java”> (a) Dependency Parse Tree (b) Generated Tuple

OPKE simply uses the accepted answer as the nal answer for a post. Although it might not be the best solution with highest votes, we believe that the questioner has the judgment on the solutions. After obtaining the questions and answers from previous steps, OPKE generate triples with the format of h\question"; \answer"; \tag1",\tag2",...i where question and answers are obtained from Section 2.2 and tags are obtained from Section 2.1. So for the example question, the triple is depicted as in Figure 2(b). 3

Experiment

The performance of OPKE system has been evaluated by performing extraction on Stack Over ow dump datasets3 (the version is 2016-06-13). We choose valid posts with non-empty titles and have accepted answers as the master posts. We obtain the duplicate and linked posts of these master posts. These result in 3 https://archive.org/details/stackexchange 339,990 posts in total. We de ne the evaluation metrics, clustering recall, as the number of correctly labeled posts (i.e., duplicate or not) divided by the total posts. Figure 3 reports the clustering recall rate on di erent number of clusters for duplicate and linked questions. Duplicate has higher recall rate than linked ones because linked posts do not always represent the same meaning with the master questions. When the cluster number is the 1/2000 of the total number of posts, the recall rate achieves the best.

40 10 36% 36% 38% 34%

Conclusion and Future Works In this work, we discuss our attempt to extract structured information from programming QA communities. The method, which combines data mining and NLP techniques, can also be applied to other QA communities. In the future, we will develop more ne-grained methods to identify paraphrased questions and consider the evolvement of programming language/tools. A programming-centric knowledge base and corresponding QA system will be built.

References

1. M. Ahasanuzzaman , M. Asaduzzaman , C. K. Roy , and K. A. Schneider . Mining Duplicate Questions in Stack Over ow . In Proc. of MSR 2016 .

2. Q. V. Le and T. Mikolov . Distributed Representations of Sentences and Documents . In Proc. of ICML 2014 .

3. M.-C. D. Marne e, B. MacCartney, and C. D. Manning . Generating Typed Dependency Parses From Phrase Structure Parses . In Proc. of LREC 2006 .

4. S. Nam , Y. Hahm , S. Nam , and K. Choi . SRDF: korean open information extraction using singleton property . In Proc. of ISWC 2015 ( Posters & Demonstrations Track) .

5. D. Sculley . Web-Scale K-Means Clustering . In Proc. of WWW 2010 .

6. P. Yin , N. Duan , B. Kao , J. Bao , and M. Zhou . Answering Questions with Complex Semantic Constraints on Open Knowledge Bases . In Proc. of CIKM 2015 .