Content deleted Content added
Narky Blert (talk | contribs) DN tag |
Citation bot (talk | contribs) Added website. | Use this bot. Report bugs. | Suggested by Dominic3203 | Linked from User:LinguisticMystic/cs/outline | #UCB_webform_linked 1627/2277 |
||
| (14 intermediate revisions by 7 users not shown) | |||
Line 1:
{{Infobox software
| name = PSL
| logo = PSL_Logo.png
| developer = [https://linqs.soe.ucsc.edu/ LINQS Lab]
| released = {{Start date|2011|09|23}}
| latest release version = 2.2.2<ref name=psl:repo:2.2.2 />
| latest release date = {{Start date|2020|05|20}}
| repo = {{URL|https://github.com/linqs/psl}}
| programming language = [[Java (programming language)|Java]]
| platform = [[Linux]], [[macOS]], [[Windows]]
| genre = [[Machine Learning]], [[Statistical relational learning]]
| license = [[Apache License 2.0]]
| website = {{URL|https://psl.linqs.org}}
}}
'''Probabilistic Soft Logic (PSL)''' is a [[Statistical relational learning | statistical relational learning (SRL)]] framework for modeling probabilistic and relational domains.
<ref name=bach:jmlr17 />
It is applicable to a variety of [[machine learning]] problems, such as [[collective classification]], [[Record linkage | entity resolution]], [[link prediction]], and [[ontology alignment]].
PSL combines two tools: [[first-order logic]], with its ability to succinctly represent complex phenomena, and [[graphical model | probabilistic graphical models]], which capture the uncertainty and incompleteness inherent in real-world knowledge.
More specifically, PSL uses [[Fuzzy logic | "soft" logic]] as its logical component and [[Markov random fields]] as its statistical model.
PSL provides sophisticated inference techniques for finding the most likely answer (i.e. the [[Maximum_a_posteriori_estimation|maximum a posteriori (MAP)]] state).
The "softening" of the logical formulas makes inference a [[polynomial time]] operation rather than an [[NP-hardness | NP-hard]] operation.
== Description ==
The [[Statistical relational learning | SRL]] community has introduced multiple approaches that combine [[graphical model]]s and [[first-order logic]] to allow the development of complex probabilistic models with relational structures.
A notable example of such approaches is [[Markov logic network]]s (MLNs).
<ref name=getoor:book07 />
Like MLNs, PSL is a modelling language (with an accompanying implementation<ref name=psl:repo />) for learning and predicting in relational domains.
Unlike MLNs, PSL uses soft truth values for predicates in an interval between [0,1].
This allows for the underlying inference to be solved quickly as a convex optimization problem.
This is useful in problems such as [[collective classification]], [[link prediction]], [[social network]] modelling, and [[record linkage|object identification/entity resolution/record linkage]].
Probabilistic Soft Logic was first released in 2009 by [[Lise Getoor]] and Matthias Broecheler.
<ref name=broecheler:srl09 />
This first version focused heavily on reasoning about similarities between entities.
Later versions of PSL would still keep the ability to reason about similarities, but generalize the language to be more expressive.
In 2017, a [[Journal of Machine Learning Research]] article detailing PSL and the underlying graphical model was published along with the release of a new major version of PSL (2.0.0).
<ref name=bach:jmlr17 />
The major new features in PSL 2.0.0 was a new type of rule mainly used in specifying constraints and a [[command-line interface]].
== Syntax and Semantics ==
=== Terminology ===
* PSL Program — A collection of rules, each of which is a template for a potential in a graphical model.
* Rule — An expression relating atoms. Rules will typically take the form of either a [[First-order logic | first-order logical]] implication or a [[Linear combination | linear combination]].
* Constant — A string or number that represents a real element in the universe over which a PSL program represents. Constants can represent attributes or entire entities.
* Variable — An identifier for which constants can be substituted.
* Term — Either a constant or a variable.
* Predicate — A relation defined by a unique name and a number of arguments it accepts.
* Atom — A predicate along with its term arguments.
* Ground Atom — An atom where all arguments are constants.
=== Syntax ===
A PSL model is composed of a series of weighted rules and constraints.
PSL supports two types of rules: Logical and Arithmetic.
<ref name=psl:wiki:rules />
Logical rules are composed of an implication with only a single atom or a conjunction of atoms in the body and a single atom or a disjunction of atoms in the head.
Since PSL uses soft logic, hard logic operators are replaced with [[Lukasiewicz fuzzy logic#Real-valued_semantics | Łukasiewicz soft logical operators]].
An example of a logical rule expression is:
<syntaxhighlight lang="prolog">
Similar(A, B) & HasLabel(A, X) -> HasLabel(B, X)
</syntaxhighlight>
This rule can be interpreted to mean: ''If A and B are similar and A has the label X, then there is evidence that B also has the label X.''
Arithmetic rules are relations of two [[Linear combination | linear combinations]] of atoms.
Restricting each side to a linear combination ensures that the resulting potential is [[Convex function | convex]].
The following relational operators are supported: <code>=</code>, <code><=</code>, and <code>>=</code>.
<syntaxhighlight lang="prolog">
Similar(A, B) = Similar(B, A)
</syntaxhighlight>
This rule encodes the notion that similarity is symmetric in this model.
A commonly used feature of arithmetic rules is the summation operation.
The summation operation can be used to aggregate multiple atoms.
When used, the atom is replaced with the sum of all possible atoms where the non-summation variables are fixed.
Summation variables are made by prefixing a variable with a <code>+</code>.
Fox example:
<syntaxhighlight lang="prolog">
HasLabel(A, +X) = 1.0
</syntaxhighlight>
If the possible values for X are ''label1'', ''label2'', and ''label3'', then the above rule is equivalent to:
<syntaxhighlight lang="prolog">
HasLabel(A, 'label1') + HasLabel(A, 'label2') + HasLabel(A, 'label3') = 1.0
</syntaxhighlight>
Both of these rules force the sum of all possible labels for an entity to sum to 1.0.
This type of rule is especially useful for [[collective classification]] problems, where only one class can be selected.
=== Semantics ===
==== HL-MRF ====
A PSL program defines a family of probabilistic [[graphical model]]s that are parameterized by data.
More specifically, the family of graphical models it defines belongs to a special class of [[Markov random field]] known as a Hinge-Loss Markov Field (HL-MRF).
An HL-MRF determines a density function over a set of continuous variables <math>\mathbf{y} = (y_1, \cdots , y_n)</math> with joint ___domain <math>[0, 1]^n</math> using set of evidence <math>\mathbf{x} = (x_1, \cdots , x_m)</math>, weights <math>\mathbf{w} = (w_1, \cdots , w_k)</math>, and potential functions <math>\mathbf{\phi} = (\phi_1, \cdots , \phi_k)</math> of the form <math>\mathbf{\phi_i (\mathbf{x}, \mathbf{y})} = \max(\ell_i (\mathbf{x}, \mathbf{y}), 0)^{d_i}</math> where <math>\ell_i</math> is a linear function and <math>d_i \in \{1,2\}</math>.
The conditional distribution of <math>\mathbf{y}</math> given the observed data <math>\mathbf{x}</math> is defined as
<math>P(\mathbf{y} | \mathbf{x}) = \frac{1}{Z(\mathbf{y})} \exp(\sum_{i = 1}^{k} w_i \phi_i (\mathbf{x}, \mathbf{y}))</math>
Where <math>Z(\mathbf{y}) = \int_{\mathbf{y}} \exp(\sum_{i = 1}^{k} w_i \phi_i (\mathbf{x}, \mathbf{y}))</math> is the partition function.
This density is a [[logarithmically convex function]], and thus the common inference task in PSL of finding a [[maximum a posteriori estimation]] of the joint state of <math>\mathbf{y}</math> is a convex problem.
This allows inference in PSL to be achievable in polynomial-time.
==== Open/Closed Predicates -- Closed World Assumption ====
Predicates in PSL can be labeled as open or closed.
When a predicate is labeled closed, PSL makes the [[closed-world assumption]]: any predicates that are not explicitly provided to PSL are assumed to be false.
In other words, the closed world assumption presumes that a predicate that is partially true is also known to be partially true.
For example, if we had the following constants in the data for representing people: <math>\{Alice, Bob\}</math> and the following constant for movies: <math>\{Avatar\}</math>, and we provided PSL with the predicate data <math>\{rating(Alice, Avatar) = 0.8\}</math> and <math>rating(\cdot)</math> was labeled closed, then PSL would assume that <math>\{rating(Bob, Avatar) = 0\}</math> even though this data was never explicitly provided to the system.
If a predicate is labeled as open, then PSL does not make the closed-world assumption. Instead, PSL will attempt to collectively infer the unobserved instances.
==== Grounding ====
Data is used to instantiate several potential functions in a process called grounding.
The resulting potential functions are then used to define the HL-MRF.
Grounding predicates in PSL is the process of making all possible substitutions of the variables in each predicate with the existing constants in the data, resulting in a collection of ground atoms, <math>\mathbf{y} = \{y_1, \cdots, y_n\}</math>.
Then, all possible substitutions of the ground atoms for the predicates in the rules are made to create ground rules.
Each of the ground rules are interpreted as either potentials or hard constraints in the induced HL-MRF.
A logical rule is translated as a continuous relaxation of Boolean connectives using [[Łukasiewicz logic]].
A ground logical rule is transformed into its [[disjunctive normal form]].
Let <math>I^{+}</math> be the set of indices of the variables that correspond to atoms that are not negated, and, likewise <math>I^{-}</math> the set of indices corresponding to atoms that are negated, in the disjunctive clause.
Then the logical rule maps to the inequality:
<math>1 - \sum_{i \in I^+} y_i - \sum_{i \in I^-}(1 - y_i) \leq 0</math>
If the logical rule is weighted with a weight <math>w</math> and exponentiated with <math>d \in \{1, 2\}</math>, then the potential
<math>\phi(\mathbf{y}) = \Big ( \max \Big \{ 1 - \sum_{i \in I^+} y_i - \sum_{i \in I^-}(1 - y_i), 0\Big \} \Big )^{d}</math>
is added to the HL-MRF with a weight parameter of <math>w</math>.
An arithmetic rule is manipulated to <math>\ell(\mathbf{y}) \leq 0</math> and the resulting potential takes the form <math>\phi(\mathbf{y}) = (\max \{\ell(\mathbf{y}), 0\})^{d}</math>.
== Interfaces ==
PSL is available via three different language [[Application programming interface | interfaces]]: [[Command-line interface | CLI]], [[Java (programming language) | Java]], and [[Python (programming language) | Python]].
PSL's command line interface (CLI) is the recommended way to use PSL.
<ref name=psl:blog:gettingstarted />
It supports all the features commonly used in a reproducible form that does not require compilation.
Since PSL is written in Java, the PSL Java interface is the most expansive and users can call directly into the core of PSL.
<ref name=psl:api />
The Java interface is available through the [[Apache Maven | Maven]] central repository.
<ref name=maven:psl:java />
The PSL Python interface is available through [[Python Package Index | PyPi]]
<ref name=pypi:pslpython />
and uses [[pandas (software) | pandas]] DataFrames to pass data between PSL and the user.
<ref name=psl:blog:2.2.1:python />
PSL previously provided a Groovy interface.
<ref name=maven:psl:groovy />
It has been deprecated in 2.2.1 release of PSL, and is scheduled to be removed in the 2.3.0 release.
<ref name=psl:blog:2.2.1:groovy />
== Examples ==
The LINQS lab, developers of the official PSL implementation, maintain a collection of PSL examples.
<ref name=psl:repo:examples />
These examples cover both synthetic and real-world datasets and include examples from academic publications using PSL.
Below is a toy example from this repository that can be used to infer relations in a social network.
Along with each rule is a comment describing the motivating intuition behind the statements.
<syntaxhighlight lang="prolog">
/* People living in the same ___location are more likely to know one another. */
20: Lived(P1, L) & Lived(P2, L) & (P1 != P2) -> Knows(P1, P2) ^2
/* People who have not lived in the same ___location are not likely to know one another. */
5: Lived(P1, L1) & Lived(P2, L2) & (P1 != P2) & (L1 != L2) -> !Knows(P1, P2) ^2
/* Two people with similar interests are more likely to know one another. */
10: Likes(P1, X) & Likes(P2, X) & (P1 != P2) -> Knows(P1, P2) ^2
/* People in the same circles tend to know one another (transitivity). */
5: Knows(P1, P2) & Knows(P2, P3) & (P1 != P3) -> Knows(P1, P3) ^2
/* Knowing one another is symmetric. */
Knows(P1, P2) = Knows(P2, P1) .
/* By default, assume that two arbitrary people do not know one another (negative prior). */
5: !Knows(P1, P2) ^2
</syntaxhighlight>
== See also ==
* [[Statistical relational learning]]
* [[Probabilistic logic network]]
Line 10 ⟶ 192:
* [[Fuzzy logic]]
== References ==
{{reflist|
refs=
<ref name=bach:jmlr17>
{{cite journal |last1=Bach |first1=Stephen |last2=Broecheler |first2=Matthias |last3=Huang |first3=Bert |last4=Getoor |first4=Lise |date=2017 |title=Hinge-Loss Markov Random Fields and Probabilistic Soft Logic |journal=Journal of Machine Learning Research |volume=18 |pages=1–67}}
</ref>
<ref name=broecheler:srl09>
{{cite conference |url=https://linqs.github.io/linqs-website/publications/#id:broecheler-srl09 |title=Probabilistic Similarity Logic |last1=Broecheler |first1=Matthias |last2=Getoor |first2=Lise |author-link2=Lise Getoor |date=2009 |conference=International Workshop on Statistical Relational Learning (SRL) }}
</ref>
<ref name=getoor:book07>
{{cite book |last1=Getoor |first1=Lise |last2=Taskar |first2=Ben |author-link1=Lise Getoor |author-link2=Ben Taskar |date=2007 |title=Introduction to Statistical Relational Learning |url=https://linqs.github.io/linqs-website/publications/#id:getoor-book07 |publisher=MIT Press |isbn=978-0262072885}}
</ref>
<ref name=maven:psl:groovy>
{{cite web |title=Maven Repository: org.linqs » psl-groovy |url=https://mvnrepository.com/artifact/org.linqs/psl-groovy |website=mvnrepository.com}}
</ref>
<ref name=maven:psl:java>
{{cite web |title=Maven Repository: org.linqs » psl-java |url=https://mvnrepository.com/artifact/org.linqs/psl-java |website=mvnrepository.com |accessdate=15 July 2020}}
</ref>
<ref name=psl:api>
{{cite web |title=PSL API Reference |url=https://psl.linqs.org/api/ |website=Probabilistic Soft Logic |accessdate=15 July 2020 |language=en}}
</ref>
<ref name=psl:blog:2.2.1:python>
{{cite web |last1=Augustine |first1=Eriq |title=PSL 2.2.1 Release |url=https://psl.linqs.org/blog/2019/12/06/psl-2.2.1-release.html#new-python-interface |website=Probabilistic Soft Logic |accessdate=15 July 2020 |language=en |date=6 December 2019}}
</ref>
<ref name=psl:blog:gettingstarted>
{{cite web |last1=Augustine |first1=Eriq |title=Getting Started with PSL |url=https://psl.linqs.org/blog/2018/07/15/getting-started-with-psl.html |website=Probabilistic Soft Logic |accessdate=15 July 2020 |language=en |date=15 July 2018}}
</ref>
<ref name=psl:blog:2.2.1:groovy>
{{cite web |last1=Augustine |first1=Eriq |title=PSL 2.2.1 Release |url=https://psl.linqs.org/blog/2019/12/06/psl-2.2.1-release.html#groovy-interface-deprecated |website=Probabilistic Soft Logic |accessdate=15 July 2020 |language=en |date=6 December 2019}}
</ref>
<ref name=psl:repo>
{{cite web|url=https://github.com/linqs/psl|title=GitHub repository|website=[[GitHub]] |accessdate=26 March 2018}}
</ref>
<ref name=psl:repo:examples>
{{cite web |title=linqs/psl-examples |url=https://github.com/linqs/psl-examples |website=Github |publisher=linqs |date=19 June 2020}}
</ref>
<ref name=psl:wiki:rules>
{{cite web | url=https://psl.linqs.org/wiki/master/Rule-Specification.html |title=Rule Specification |author=<!--Not stated--> |date=December 6, 2019 |website=psl.linqs.org |publisher=LINQS Lab |access-date=July 10, 2020}}
</ref>
<ref name=pypi:pslpython>
{{cite web |title=pslpython: A python inferface to the PSL SRL/ML software. |url=https://pypi.org/project/pslpython/ |website=Python Package Index |accessdate=15 July 2020}}
</ref>
<ref name=psl:repo:2.2.2>
{{cite web | url = https://github.com/linqs/psl/tree/2.2.2 | title = PSL 2.2.2 | website = GitHub | language = en-US | accessdate = 16 July 2020}}
</ref>
}}
== External links ==
* [https://www.youtube.com/channel/UCJjzqRLiAIa3qENUkzK0zMA Video lectures about PSL on Youtube]
[[Category:Bayesian statistics]]
| |||