Supporting architecture documentation: a comparison of two ontologies for knowledge retrieval

Context: Software architecture documentation is used to communicate architectural knowledge. It is often difficult for document users to find all the architectural knowledge they need to do their tasks, and this results in wasted time and mistakes during development. Objective: In this paper we investigate how ontology-based documentation may support users in finding the architectural knowledge they need. Method: We executed a controlled experiment to test for differences in knowledge retrieval efficiency and effectiveness between two groups of master students that used two ontologies built from different understandings of the architectural knowledge needs of document users. Results: Use of the ontology built based on a better understanding of architectural knowledge needs was significantly more efficient or effective for retrieving part of the knowledge needed by document users. We analysed participants' search actions and identified which organisation of knowledge in the ontologies resulted in efficient and effective knowledge retrieval. Conclusion: We found that an improved understanding of knowledge needs allows for the construction of an ontology from which document users retrieve knowledge more efficiently and effectively. In some cases we found that the ontology support for knowledge needs had to be traded off against ontology design criteria.

INTRODUCTION
It is recognized by Bass et al. in [3] and Clements et al. in [6] that even a perfect Software Architecture (SA) is essentially useless if it is not understood; proper documentation should have enough detail, no ambiguity, and it must be organised such that users can quickly find information and answer their questions [19]. Documentation of software architecture serves three important purposes: it is used for education, system analysis, and it is the primary vehicle for stakeholder communication [6].
Architectural Knowledge (AK) is contained in SA documentation. AK can be defined as "the integrated representation of the software architecture of a software-intensive system (or a family of systems), the architectural design decisions, and the external context/environment" [15]. Filebased documents, e.g., text and diagram files, are commonly used in industry practice to organise and retrieve AK [20].
File-based SA documentation is often 'one-size-fits-all' and does not serve the needs of specific users and their tasks well [20]. This mismatch between the expected and actual AK needs of document users reduces the value of SA documentation [17]. SA documentation that is not fitting for its users is not cost-effective [6].
The linear organisation of file-based documentation limits document writers in organising AK and explicitly communicating the relationships between AK that users need to find [9]. Relationships between AK are often tacit, e.g., between requirements and design rationale [22]. Industry practitioners consider incomplete documentation and missing relationships between AK, i.e., lack of 'traceability' between AK, as the main problems with SA documentation [20] and indicate that these problems negatively affect software maintainance [5]. Improving the traceability between AK leads to better architectural understanding [13,21].
Ontology-based documentation makes use of ontologies for non-linear organisation of AK via classes and relationships, and this allows document writers to comprehensively organise AK and relationships between AK for the needs of document users. Recent studies provide evidence that the use of ontology-based AK organisation improves architectural review quality [12] as well as the efficiency and effectiveness of AK recovery [16] and AK retrieval [9], compared to filebased AK organisation.
However, we do not know how different ontologies perform in terms of their relative efficiency and effectiveness.
In a previous study [23], an ontology was built for the AK needs based on expected use cases for finding requirements and design. If we know the actual AK needs, and build an ontology according to these needs, how would this ontology perform? Would an ontology built from actual AK needs result in more efficient and effective AK retrieval than an ontology built from expected AK needs?
As such, we compare an ontology built from expected AK needs with an ontology built from actual AK needs. We investigate if there is any difference between the two ontologies in terms of AK retrieval efficiency and effectiveness. We also investigated the limitations of building an ontology from actual AK needs.
We report on a controlled experiment in which participants answer questions about AK from ontology-based SA documentation in a semantic wiki. The participants were organised in two groups. One group retrieved AK using an ontology built from the AK organisation in an SA document. Another group retrieved AK using an ontology built from the AK needs in an architectural review approach. Both ontologies were intended and used for architectural review [4], however, one was built from the expected AK needs of document users, i.e., built without knowing their exact AK needs and questions, and the other was built from the actual AK needs of document users in the experiment. We compared how the use of the two different ontologies affected the timeefficiency and effectiveness (in precision and recall) of AK retrieval by participants.
We identified which parts of the ontology-based AK organisation supported the experiment questions. By analysing the search actions of experiment participants we verified that the use of supporting AK organisation positively correlates with the efficiency and effectiveness of AK retrieval. We compared the AK organisation of the two ontologies and reflect on the use of several criteria for designing clear and extendible knowledge sharing ontologies, and how the use of these design criteria affected the support for AK needs in the constructed ontologies.
This paper makes the following contributions: • Demonstrate how an improved understanding of AK needs can be used to provide ontology support for more efficient and effective AK retrieval.
• Identify the kind of ontology-based AK organisation that improves AK retrieval efficiency and effectiveness.
• Illustrate how the use of ontology design criteria affects the organisation and retrieval of AK.
In Section 2 we provide background on ontologies and ontology-based SA documentation. Section 3 details on the experiment and its results. In Section 4 we analyse the ontology-based AK organisation to explain the underlying causes for the experiment results. In Section 5 we discuss insights gained from constructing the ontologies and analysing the experiment results. Section 6 describes threats to validity and Section 7 reports our conclusions and future work.

Ontology-based SA Documentation
"An ontology" explicitly specifies the conceptualization of a domain [11], i.e., "an ontology" refers to a formal domain model in which concepts and relationships among concepts are described [16]. Ontologies enable a hierarchical classification of interrelated domain concepts and can be represented using a Resource Description Framework (RDF) Schema or the more expressive Web Ontology Language (OWL). The use of RDF makes ontologies human readable and machine-interpretable, allowing querying of and inference over knowledge.
The classes and relationships in an ontology can be used for organising AK. Each distinct ontology class and relationship has properties and descriptions that explicitly define their meaning, allowing different AK users to interpret them consistently and unambiguously. Relationships in an ontology allow its users to see how AK instances are interrelated, e.g., "requirement X is realized by component Y ", and thereby improves traceability between AK. Moreover, the relationships between AK can be used to provide different views on, and cross-section of the same AK to satisfy the AK needs of diverse SA documentation users. The use of ontologies for SA documentation is described in more detail in [7-9, 12, 16, 17].

ArchiMind Semantic Wiki
A semantic wiki allows for presentation and navigation of classes and relationships in an ontology. Semantic wikis can provide features of traditional wiki-like systems, e.g., centralised access to and editing of documentation, versioning, and collaboration mechanisms.
We used the OntoWiki tool [2] as the basis for the tool in our ontology-based documentation approach. OntoWiki is open source and aims to support collaborative knowledge engineering. It offers web-based visualization and management of (ontology and its instances in) knowledge bases and semantic-enhanced search facilities. We made adaptations to version 0.9.5 of OntoWiki in order to optimize it for storage and retrieval of architecture documentation. We named the adapted version 'ArchiMind' (see http://www. archimind.nl/archimind/ for a demo).
File-based documentation content, e.g., from word processors and UML tools, and its layout is stored in wikipages using a WYSIWYG editor in ArchiMind. 'Wikipage' is an ontology class and its instances are used to store documentation content. ArchiMind allows for semantic annotation of phrases in documentation content that refer to AK instances. For example, in phrase "D11: managers can use analytics GUI " one could annotate "D11 " as (an instance of class) decision, "manager " as stakeholder, and "GUI " as component. The annotated text on the wikipages is highlighted yellow and, when one clicks it, a pop-up menu shows the full description of the AK instance, its relationships to other AK instances, and to other wikipages that also mention the AK instance.
When a fragment of text is annotated on a wikipage, a relationship is created from the wikipages to the AK instance(s) that the annotated text fragment refers to, and vice versa. AK instances become traceable to the various fragments of documentation content (wikipages) that describe it and vice versa. This helps users to locate (sources of) AK descriptions. Please see [7] for more details.

AK RETRIEVAL EXPERIMENT
SA documentation often does not support the AK needs of all document users in its AK organisation [20]. It is hard for document writers to accurately predict all AK needs of document users, and this introduces a mismatch between the AK needs that are supported in an SA document and the actual AK needs of document users. We investigate whether support for the actual AK needs of document users in an ontology affects the efficiency and effectiveness of AK retrieval from ontology-based SA documentation.
We execute an experiment in which participants use two different ontologies to answer questions about AK as part of an architecture review. One ontology is built based on the AK needs that document writers expect document users to have (an 'expected-needs ontology') when conducting the architectural review. The other ontology is built based on the actual AK needs of document users (an 'actual-needs ontology') when they conduct the architectural review. The actual AK needs were identified by analysing questions in the architectural review approach, and modelled in the actualneeds ontology to provide an organisation for retrieving this AK. We test whether there is a significant difference in timeefficiency and effectiveness (in recall and precision) of AK retrieval between the two ontologies.
The primary experimental goals are: • (A) evaluate the AK retrieval efficiency of an ontology built based on expected AK needs and an ontology built based on actual AK needs.
• (B) evaluate the AK retrieval effectiveness of an ontology built based on expected AK needs and an ontology built based on actual AK needs.
The experiment took place during a software architecture course given at the University of Amsterdam. This course is part of a professional software engineering master programme. The experiment was advocated to students during one of the final lectures as a voluntary extracurricular activity, and participation did not affect their course grades. In total 49 students participated in the experiment.

Experiment Materials
We used a file-based SA document for constructing the ontology-based documentation. This file-based SA document is the main deliverable of one team of 5 students in the software architecture course.
The SA document describes the architecture of a social network system for software developers that can answer queries of individual software developers and analyse the development community. Several students acted as stakeholders with specific concerns and requirements for the system. Students in the architect role had to design the system such that it addresses the concerns and requirements.
The SA document is written in English, consists of 39 pages, 16 (mostly UML) diagrams, 528 paragraphs, and 10.874 words. The AK in this document is organised by a table of contents with 26 (sub)sections. The document has a view-based AK organisation, containing a logical & implementation view and deployment view, following the architecture description principles of Bass et al. in [3] (advocated as textbook for the course), as well as [1,14].
The content of the SA document was imported as wikipages in ArchiMind by following the process described in Section 2.2 and in [7]. AK elements and relationships between AK elements described in wikipage content were subsequently annotated using the two ontologies (expected-needs and actual-needs ontology) introduced in the next subsections.

Ontology Design Criteria
We followed design criteria for knowledge sharing ontologies, proposed by Gruber in [11], when constructing the two ontology used in the experiment. These criteria aim for construction of clear and extendible ontologies that are suitable for sharing knowledge in different applications.
Design criterion 1) on 'Clarity' states that ontology constructs should be clear and objective, e.g., supported by natural language descriptions to specify their meaning.
Design criterion 2) on 'Coherence' states that an ontology should be logically consistent, i.e., that its constructs and axioms do not contradict each other.
Design criterion 3) on 'Extendibility' states that ontology extensions should be anticipated to support future tasks, and not require revision of existing ontology constructs.
Design criterion 4) on 'minimal encoding bias' states that the definition of concepts should not depend on a particular encoding, implementation, or notation, because this restricts ontology use to specific programs and tools. Our use of ontology class 'Wikipage', for storing SA document content in ArchiMind, is a form of encoding bias.
Design criterion 5) on 'minimal ontological commitment' states that an ontology should model a domain using the minimal set of constructs and claims necessary for its knowledge sharing activities. This allows more freedom when extending and instantiating the ontology in different and specialized domains.

Expected-needs Ontology
We used the file-based SA document to construct an ontology for organising and indexing its AK in ontology-based documentation. We refer to this ontology as an 'expectedneeds ontology' because it was constructed based on the AK needs that the document writers expected document users to have. The expected-needs ontology is depicted in Figure  1 (without grey elements).
The 5 students who wrote the SA document knew that their architecture would be reviewed by the course staff for grading, and reviewed by other students as part of an assignment. The document writers expected architectural review by document users, and they understood that the AK needed for these review tasks should be recorded in their SA document. Similarly, the two researchers that built the ontology knew that the SA document was written with architectural review (by course staff and students) in mind. The researchers and the document authors however did not know the exact AK needs and actual questions that had to be answered during review.
The expected-needs ontology employed in the experiment was constructed based on the AK organisation of the filebased SA document, using the table of contents, views, tables, diagrams, lists of AK elements, and boldface headers, which make explicit where different types of AK and relationships between AK are recorded. Two researchers collaborated to identify AK concepts and relationships between AK based on the available AK organisation and their understanding of SA concepts.
For example, the table of contents in the SA document has subsections "design rationale", "assumptions", and "scenarios", which makes it explicit where design rationale is recorded. Boldface text and table column headers made design options explicit in the content of these sections. Based on this AK organisation we modelled class 'Design issue', 'Option', 'Assumption', and 'Scenario', as well as relationships 'assumes' and 'supports' in the expected-needs ontology, as depicted in Figure 1. Various UML diagrams made elements of the architectural solution design explicit, e.g., components and layers, which were modelled as subclasses of 'Architecture' in the ontology. In [12] a similar process was used to derive a domain ontology, during which AK elements were annotated in SA document content. We followed the five design criteria, introduced in Section 3.1.1, whilst constructing the expected-needs ontology. Most notably, we modelled class 'Option', 'Assumption', and 'Scenario', instead of a single class 'Decision', when considering design criterion 3. This allows for an extended definition of design rationale and supports future associated tasks, e.g., extensive evaluation of design rationale, without having to revise the ontology.

Actual-needs Ontology
In [18] Nord et al. provide a number of questions, organised in question sets, to review architecture documentation as part of an SEI architectural review approach. 50 of the 127 SEI questions could be fully or partially answered from the SA document used in the experiment.
We used the AK needs expressed in these 50 SEI questions to build the actual-needs ontology. We identified AK types and relationships between AK in the SEI questions, and added these AK types and relationships to the actualneeds ontology if they were not yet present in the expectedneeds ontology. This aims to support the AK needs of document users (experiment participants) when they apply the SEI architectural review approach.
For example, we added relationships 'provides', 'offers', and class 'Pattern' to support document users in answering SEI questions about software development activities. We also added an ontology class 'Concern' to support SEI questions for reviewing the documentation of stakeholders, concerns, and conformance to ISO/IEC 42010 [1].
The actual-needs ontology extends the expected-needs ontology. We chose for ontology extension, instead of building another ontology from scratch, because this allows us to investigate how the addition of specific ontology constructs to support AK needs influences AK retrieval. The added ontology constructs are marked grey in Figure 1.
The above process is in part similar to that in the 'typical question' approach to ontology engineering for software architecture documentation in [8]. In [8], questions that SA document users ask during their daily tasks, i.e., their 'typical questions' that represent their AK needs, are used to construct an ontology that supports the AK needs of document users.
We again used the ontology design criteria by Gruber [11] (see Section 3.1.1). For example, several of the SEI questions that review the support for software development activities required retrieval of implementation units and development dependencies. We however decided not to model implementation units and development dependencies as AK types and relationships in the ontology because this introduces a lot of ontological commitment (design criterion 5).
Several SEI questions for reviewing the documentation of stakeholders aim to locate stakeholder concerns in the SA document content, which is stored in wikipages in Archi-Mind. We however decided to not add more relationships to and from class 'Wikipage' because Wikipage is application specific and introduces encoding bias (design criterion 4).
We added relationship 'addressed by', between class 'Requirement' and 'Design issue', as well as relationship 'results in', between class 'Requirement' and 'Architecture' in the actual-needs ontology. This supports SEI questions for reviewing the identification of requirements and design decisions. The added relationships are more specific than the existing relationships in the expected-needs ontology, and this adheres to design criterion 1) clarity.

Experiment Questions
We selected 5 SEI questions which are representative of the AK needs in the 50 SEI questions that were used to build the actual-needs ontology. These 5 SEI question are used as experiment questions to test and compare AK retrieval efficiency and effectiveness between the two ontologies. We used several criteria to select the 5 experiment questions from the 50 SEI questions.
Firstly, the experiment questions must be answerable from the SA documentation used in the experiment. Secondly, the experiment questions must have answers that can be quantitatively assessed, i.e., such that evaluators do not have to subjectively judge whether the answer to an open-ended question is either correct or incorrect. Thirdly, selected experiment questions should be representative of multiple SEI questions, to cover a large part of the SEI architectural review approach. We finally selected the following questions: 1: List ten development dependencies between implementation units.

2:
Which implementation units and decisions are explicitly related to requirement 'Security' ?
3: Which architectural patterns are described in the architecture?
4: Which functional requirements are related to non-functional requirement 'Compatibility' ?
5: Find ten wikipages in which the concerns of the stakeholders are addressed (not just listed).
The experiment questions cover several aspects of the SEI architectural review approach. Question 1 reviews the support for software development in an SA document. Question 2 reviews the support for comprehensive architectural evaluation, software development, and identification of requirements and decisions in an SA document. Question 3 reviews the support for software development, and question 4 reviews the support for identification of requirements and design decisions. Question 5 reviews conformance to ISO/IEC 42010, support for comprehensive architectural evaluation, and reviews whether important stakeholders and concerns are captured.
We estimated that it was not acceptable for all participants to spend more than 45 minutes on the experiment. Therefore we limited the number of answers for experiment questions 1 and 5 to ten, and instantiated the requirements that have to be retrieved in questions 2 and 4. The original SEI questions require complete AK retrieval and thus more time. Question 3 is a shorter version of an SEI question.

Experiment Hypothesis
We formulate the following alternative hypotheses for experimental goals A and B specified in Section 3; H 1A = The use of the actual-needs ontology for answering experiment questions results in higher time-efficiency than the use of the expected-needs ontology.
H 1B = The use of the actual-needs ontology for answering experiment questions results in higher effectiveness than the use of the expected-needs ontology.
The null hypotheses state that there is no difference in efficiency and effectiveness between the use of the two ontologies.
In the experiment we used one independent variable (or 'predictor variable') with two levels, namely the expectedneeds and the actual-needs ontology. Two dependent variables (or 'response variables') are used in the experiment. Time is used as a measure of efficiency. The harmonic mean of precision and recall, the F 1 score, introduced by van Rijsbergen in [24], is used for measuring effectiveness: Where Recall is the proportion of relevant items retrieved from the total set of relevant items in a system and precision is the proportion of retrieved items that is relevant in a result set. Recall represents the completeness of AK retrieval (i.e, answers by participants to experiment questions) and precision represents the correctness of AK retrieval. The students that wrote the SA document also participated in the experiment. Their answers to the experiment questions were only used to verify the relevancy of items, or 'ground truth', when calculating precision and recall.

Experiment Procedure
A ten-minute introduction to ontology-based SA documentation was given to participants during the final lecture of the software architecture course. A researcher explained the functions and GUI of ArchiMind using a graphical overview in presentation slides. The participants also received a printed form with a graphical overview of ArchiMind's GUI and an explanation of its functionality.
The participants received another printed form which depicted the ontology they had to use. This form also instructed participants: "Please try to simulate your behavior in normal work and studies: balance between time-efficiency and correct answers.". This instruction was given to encourage participants to perform the experiment seriously and answer the questions as time-effectively as possible.
We handed out two versions of the printed experiment instructions in random order. In one version of the instructions we asked participants to navigate to a URL which hosted ArchiMind with the expected-needs ontology. The other version led participants to a URL which hosted Archi-Mind with the actual-needs ontology. These URLs also hosted a web-based form which listed the questions, input boxes for answers, and the expected format of answers. The experiment took place in two classrooms with PCs containing the same hardware and operating system image.
Before the start of the experiment we asked each participant: "How many years of working experience in IT industry do you have? ". Participants reported an average of 3.92 years experience in IT industry. 27 participants used the expected-needs ontology and reported 4.78 years experience on average, and 22 participants used the actual-needs ontology and reported 2.87 years of experience on average. Two participants using the expected-needs ontology were outliers with 16 and 30 years of experience, which explains the large difference in average years of experience between the two groups.

Experiment Test Results
Using the Shapiro-Wilk and Kolmogorov-Smirnov tests, we found that the experiment measurements were not normally distributed. Therefore we applied the non-parametric Mann-Whitney-Wilcoxon (MWW) test to the experiment measurements. Table 1 reports the average efficiency and effectiveness measurements, the p-values for one-tailed MWW tests (corrected for ties), and effect size per question. 12 participants encountered errors in ArchiMind whilst answering questions (the database server could not handle 49 concurrent users). We excluded measurements for these questions. In some cases we could include the F1 scores of answers in our measurements because participants lost time due to an error, but could still continue to give an answer. This results in an unpaired number of measurements (see second-to-last column of Table 1) between the control and test group, however, the MWW test allows testing of unpaired measurements.
Column 'p-value test results' in Table 1 contains the pvalues for one-tailed MWW test results on efficiency for each row with 'Seconds' in column 'Metric'. Table 1 shows that the difference in AK retrieval efficiency between the expected-needs and actual-needs ontology is statistically insignificant at the p=0.05 level for all experiment questions, except for question 3. Consequently, we only reject the null hypothesis H 0A and accept the alternative hypothesis H 1A for question 3. Most participants that used the expectedneeds ontology quickly gave up searching without finding answers to question 4. This explains the insignificant difference in efficiency between the ontologies for question 4. Table 1 shows that the difference in AK retrieval effectiveness (rows with "F1score") between the expected-needs and actual-needs ontology is statistically significant at the p=0.05 level for experiment questions 3 and 4. Consequently, we reject the null hypothesis H 0B and accept the alternative hypothesis H 1B for questions 3 and 4.

AK ORGANISATION AND AK RETRIEVAL
In this section we analyse the experiment results. The actualneeds ontology provided significantly higher AK retrieval efficiency and effectiveness than the expected-needs ontology for experiment questions 3 and 4. The only intended (or 'designed') difference in the experiment materials was between the AK organisations provided by the two ontologies.
We explain the differences in AK retrieval efficiency and effectiveness by comparing the difference in AK organisation that the two ontologies provided.
In Section 4.1 we analyse which ontology-based AK organisation supported participants in finding the AK and relationships between AK for each experiment question. We analyse the usage of supporting AK organisation from the search actions of participants in Section 4.2 and verify that this usage leads to efficient and effective AK retrieval. Section 4.3 describes how the AK retrieval efficiency and effectiveness of participants was affected by the supporting AK organisation for each experiment question and by different ontology constructs.

Fitting AK Organisation
The ontology-based documentation tested in the experiment is organised by ontology classes and relationships between classes. Figure 2 depicts the ontology-based AK organisation that provided one or more paths to the answers for each experiment question, i.e., the ontology classes with AK instances and the relationships between classes that can be used to navigate to AK instances and answers.
Some of the nodes on a path to the answer explicitly relate to the AK needs in the question asked. For example, experiment question 4 "Which functional requirements are related to non-functional requirement 'Compatibility' ? ", specifies that instances of AK types 'functional requirement' and 'non-functional requirement' have to be found. Both the actual-needs and expected-needs AK organisation in Figure 2 contain classes 'Functional Requirement' and 'Nonfunctional Requirement' which relate to the two AK types in question 4, and these classes can be used to find a path to answers for question 4. Experiment question 4 also specifies a relationship 'related to' between requirements, which is not supported in the expected-needs AK organisation. Participants can still identify the relationships between requirements in the content of wikipages, from properties of class Requirement, or by deriving the relationships via transitive or symmetric properties of other ontology relationships to and from requirements, e.g., 'depends on', 'is concern of ', and 'realized by'. The AK organisation provided by the actual-needs ontology additionally contains relationship 'related to', which explicitly matches 'related to' in experiment question 4 and provides a direct path to its answers.

Question 2: Which implementation units and decisions are explicitly related to requirement 'Security'?
Question 3: Which architectural patterns are described in the architecture? We term the elements in the ontology-based AK organisation that explicitly refer to the AK needs in the question asked, and provide a direct path to its answer(s), as "fitting AK organisation". We adopt the specific term "fitting AK organisation" and its definition because there may be other forms of support that an ontology-based AK organisation provides for AK needs in questions. Ontology classes and relationships that provided fitting AK organisation for AK needs in an experiment question are surrounded by boxes filled with green diagonal lines in Figure 2

Usage of Fitting AK Organisation
There are various (confounding) factors that may have influenced the efficiency and effectiveness of AK retrieval in the experiment. For example, participants could find answers by keyword searching and reading plain text stored in wikipages, without making use of the fitting AK organisation provided by the ontologies. In this section we verify that the usage of fitting AK organisation influences the efficiency and effectiveness of AK retrieval.
We quantified the usage of AK organisation from over 3,000 AK retrieval actions of participants that were automatically logged during the experiment. Each logged search action is time-stamped and contains the name of the search action (e.g., 'keyword search' and 'class navigation'), the AK organisation that was used (e.g. class 'Requirement'), and the names of visited AK instances or keyword search terms.
We measured the use of fitting AK organisation if 1) the fitting AK organisation appeared on the screen of a participant for 3 seconds or more, and 2) the participant navigated to answers by following the fitting AK organisation or gave answers based on the fitting AK organisation shown on screen. We evaluated these criteria by looking at the properties of the logged search actions, their time-stamp, and by re-enacting the logged search actions in ArchiMind. We measured usage of the fitting AK organisation based on the ontology classes and relationships, that provided fitting AK organisation for AK needs, depicted in Figure 2. This includes the use of fitting AK organisation in wikipage content, which was annotated based on the ontologies (see Section 2.2).
RatioTimeFitting is introduced as a metric to represent how much fitting AK organisation was used to answer an experiment question. RatioTimeFitting is calculated per participant per experiment question by dividing the 'time spent using fitting AK organisation' by the 'total time spent searching for AK '. Time-effectiveness is introduced in order to represent the efficiency and effectiveness of AK retrieval in a single metric. Time-effectiveness is calculated per answer in the experiment by dividing the F1 score (effectiveness) by the 'total time spent searching for AK ' (efficiency). A Time-effectiveness of 0.02 (e.g., for F1 score 1.0 divided by 50 seconds spent searching for AK) means that a participant was able to retrieve 2% of the complete and correct answer to an experiment question each second.
To verify that the use of fitting AK organisation influences the efficiency and effectiveness of AK retrieval, we test if a correlation exists between RatioTimeFitting and Timeeffectiveness. We use the following hypothesis: H 1C = There is a correlation between RatioTimeFitting and Time-effectiveness. The null hypothesis states that there is no correlation.
Using the Kolmogorov-Smirnov test, we found that the measurements for RatioTimeFitting and Time-effectiveness are not normally distributed. Therefore the non-parametric Spearman's rank correlation test is applied.
Application of Spearman's rank test indicates a moderate positive correlation (coefficient r = 0.509) between Ratio-TimeFitting and Time-effectiveness. These test results are statistically significant at the p=0.01 level with a (2-sided) P-value of 1.005 −11 . Consequently, we reject the null hypothesis H 0C and accept the alternative hypothesis H 1C . This shows that the use of fitting AK organisation was positively correlated with the time-effectiveness of AK retrieval.

Fitting AK Organisation per Question
The experiment results in Table 1 show that there was no significant difference in AK retrieval efficiency and effectiveness between the two ontologies for questions 1 and 2. The insignificant difference for question 1 can be explained by the lack of fitting AK organisation in both ontologies, as shown in Figure 2. The actual-needs ontology contained four additional relationships that provided paths to answers for questions 1. The names of the four relationships did however not make it explicit to users where they could find development dependencies, and were thus not fitting for question 1.
The actual-needs ontology contained two additional relationships that provided fitting AK organisation for the AK needs in question 2. However, these two additional relationships in the actual-needs ontology were redundant because existing relationships 'depends on', 'realized by', and 'satisfies' in both ontologies provided the same paths to answers and were fitting for the same AK needs in question 2. The actual-needs ontology thus provided redundant fitting AK organisation for AK needs in question 2, and its use did not result in significantly higher AK retrieval efficiency and effectiveness compared to use of the expected-needs ontology.
The actual-needs ontology provided additional fitting organisation by means of ontology class 'Pattern' for AK needs in question 3 and relationship 'Related to' (between requirements) for AK needs in question 4, as depicted in Figure 2. These AK needs were not yet supported by fitting AK organisation in the expected-needs ontology. Consequently, the AK retrieval efficiency and effectiveness of the actual-needs ontology was significantly higher than that of the expectedneeds ontology for question 3, and AK retrieval effectiveness was significantly improved for question 4. This evidence also shows that a single class or relationship can be added to an ontology to provide fitting organisation for AK needs and thereby improve the time-effectiveness of AK retrieval.
The actual-needs ontology contains an additional class 'Concern', which provided fitting AK organisation for AK needs in question 5. However, the expected-needs ontology already provided fitting AK organisation to support participants in finding the concerns for question 5, namely, via relationships 'is concern of ' and 'concerned about'. Consequently, the AK retrieval efficiency and effectiveness of the actual-needs ontology was not significantly higher than that of the expected-needs ontology. Adding fitting AK organisation that is redundant to existing fitting AK organisation thus did not help to improve AK retrieval efficiency and effectiveness.

DISCUSSION
We built the expected-needs ontology based on the AK organisation of the SA document that was used in the experiment. The SA document contained all the AK needed by participants in the experiment because we only asked questions that could be answered from the SA document content. Moreover, the document authors anticipated the AK needs for architectural review, and architectural review questions were asked in the experiment. As such the SA document contained all AK needed in the experiment, which could have been modelled in the expected-needs ontology to provide fitting AK organisation.
However, certain types of AK and relationships between AK were not very explicit in the SA document, and difficult to identify without knowing if this AK was needed by document users. The AK in the SA document was organised to support the anticipated AK needs of its users, yet it did not clearly specify these AK needs. Building the expected-needs ontology thus required reverse engineering of the AK needs for which the SA document was written.
We noticed that the relationships between AK were especially hard to identify because they were not always explicitly described in the SA document. For example, the table of contents and boldface headers made it very explicit where decisions were recorded, yet their relationships with the requirements were less explicitly listed in the text inside the sections. This issue might be addressed by assuming that certain relationships between AK exist, instead of identifying and modeling the relationships between AK that are very explicit in the SA document.
We constructed the actual-needs ontology using the coding and ontology construction step in the 'typical question' approach described in [8]. It is suggested in [8] that the questions of users help AK ontology construction because they clearly identify the required types of AK and relationships between AK. This suggestion is supported by our study since we were able to identify AK types and relationships between AK from the SEI questions to construct the actual-needs ontology.
The actual-needs ontology however did not provide fitting AK organisation for all AK needs in the experiment, even though AK needs were identified from SEI questions. This lack of fitting AK organisation curtailed the efficiency and effectiveness of AK retrieval. The correlation found in Section 4.2 suggests that participants would have retrieved AK more efficiently and effectively if additional fitting AK organisation was provided to support their AK needs.
We found that the use of the ontology design criteria (see Section 3.1.1) restricted the modelling of the identified AK needs. The design criteria helped to construct a clear and extendible ontology for knowledge sharing across different applications. For example, based on these criteria we decided to comprehensively model design rationale to support future AK retrieval tasks (see Section 3.1.2). We also decided not to model certain constructs in the actual-needs ontology because they affected ontological commitment and encoding bias (see Section 3.1.3). This allows for more freedom to use the ontology in different domains and applications.
However, these decisions, made based on the ontology design criteria, restricted modelling of fitting AK organisation to support AK needs, and this in turn negatively affected the AK retrieval efficiency and effectiveness of participants. Use of the ontology design criteria was thus traded off against lower efficiency and effectiveness of AK retrieval.
Above findings can be used in practice to create ontologybased SA documentation from which AK can be retrieved efficiently and effectively. In [10] Falessi et al. investigated whether an accurate understanding of the value of AK for the activities of document users can be used to only document valuable AK, and thereby reduce the costs of producing documentation. Conversely, we investigated whether an accurate understanding of the AK needs of document users can be used to improve AK retrieval from documentation, and thereby reduce time-costs and increase the effectiveness of AK retrieval when consuming documentation.

Internal Validity
The file-based SA documentation which was used as input for the experiment was written by 5 students, of which 4 participated in the experiment. We excluded the answers of these document authors from statistical testing because their prior knowledge about the SA documentation would bias the experiment results. Instead we used their answers as a 'gold standard' (i.e. 'ground truth') to verify that our evaluation of precision and recall was correct.
A group of 5 students who acted as stakeholders in the SA course answered several SEI questions from the file-based SA document as part of an assignment prior to the experiment. The AK needs in these questions partially overlaps with the AK needs in experiment questions, which means that these 5 students may have had prior knowledge about the answers to questions in the experiment. This threat to validity was mitigated by equal distribution of the 4 stakeholder-students that participated in the experiment across the test and control group: two students used the expected-needs ontology and two used the actual-needs ontology.
Two students registered as 'anonymous' for the experiment, and may have been part of the 5 stakeholders or 5 document authors discussed above. They however retrieved AK with average efficiency and effectiveness, which leads us to believe they do not have prior knowledge and are not part of the document authors or stakeholders discussed above.

External Validity
The specific set of questions from the SEI architectural review approach that were used in the experiment limits generalization of the experiment results and findings. The SA documentation used in the experiment was written by students that used guidelines in [1,3,14] for view-based architecture description. The experiment documentation can be generalized to documentation practice in industry to the extent that industry practitioners also make use of UML and view-based architecture descriptions.
The ArchiMind semantic wiki tool is not specific to the ontologies and SA documentation in the experiment, and can be used for any type of ontology and documentation. The findings in this work can to a certain extent be generalized to ontology-based documentation approaches that make use of a semantic wiki tool.

CONCLUSIONS
It is important that AK is quickly and correctly retrieved from SA documentation, however, SA documentation often does not support its users in retrieving all the AK that they need for their tasks. In this paper we investigated whether document users retrieve AK more efficiently and effectively when they use an ontology-based document organisation that is constructed from an improved understanding of their AK needs. We conducted an experiment to compare AK retrieval using an ontology built from the expected AK needs of document users and an ontology built from their actual AK needs.
The use of the actual-needs ontology was significantly more efficient and effective for answering one experiment question, and significantly more effective for answering another experiment question, compared to the use of the expected-needs ontology. Part of the ontology-based AK organisation was fitting for AK retrieval; it explicitly denoted the AK types and relationships between AK that participants needed to retrieve. We found that the use of AK organisation that was fitting for AK needs in a question had a significant correlation with the efficiency and effectiveness of answering that question. The actual-needs ontology provided more fitting AK organisation for the AK needs in two questions, and its users answered one of the two questions more efficiently and effectively and the other question more effectively than users of the expected-needs ontology.
The experiment results show that better support for the AK needs of ontology-based documentation users improves the efficiency and effectiveness when the users retrieve the AK that they need. The results highlight the importance of accurately understanding the AK needs of SA documentation users; it allows document writers to organise AK such that document users can efficiently and effectively retrieve the AK that they need. Not all AK needs were supported by fitting AK organisation, and this curtailed the efficiency and effectiveness of AK retrieval. This was caused by the use of criteria for designing clear and extendible knowledge sharing ontologies, which limited the amount of fitting AK organisation that was added to support AK needs. The use of the ontology design criteria was traded off against the efficiency and effectiveness of AK retrieval.
We plan to further investigate how fitting AK organisation can be provided for more AK needs of document users, whilst using design criteria for knowledge sharing ontologies.


extfieldsofstudy:
Computer Science
Mathematics

s2fieldsofstudy:
Computer Science
Mathematics

text:
Embed to Control: A Locally Linear Latent Dynamics Model for Control from Raw Images

We introduce Embed to Control (E2C), a method for model learning and control of non-linear dynamical systems from raw pixel images. E2C consists of a deep generative model, belonging to the family of variational autoencoders, that learns to generate image trajectories from a latent space in which the dynamics is constrained to be locally linear. Our model is derived directly from an optimal control formulation in latent space, supports long-term prediction of image sequences and exhibits strong performance on a variety of complex control problems.

Introduction
Control of non-linear dynamical systems with continuous state and action spaces is one of the key problems in robotics and, in a broader context, in reinforcement learning for autonomous agents. A prominent class of algorithms that aim to solve this problem are model-based locally optimal (stochastic) control algorithms such as iLQG [1,2], which approximate the general non-linear control problem via local linearization. When combined with receding horizon control [3], and machine learning methods for learning approximate system models, such algorithms are a powerful tool for solving complicated control problems [3,4,5,6]; however, they either rely on a known system model or require the design of relatively low-dimensional state representations. For real autonomous agents to succeed, we ultimately need algorithms that are capable of controlling complex dynamical systems from raw sensory input (e.g. images) only. In this paper we tackle this difficult problem.
If stochastic optimal control (SOC) methods were applied directly to control from raw image data they would face two major obstacles. First, sensory data is usually high-dimensional -i.e. images with thousands of pixels -rendering a naive SOC solution computationally infeasible. Second, the image content is typically a highly non-linear function of the system dynamics underlying the observations; thus model identification and control of this dynamics is non-trivial.
While both problems could, in principle, be addressed by designing more advanced SOC algorithms we approach the "optimal control from raw images" problem radically different: turning the problem of locally optimal control in high-dimensional, non-linear systems, into one of identifying a lowdimensional latent state space in which locally optimal control can be performed robustly and easily. To learn such a latent space we propose a new deep generative model belonging to the class of variational autoencoders [7,8] that is derived directly from an iLQG formulation in latent space. The resulting Embed to Control (E2C) system is a probabilistic generative model that holds a belief over viable trajectories in sensory space; allows for accurate long-term planning in latent space; and is trained fully unsupervised.
We demonstrate the success of our approach on four challenging tasks for control from raw images and compare it to a range of methods for unsupervised representation learning. As an aside, we also validate that deep up-or de-convolutional networks [9,10,11] can be used as powerful generative models for large images.

The Embed to Control (E2C) model
We briefly review the problem of SOC for dynamical systems, introduce approximate locally optimal control in latent space, and finish with the derivation of our model.

Problem Formulation
We consider the control of unknown dynamical systems of the form where t denotes the time steps, s t ∈ R ns the system state, u t ∈ R nu the applied control and ξ the system noise. The function f (s t , u t ) is an arbitrary, smooth, system dynamics. We equivalently refer to Equation (1) using the notation P (s t+1 |s t , u t ), which we assume to be a multivariate normal distribution N (f (s t , u t ), Σ ξ ). We further assume that we are only given access to visual depictions x t ∈ R nx of state s t . This restriction requires solving a joint state identification and control problem.
For simplicity we will in the following assume that x t is a fully observed depiction of s t , but relax this assumption later.
Our goal then is to infer a low-dimensional latent state space model in which optimal control can be performed. That is, we seek to learn a function m, mapping from high-dimensional images x t to low-dimensional vectors z t ∈ R nz with n z n x , such that the control problem can be solved in z t instead of x t : where ω accounts for system noise; or equivalently z t ∼ N (Z t |m(x t ), Σ ω ). Assuming for the moment that such a function can be learned (or approximated), we will first define SOC in a latent space and introduce our model thereafter.

Stochastic locally optimal control in latent spaces
Let z t ∈ R nz be the inferred latent state from image x t of state s t and f lat (z t , u t ) the transition dynamics in latent space, i.e., z t+1 = f lat (z t , u t ). Thus f lat models the changes that occur in z t when control u t is applied to the underlying system as a latent space analogue to f (s t , u t ).
Assuming f lat is known, optimal controls for a trajectory of length T in the dynamical system can be derived by minimizing the function J(z 1:T , u 1:T ) which gives the expected future costs when following (z 1:T , u 1:T ): where c(z t , u t ) are instantaneous costs, c T (z T , u T ) denotes terminal costs and z 1:T = {z 1 , . . . , z T } and u 1:T = {u 1 , . . . , u T } are state and action sequences respectively. If z t contains sufficient information about s t , i.e., s t can be inferred from z t alone, and f lat is differentiable, the cost-minimizing controls can be computed from J(z 1:T , u 1:T ) via SOC algorithms [12]. These optimal control algorithms approximate the global non-linear dynamics with locally linear dynamics at each time step t. Locally optimal actions can then be found in closed form. Formally, given a reference trajectorȳ z 1:T -the current estimate for the optimal trajectory -together with corresponding controlsū 1:T the system is linearized as where A(z t ) = δf lat (zt,ūt) δzt , B(z t ) = δf lat (zt,ūt) δūt are local Jacobians, and o(z t ) is an offset. To enable efficient computation of the local controls we assume the costs to be a quadratic function of the latent representation Figure 1: The information flow in the E2C model. From left to right, we encode and decode an image x t with the networks h enc φ and h dec θ , where we use the latent code z t for the transition step. The h trans ψ network computes the local matrices A t , B t , o t with which we can predictẑ t+1 from z t and u t . Similarity to the encoding z t+1 is enforced by a KL divergence on their distributions and reconstruction is again performed by h dec θ .
where R z ∈ R nz×nz and R u ∈ R nu×nu are cost weighting matrices and z goal is the inferred representation of the goal state. We also assume c T (z t , u t ) = c(z t , u t ) throughout this paper.
In combination with Equation (4) this gives us a local linear quadratic Gaussian formulation at each time step t which can be solved by SOC algorithms such as iterative linear quadratic regulation (iLQR) [13] or approximate inference control (AICO) [14]. The result of this trajectory optimization step then is a locally optimal trajectory with corresponding control sequence (z * 1:T , u * 1:T ) ≈ arg minz1:T u 1:T J(z 1:T , u 1:T ).

A locally linear latent state space model for dynamical systems
Starting from the SOC formulation, we now turn to the problem of learning an appropriate lowdimensional latent representation z t ∼ P (Z t |m(x t ), Σ ω ) of x t . The representation z t has to fulfill three properties: (1) it must capture sufficient information about x t (enough to enable reconstruction); (2) it must allow for accurate prediction of the next latent state z t+1 and thus, implicitly, of the next observation x t+1 ; (3) the prediction f lat of the next latent state must be locally linearizable for all valid control magnitudes u t . Given some representation z t , properties (2) and (3) in particular require us to capture possibly highly non-linear changes of the latent representation due to transformations of the observed scene induced by control commands. Crucially, these are particularly hard to model and subsequently linearize. We circumvent this problem by taking a more direct approach: instead of learning a latent space z and transition model f lat which are then linearized and combined with SOC algorithms, we directly impose desired transformation properties on the representation z t during learning. We will select these properties such that prediction in the latent space as well as locally linear inference of the next observation according to Equation (4) are easy.
The transformation properties that we desire from a latent representation can be formalized directly from the iLQG formulation given in Section 2.2 . Formally, following Equation (2), let the latent representation be Gaussian P (Z|X) = N (Z|m(x t ), Σ ω ). To infer z t from x t we first require a method for sampling latent states. Ideally, we would generate samples directly from the unknown true posterior P (Z|X), which we, however, have no access to. Following the variational Bayes approach (see Jordan et al. [15] for an overview) we resort to sampling z t from an approximate posterior distribution Q φ (Z|X) with parameters φ.
Inference model for Q φ . In our work this is always a diagonal Gaussian distribution Q φ (Z|X) = N (Z|µ t , diag(σ 2 t )), whose mean µ t ∈ R nz and covariance Σ t = diag(σ 2 t ) ∈ R nz×nz are computed by an encoding neural network with outputs where h enc φ ∈ R ni is the activation of the last hidden layer and where φ is given by the set of all learnable parameters of the encoding network, including the weight matrices W µ , W σ and biases b µ , b σ . Parameterizing the mean and variance of a Gaussian distribution based on a neural network gives us a natural and very expressive model for our latent space. It additionally comes with the benefit that we can use the reparameterization trick [7,8] to backpropagate gradients of a loss function based on samples through the latent distribution.
Generative model for P θ . Using the approximate posterior distribution Q φ we generate observed samples (images)x t andx t+1 from latent samples z t and z t+1 by enforcing a locally linear relationship in latent space according to Equation (4), yielding the following generative model: whereQ ψ is the next latent state posterior distribution which exactly follows the linear form required for stochastic optimal control, ω t ∼ N (0, H t ) is an estimate of the system noise and C can be decomposed as C t = A t Σ t A T t + H t . Note that while the transition dynamics in our generative model operates on the inferred latent space, it takes untransformed controls into account. That is, we aim to learn a latent space such that the transition dynamics in z linearizes the non-linear observed dynamics in x and is locally linear in the applied controls u. Reconstruction of an image from z t is performed by passing the sample through multiple hidden layers of a decoding neural network which computes the mean p t of the generative Bernoulli distribution 1 where h dec θ (z t ) ∈ R n d is the response of the last hidden layer in the decoding network. The set of parameters for the decoding network, including weight matrix W p and b p , then make up the learned generative parameters θ.
Transition model forQ ψ . What remains is to specify how the linearization matrices A t ∈ R nz×nz , B t ∈ R nz×nu and offset o t ∈ R nz are predicted. Following the same approach as for distribution means and covariance matrices, we predict all local transformation parameters from samples z t based on the hidden representation h trans ψ (z t ) ∈ R nt of a third neural network with parameters ψto which we refer as the transformation network. Specifically, we parametrize the transformation matrices and offset as vec where vec denotes vectorization and therefore vec[A t ] ∈ R (n 2 z ) and vec[B t ] ∈ R (nz·nu) . To circumvent estimating the full matrix A t of size n z × n z , we can choose it to be a pertubation of the identity matrix A t = (I − vr T ) −1 which reduces the parameters to be estimated for A t to 2n z .
A sketch of the complete architecture is shown in Figure 1 . It also visualizes the additional constraint that is essential for learning a representation for long-term predictions: we require sampleŝ z t+1 from the state transition distributionQ ψ to be similar to the encoding of x t+1 through Q φ . While it might seem that just learning a perfect reconstruction of x t+1 fromẑ t+1 is enough, we require multi-step predictions for planning in Z which must correspond to valid trajectories in the observed space X. Without enforcing similarity between samples fromQ ψ and Q φ following a transition in latent space from z t using control u t may lead to a pointẑ t+1 from which reconstruction of x t+1 is possible but that is not a valid encoding (i.e. the model has never seen an image corresponding toẑ t+1 ). Executing another action inẑ t+1 then does not result in a valid latent state -since the transition model is conditional on samples coming from the inference network -and thus long-term predictions fail. In a nutshell such a divergence between encodings and the transition model results in a generative model that does not accurately model the Markov chain formed by the observations.

Learning via stochastic gradient variational Bayes
For training the model we use a data set D = {(x 1 , u 1 , x 2 ), . . . , (x T −1 , u T −1 , x T )} containing observation tuples with corresponding controls obtained from interactions with the dynamical system. Using this data set, we learn the parameters of the inference, transition and generative model by minimizing a variational bound on the true data negative log-likelihood − log P (x t , u t , x t+1 ) plus an additional constraint on the latent representation. The complete loss function is given as 1 A Bernoulli distribution for P θ is a common choice when modeling black-and-white images.
The first part of this loss is the per-example variational bound on the log-likelihood (12) where Q φ , P θ andQ ψ are the parametric inference, generative and transition distributions from Section 2.3 and P (Z t ) is a prior on the approximate posterior Q φ ; which we always chose to be an isotropic Gaussian distribution with mean zero and unit variance. The second KL divergence in Equation (11) is an additional contraction term with weight λ, that enforces agreement between the transition and inference models. This term is essential for establishing a Markov chain in latent space that corresponds to the real system dynamics (see Section 2.3 above for an in depth discussion). This KL divergence can also be seen as a prior on the latent transition model. Note that all KL terms can be computed analytically for our model 2 .
During training we approximate the expectation in L(D) via sampling. Specifically, we take one sample z t for each input x t and transform that sample using Equation (10) to give a valid sampleẑ t+1 fromQ ψ . We then jointly learn all parameters of our model by minimizing L(D) using stochastic gradient descent. We highlight that training proceeds without any layer-wise pre-training, alternating optimization or other tricks.

Experimental Results
We evaluate our model on four visual tasks: an agent in a plane with obstacles, a visual version of the classic inverted pendulum swing-up task, balancing a cart-pole system, and control of a 3-link arm with larger images. These are described in detail below.

Experimental Setup
Model training. We consider two different network types for our model: Standard fully connected neural networks with up to three layers which work well for moderately sized images and are used for the planar and swing-up experiments; A deep convolutional network for the encoder in combination with an "up-convolutional" (or deconvolutional) network as the decoder which, in accordance to recent findings from the literature [9,10,11], we found to be an adequate model for larger images. Training was performed using Adam [16] throughout all experiments. The training data set D for all tasks was generated by randomly sampling N state observations and actions with corresponding successor states. For the plane we used N = 3, 000 samples, for the inverted pendulum and cart-pole system we used N = 15, 000 and for the 3-link arm N = 30, 000. A complete list of architecture parameters and hyperparameter choices as well as an in-depth explanation of the up-convolutional network are specified in the supplementary material. To facilitate reproduction of the results presented we will open source our implementation in Theano [17] together with the considered benchmarks.
Model variants. In addition to the Embed to Control (E2C) dynamics model derived above we also consider two variants: By removing the latent dynamics network h trans ψ i.e. setting its output to one in Equation (10) -we obtain a variant in which A t , B t and o t are estimated as globally linear matrices (Global E2C). If we instead replace the transition model with a network estimating the dynamics as a non-linear functionf lat and only linearize during planning, estimating A t , B t , o t as Jacobians tô f lat as described in Section 2.2, we obtain a variant with nonlinear latent dynamics.
Baseline models. For a thorough comparison, and to exhibit the complicated nature of the tasks, we also test a set of baseline models on the plane and the inverted pendulum task: a standard variational autoencoder (VAE) and a deep autoencoder (AE) are trained on the autoencoding subtask for visual problems. That is, given a data set D used for training our model, we remove all actions from the tuples in D and disregard temporal context between images. After autoencoder training we learn a dynamics model in latent space, approximating f lat from Section 2.2. We also consider a VAE variant with a slowness term on the latent representation. Due to space constraints we refer the reader to the supplementary material for a detailed derivation of this model. The architectures used for the baseline methods are the same as for our E2C model in all experiments.  Optimal control algorithms. To perform optimal control in the latent space of different models, we employ two trajectory optimization algorithms: iterative linear quadratic regulation (iLQR) [13] (for the plane and inverted pendulum) and approximate inference control (AICO) [14] (all other experiments). For all VAEs both methods operate on the mean of distributions Q φ andQ ψ . AICO additionally makes use of the local Gaussian covariances Σ t and C. Except for the experiments on the planar system, control was performed in a model predictive control fashion using the receding horizon scheme introduced in [3]. To obtain closed loop control given an image x t , it is first passed through the encoder to obtain the latent state z t . A locally optimal trajectory is subsequently found by optimizing (z * t:t+T , u * t:t+T ) ≈ arg minzt:t+T u t:t+T J(z t:t+T , u t:t+T ) with fixed, small horizon T (with T = 10 unless noted otherwise). Controls u * t are applied to the system and a transition to z t+1 is observed (by encoding the next state image x t+1 ). Then a new control sequence -with horizon T -starting in z t+1 is found using the last estimated trajectory as a bootstrap. Note that planning is performed entirely in the latent state without access to any observations except for the depiction of the current state. To compute the cost function c(z t , u t ) required for trajectory optimization in z we assume knowledge of the observation x goal of the goal state s goal . This observation is then transformed into latent space and costs are computed according to Equation (5).

Control in a planar system
The agent in the planar system can move in a bounded two-dimensional plane by choosing a continuous offset in x-and y-direction. Obstructed by six circular obstacles, the task is to move to the bottom right of the image, starting from a random x position at the top of the image. The highdimensional representation of a state is a 40 × 40 black-and-white image. The agent cannot move beyond boundaries. The cost matrices were set to be diagonal with diag(R z ) = 0.1, diag(R u ) = 1. The encodings of obstacles are obtained prior to planning and an additional quadratic cost term penalizing closeness to obstacles was added to the cost based on them.
A depiction of the observations on which control is performed -together with their corresponding state values and embeddings into latent space -is shown in Figure 2. The figure also clearly shows a fundamental advantage the E2C model has over its competitors: While the separately trained autoencoders make for aesthetically pleasing pictures, the models failed to discover the underlying structure of the state space, complicating dynamics estimation and largely invalidating costs based on distances in said space. Including the latent dynamics constraints in these end-to-end models on the other hand, yields latent spaces approaching the optimal planar embedding.
We test the long-term accuracy by accumulating latent and real trajectory costs to quantify whether the imagined trajectory reflects reality. The results for all models when starting from random positions and executing 50 pre-computed actions are summarized in Table 1 -using a seperate test set for evaluating reconstructions. While all methods achieve a low mean reconstruction log loss per image, the difference in accumulated costs per trajectory clearly show the superiority of the E2C model. Using the globally or locally linear E2C model, trajectories planned in latent space are as Table 1: Comparison between different approaches to model learning from raw pixels for the planar and inverted pendulum system. We compare all models with respect to their prediction quality on a test set of sampled transitions and with respect to their performance when combined with SOC (trajectory cost for control from different start states). Note that trajectory costs in latent space are not necessarily comparable. The "real" trajectory cost was computed on the dynamics of the simulator while executing planned actions. For the true models for s t , real trajectory costs were 20.24 ± 4.15 for the planar system, and 9.8 ± 2.4 for the inverted pendulum. A † marks separately trained dynamics networks. good as trajectories planned on the real system state. All models besides E2C fail to give long-term predictions that result in good performance.

Learning swing-up for an inverted pendulum
We next turn to the task of controlling the classical inverted pendulum system [18,19] from images. We create depictions of the state by rendering a fixed length line starting from the center of the image at an angle corresponding to the pendulum position. The goal in this task then is to swing-up and balance an underactuated pendulum from a resting position, in which the pendulum is hanging down. Exemplary observations and reconstructions for this system are given in Figure 3 (d). In the visual inverted pendulum task our algorithm faces two additional difficulties: the observed space is non-Markov, as the angular velocity cannot be inferred from a single image, and second, discretization errors due to rendering pendulum angles as small 48x48 pixel images make exact control difficult.
To restore the Markov property, we stack two images (increasing the number of input channels), thus observing a one-step history.  can learn a meaningful embedding, cleanly seperating velocities from positions, from this noisy data is remarkable; and no other model recovered this shape. Table 1 again compares the different models quantitatively. While the E2C model is not the best in terms of reconstruction performance, it is the only model resulting in stable swing-up and balance behavior. The only other model that can be used to swing-up an inverted pendulum is the E2C model with non-linear dynamics, which however does not result in a control that can balance the pole once swung-up. We explain this failure with the fact that the non-linear latent dynamics model cannot be guaranteed to be linearizable for all control magnitudes, resulting in undesired behavior around unstable fixpoints of the real system dynamics. Also note that for this task a globally linear dynamics model is inadequate.

Balancing a cart-pole and controlling a simulated robot arm
Finally, we consider control of two more complex dynamical systems from high-dimensional images using a six layer convolutional inference and six layer up-convolutional generative network, resulting in a 12-layer deep path from input to reconstruction. Specifically, we control a visual version of the classical cart-pole system [20] from a history of two raw 80 × 80 pixel images as well as a three-link planar robot arm based on a history of two 128 × 128 pixel images. The latent space was set to be 8 dimensional in both experiments. The real state dimensionality for the cart-pole is four and is controlled using one action while for the arm the real state can be described in 6 dimensions (joint angles and velocities) and controlled using a three-dimensional action vector corresponding to motor torques. We simply used cost weights diag(R z ) = 1, diag(R u ) = 1 in both experiments.
As in previous experiments the E2C model seems to have no problem finding a locally linear embedding of images into latent space in which control can be performed. Figure 4 depicts exemplary images -for both problems -from a trajectory executed by our system when combined with MPC. The costs for these trajectories (11.13 for the cart-pole, 85.12 for the arm) are only slightly worse than trajectories obtained by AICO operating on the real system dynamics starting from the same start-state (7.28 and 60.74 respectively). The supplementary material contains additional experiments using these domains. A video containing exemplary controlled trajectories for all systems can be found at http://ml.informatik.uni-freiburg.de/research/e2c .

Comparison to recent work
In the context of representation learning for control (see Böhmer et al. [21] for a recent review), deep autoencoders (ignoring state transitions) similar to those used in our comparison have been applied previously, e.g. by Lange and Riedmiller [22]. A more direct route to achieve control based on image streams is taken by recent work employing end-to-end reinforcement learning from raw images. This approach has been used by Mnih et al. [23], who learn deep non-linear Q-functions and Levine et al. [24] who learn a deep policy mapping directly to motor torques.
Close to the approach we propose is a recent paper by Wahlström et al. [25], where autoencoders are used to extract a latent representation from images, on which a non-linear model of the (latent) forward dynamics is learned with MLPs. This model is then used in combination with MPC. The autoencoder and dynamics model are trained jointly and are thus similar to the non-linear E2C variant in our comparison. In contrast to our model the approach however requires pre-processing by PCA and does neither ensure that long-term predictions in latent space do not diverge, nor that they are linearizable.
As stated above, our system belongs to the family of VAEs and is generally similar to recent work such as Kingma and Welling [7], Rezende et al. [8], Gregor et al. [26], Bayer and Osendorfer [27]. While we learn a latent dynamics model for control, our approach shares with Gregor et al. [28] another recent stochastic VAE variant -the use of a history of image sequences to learn the latent representation. Two additional parallels between our work and recent advances for training deep neural networks can be observed. First, the idea of enforcing desired transformations in latent space during learning, such that the the data is easy to model in that space, has appeared several times already in the literature. This includes the development of transforming auto-encoders [29] and recent probabilistic models for images [30,31]. Second, learning relations between pairs of images -although without control -has received considerable attention from the community during the last years [32,33]. We refer to Memisevic [33] for a recent overview and note that the predicted transition matrices A t and B t in the E2C algorithm can implement the multiplicative interactions typically found in these models.
In a broader context our model is also related to work on learning non-linear (latent) dynamic models for observations in a Markov decision process through, e.g., hidden Markov models and Kalman filters [34,35,36]. We refer to Langford et al. [37] for a recent discussion and a general formalization of this problem.

Conclusion
We presented Embed to Control (E2C), a system for stochastic optimal control on high-dimensional image streams. Key to the approach is the extraction of a latent dynamics model which is constrained to be locally linear in its state transitions. An evaluation on four challenging benchmarks revealed that E2C can find embeddings on which control can be performed with ease, reaching performance close to that achievable by optimal control on the real system model.
is simply not an option. We thus decided to use deconvolution or up-convolutional networks which were recently show to be powerful models for image generation [9,10,11].
To set-up these models we basically "mirror" the convolutional architecture used for the encoder. More specifically for each 5 × 5 convolution followed by 2 × 2 max-pooling step in the encoder network we introduce a 5 × 5 convolution and 2 × 2 up-sampling step in the decoder network. The complete network architecture is given below. It is similar to the up-convolution networks used in Dosovitskiy et al. [10]. As the up-sampling strategy we used simple "perforated" up-sampling as described in [38].

B.2 Variational Autoencoder with slowness
Enforcing temporal slowness during learning has previously been found to be a good proxy for learning representations in reinforcement learning [39,40], and representation learning from videos [41]. We also consider a VAE variant with a slowness term on the latent representation by enforcing similarity of the encodings of temporally close images. This can be achieved by augmenting the standard VAE objective L bound with an additional KL divergence term on the latent posterior Q φ : Indeed there seems to be a slightly better coherence of similar states in the latent spaces, as e.g. depicted in Figure 8 in the main paper. Yet, our experiments show that a slowness term alone does not suffice to structure the latent space such that locally linear predictions and control become feasible.

B.3 Evaluation criteria
For comparing the performance of all variants of E2C and the baselines, the following criteria are of importance: • Autoencoding. Being able to reconstruct the given observations is the basic necessity for a model to work. The reconstruction cost drives a model to identify single states from its observations. • Decoding the next state. For any planning to be possible at all, the decoder must be able to generate the correct images from the transitions the dynamics model performed. If this is not the case, we know that the latent states of the encoding and the transition model do not coincide, thus preventing any planning. • Optimizing latent trajectory costs. The action sequences for achieving a specified goal will be determined completely by locally linearized dynamics in the latent space. Therefore minimizing trajectory costs in latent space is, again, a necessity for successful control. • Optimizing real trajectory costs. While the action sequence has been determined for the latent dynamics, the deciding criterion is whether this reflects the true state trajectory costs. Therefore carrying out the "dreamed" plans in reality is the optimality criterion for every model.
We reflected these four criteria in the evaluation table in the paper. For the reconstruction of the current and next state we specified the mean log loss, which is in case of the Bernoulli distributions the cross entropy error function: For the costs a model imagines and truly achieves, we sample from different starting states and accumulate the distances in latent and true state space according to the SOC method.

B.4 The three-link robot arm
The robot arm we used in the last experiment in the main paper was simulated using dynamics generated by the MapleSim http://www.maplesoft.com/products/maplesim/ simulator wrapped in Python and visualized for producing inputs to E2C using PyGame. We simulated a fairly standard robot arm with three links. The length of the links were set to 2, 1.2 and 0.7 (units were set to meters). The masses of the corresponding links were all set to 10kg.

B.5 Evaluating the true system model
To compare the efficacy of different models when combined with optimal control algorithms we always reported the cost in latent space (as used by the optimal control algorithm) as well as the "real" trajectory cost. To compute this real cost we computed the same cost function as in the latent space (quadratic costs on the deviation from a given goal state) but using the real system states during execution of the trajectory that was planned entirely in the latent state.
As an upper bound on the performance achievable for control by any of the models we also computed the true system cost by applying iLQR/AICO to a model of the real system dynamics. We have this model available since all experiments were performed in simulation. In order to learn dynamics predictions for the image-only autoencoders, we extracted the latent representations and combined them with the actions from D into On these low-dimensional representations we trained the dynamics MLPs, thus ensuring that all methods were trained on exactly the same data.

B.6.2 Implementation details
We used orthogonal weight initialization for every layer [42]. As described in the main paper Adam [16] was used as the learning rule for all networks. We found both these techniques to be fundamentally important for stabilizing training and achieving good reconstructions for all methods. Both methods also clearly helped to cut the hyperparameter search needed for all methods to a minimum. In the process of training, we could make out three phases: the unfolding of the latent space, the overcoming of the trivial solution (the average image of the dataset) and the minimization of the latent KL term.  Figure 5: Generated "dreamed" trajectories of different models for the plane task (from left to right). The opacity of the obstacles has been lowered in this depiction for better visibility of the agent.

C Supplementary evaluations C.1 Trajectories for plane and pendulum
To qualitatively measure the predictive accuracy, the starting state for a trajectory is encoded and the actions are applied on the latent representation. After each transition, the predicted latent position is decoded and visualized. In this manner, multi-step predictions can be generated for the planar system in Figure 5 and for the inverted pendulum in Figures 6 and 7.  Figure 6: Generated "dreamed" trajectories (from left to right) for passive dynamics: the pendulum starts with angle θ = − π 2 without velocity. The models have to predict the dynamics, while no force is applied.  Figure 7: Dreamed trajectories (from left to right) for controlled dynamics: the pendulum starts with angle θ = π 2 without velocity. For 6 timesteps, full force is applied to the right, followed by 4 timesteps of full force to the left.

C.3 Trajectories for cart-pole and three-link arm
Finally -similar to the images in Section C.1 - Figure 9 shows multi-step predictions for the cartpole system. We depict show important cases, a long-term prediction with the cart-pole standing still (essentially the unstable fix-point of the underlying dynamics). The cart-pole moving to the right, changing the direction of the poles angular velocity (middle column) and the pole moving farthest to the right. The long-term predictions by the E2C model are all of high quality. Note that for the uncontrolled dynamics the predictions show a slight bias of the pole moving to the right (an effect that we consistently saw in trained models for the cart-pole). We attribute this problem to the fact that discretization errors when rendering the pole angle make it hard to predict small velocities accurately.

Moving left Moving right
Real Generated E2C Real Generated E2C Real Generated E2C Figure 9: Dreamed trajectories (top to bottom) for uncontrolled (left column) and controlled (middle/right column) dynamics in the cart-pole system. The red image shows the initial configuration which is encoded to give z 1 the images in the right part of each column are then generated without additional input by following the dynamics in latent space. The left column depicts the uncontrolled case (u = 0 for all steps). The middle column shows a controlled trajectory with torque −20 applied in each step and the right column a trajectory with torque 20 applied in each step. Prediction of the history image is omitted in these images.
C.4 Exemplary trajectory taken for three-link arm task Figure 10 shows a segment of a controlled trajectory as executed by the E2C system. Note that, in contrast to other figures in this supplementary material, it does not show a long-term prediction but rather 10 steps of a trajectory (together with one-step-ahead predictions) that was taken by the E2C system when combined with model predictive control. For additional visualizations and controlled trajectories for all tasks we refer to the supplementary video.

C.5 Comparison of trajectory optimizers for cart-pole and robot arm
To compare how well AICO deals with the covariance matrices estimated in latent space we performed an additional experiment using on the cart-pole and three-link robot arm task comparing it to iLQR. We performed model predictive control using the locally linear E2C model starting in 10 different start states each. For the cart-pole this was always the goal state (zero angle and zero velocity) with small gaussian noise with variance 0.01. For the three-link arm system this was always a random starting position in the configuration space (while the goal always was to unroll all robot joints (e.g. make all angles zero).
As reported in Table C.5 both methods performed about the same for these tasks with a slight advantage for AICO.