The problem of causal discovery is to learn the true causal relations among a system of random variables based on the available data. Learning the true causal structure of p variables can sometimes be difficult, but it is crucial in many fields of science, such as biology, sociology and artificial intelligence. Classically, it is assumed that the true causal relations are completely encoded via a directed acyclic graph (DAG), and there are numerous algorithms for estimating a DAG representative of a causal system from data. Assuming it is feasible, the most effective way of learning the true causal structure is through interventional experiments. Eberhardt et al. identified the sufficient and in the worst case necessary number of interventions needed to learn a DAG, and then studied this problem from a game theory perspective, providing an upper bound on the expected number of experiments needed to identify the causal DAG. Here, we consider more general causal models, the CStrees, which allow for the true causal relations to be context-specific. We extend the results of Eberhardt to the family of CStrees by finding the sufficient and in the worst case necessary number of experiments the Scientist must perform in order to discover the true CStree among p variables. We generalize the game theoretic approach presented in Eberhardt's paper, to the CStrees with a specified causal ordering. We also give a geometric description of context-specific hard interventions in CStrees, through a bijection between the stages of the CStree and the faces of a polytope. / Problemet med kausal upptäckt är att lära sig de verkliga orsakssambandet mellan ett system av slumpmässiga variabler baserat på tillgängliga data. Att lära sig den sanna kausala strukturen hos p variabler kan ibland vara svårt, men det är avgörande inom många vetenskapsområden, såsom biologi, sociologi och artificiell intelligens. Klassiskt antas det att de sanna orsakssambandet är helt kodade via en riktad acyklisk graf (DAG), och det finns många algoritmer för att uppskatta en DAG-representant för ett orsakssystem från data. Förutsatt att det är genomförbart är det mest effektiva sättet att lära sig den sanna kausala strukturen genom interventionella experiment. Eberhardt et al. identifierade det tillräckliga och i värsta fall nödvändiga antalet insatser som behövdes för att lära sig en DAG, och studerade sedan detta problem ur ett spelteoriperspektiv, vilket gav en övre gräns för det förväntade antalet experiment som behövs för att identifiera orsakssambandet DAG. Här anser vi att mer allmänna orsakssambandet, CStrees, gör det möjligt att vara kontextspecifik för de verkliga orsakssambandet. Vi utvidgar resultaten av Eberhardt till familjen CStrees genom att hitta det tillräckliga och i värsta fall nödvändiga antalet experiment som forskaren måste utföra för att upptäcka den sanna CStree bland p variabler. Vi generaliserar spelets teoretiska tillvägagångssätt som presenteras i Eberhardts papper, till CStrees med en specificerad kausal ordning. Vi ger också en geometrisk beskrivning av kontextspecifika hårda ingripanden i CStrees, genom ett bijection mellan stadierna i CStree och ansikten på en polytop.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-299521 |
| Date | January 2021 |
| Creators | Karelas, Georgios-Nikolaos |
| Publisher | KTH, Matematik (Avd.) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-SCI-GRU ; 2021:198 |
Page generated in 0.0114 seconds