Markov LogicOverviewThe Interface LayerNetworkingDatabasesArtificial IntelligenceSlide 7Slide 8Slide 9Slide 10Slide 11Markov NetworksSlide 13First-Order LogicSlide 15Slide 16DefinitionExample: Friends & SmokersSlide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Markov Logic NetworksSlide 27Relation to Statistical ModelsRelation to First-Order LogicSlide 30InferenceMost Probable Explanation (MPE) InferenceMPE InferenceSlide 34Slide 35Slide 36Computing Probabilities: Marginal InferenceMarginal InferenceSlide 39Belief PropagationSlide 41Slide 42Slide 43Lifted Belief PropagationSlide 45Slide 46Slide 47Learning ParametersSlide 49Slide 50Slide 51Slide 52Slide 53Learning Parameters (Discriminative)Learning Parameters (Discriminative)Learning StructureSlide 57Slide 58Slide 59Slide 60ApplicationsEntity ResolutionSlide 63Slide 64Slide 65PredicatesPredicates & FormulasSlide 68Slide 69Slide 70Discovery of Social Relationships in Consumer Photo CollectionsMLN RulesModels ComparedResults (7 Different Relationships)AlchemyMarkov LogicParag SinglaDept. of Computer Science University of Texas, AustinOverviewMotivationBackgroundMarkov logicInferenceLearningApplicationsThe Interface LayerInterface LayerApplicationsInfrastructureNetworkingInterface LayerApplicationsInfrastructureInternetRoutersProtocolsWWWEmailDatabasesInterface LayerApplicationsInfrastructureRelational ModelQueryOptimizationTransactionManagementERPOLTPCRMArtificial IntelligenceInterface LayerApplicationsInfrastructureRepresentationLearningInferenceNLPPlanningMulti-AgentSystemsVisionRoboticsArtificial IntelligenceInterface LayerApplicationsInfrastructureRepresentationLearningInferenceNLPPlanningMulti-AgentSystemsVisionRoboticsFirst-Order Logic?Artificial IntelligenceInterface LayerApplicationsInfrastructureRepresentationLearningInferenceNLPPlanningMulti-AgentSystemsVisionRoboticsGraphical Models?Artificial IntelligenceInterface LayerApplicationsInfrastructureRepresentationLearningInferenceNLPPlanningMulti-AgentSystemsVisionRoboticsStatistical + Logical AIArtificial IntelligenceInterface LayerApplicationsInfrastructureRepresentationLearningInferenceNLPPlanningMulti-AgentSystemsVisionRoboticsMarkov LogicOverviewMotivationBackgroundMarkov logicInferenceLearningApplicationsMarkov NetworksUndirected graphical modelsCancerCoughAsthmaSmokingPotential functions defined over cliquesSmoking Cancer Ф(S,C)False False 4.5False True 4.5True False 2.7True True 4.5cccxZxP )(1)(xcccxZ )(Markov NetworksUndirected graphical modelsLog-linear model:Weight of Feature i Feature iotherwise0CancerSmokingif1)CancerSmoking,(1f5.11wCancerCoughAsthmaSmokingiiixfwZxP )(exp1)(First-Order LogicConstants, variables, functions, predicatesAnna, x, MotherOf(x), Friends(x,y)Grounding: Replace all variables by constantsFriends (Anna, Bob)Formula: Predicates connected by operatorsSmokes(x)  Cancer(x)Knowledge Base (KB): A set of formulasCan be equivalently converted into a clausal formWorld: Assignment of truth values to all ground predicatesOverviewMotivationBackgroundMarkov logicInferenceLearningApplicationsMarkov LogicA logical KB is a set of hard constraintson the set of possible worldsLet’s make them soft constraints:When a world violates a formula,It becomes less probable, not impossibleGive each formula a weight(Higher weight  Stronger constraint)  satisfiesit formulas of weightsexpP(world)DefinitionA Markov Logic Network (MLN) is a set of pairs (F, w) whereF is a formula in first-order logicw is a real numberTogether with a finite set of constants,it defines a Markov network withOne node for each grounding of each predicate in the MLNOne feature for each grounding of each formula F in the MLN, with the corresponding weight wExample: Friends & Smokers)()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesxExample: Friends & Smokers)()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesx1.15.1Example: Friends & SmokersTwo constants: Ana (A) and Bob (B))()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesx1.15.1Example: Friends & SmokersCancer(A)Smokes(A) Smokes(B)Cancer(B)Two constants: Ana (A) and Bob (B))()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesx1.15.1Example: Friends & SmokersCancer(A)Smokes(A)Friends(A,A)Friends(B,A)Smokes(B)Friends(A,B)Cancer(B)Friends(B,B)Two constants: Ana (A) and Bob (B))()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesx1.15.1Example: Friends & SmokersCancer(A)Smokes(A)Friends(A,A)Friends(B,A)Smokes(B)Friends(A,B)Cancer(B)Friends(B,B)Two constants: Ana (A) and Bob (B))()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesx1.15.1Example: Friends & SmokersCancer(A)Smokes(A)Friends(A,A)Friends(B,A)Smokes(B)Friends(A,B)Cancer(B)Friends(B,B)Two constants: Ana (A) and Bob (B))()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesx1.15.1Example: Friends & SmokersCancer(A)Smokes(A)Friends(A,A)Friends(B,A)Smokes(B)Friends(A,B)Cancer(B)Friends(B,B)Two constants: Ana (A) and Bob (B))()(),(,)()(ySmokesxSmokesyxFriendsyxxCancerxSmokesx1.15.1State of the World  {0,1} Assignment to the nodesMarkov Logic NetworksMLN is template for ground Markov networksProbability of a world x:One feature for each ground formula formulasgroundkkkxfwZxP )(exp1)(otherwise 0x given satisfied isformula if1)(kth xfkMarkov Logic NetworksMLN is template for ground Markov netsProbability of a world x:Weight of formula i No. of true groundings of formula i in x formulas MLN)(exp1)(iiixnwZxP formulasgroundkkkxfwZxP )(exp1)(Relation to Statistical ModelsSpecial cases:Markov networksMarkov random fieldsBayesian networksLog-linear modelsExponential modelsMax. entropy modelsGibbs distributionsBoltzmann machinesLogistic regressionHidden Markov modelsConditional random fieldsObtained by making all predicates zero-arityMarkov logic allows objects to be interdependent (non-i.i.d.)Relation to First-Order LogicInfinite weights  First-order logicSatisfiable KB, positive weights  Satisfying assignments = Modes of distributionMarkov logic allows contradictions between