Island algorithm - Revision history

The Anome: Adding short description: "Algorithm for performing inference on statistical models"

2024-10-28T19:00:47Z

Adding short description: "Algorithm for performing inference on statistical models"

← Previous revision		Revision as of 19:00, 28 October 2024
Line 1:		Line 1:
			{{Short description\|Algorithm for performing inference on statistical models}}
	The '''island algorithm''' is an [[algorithm]] for performing inference on [[hidden Markov models]], or their generalization, [[dynamic Bayesian networks]].		The '''island algorithm''' is an [[algorithm]] for performing inference on [[hidden Markov models]], or their generalization, [[dynamic Bayesian networks]].
	It calculates the [[marginal distribution]] for each unobserved node, conditional on any observed nodes.		It calculates the [[marginal distribution]] for each unobserved node, conditional on any observed nodes.

GreenC bot: Rescued 1 archive link. Wayback Medic 2.5

2021-04-30T15:09:36Z

Rescued 1 archive link. Wayback Medic 2.5

← Previous revision		Revision as of 15:09, 30 April 2021
Line 3:		Line 3:

	The island algorithm is a modification of [[belief propagation]].		The island algorithm is a modification of [[belief propagation]].
	It trades smaller [[memory usage]] for longer running time: while belief propagation takes [[Big O notation\|O(n)]] time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.<ref>J. Binder, K. Murphy and S. Russell. [https://pdfs.semanticscholar.org/8400/8ac8ea812b5955ffeedd4b27f4cb3a6958c8.pdf Space-Efficient Inference in Dynamic Probabilistic Networks]. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>		It trades smaller [[memory usage]] for longer running time: while belief propagation takes [[Big O notation\|O(n)]] time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.<ref>J. Binder, K. Murphy and S. Russell. [https://web.archive.org/web/20180102191353/https://pdfs.semanticscholar.org/8400/8ac8ea812b5955ffeedd4b27f4cb3a6958c8.pdf Space-Efficient Inference in Dynamic Probabilistic Networks]. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>

	==The algorithm==		==The algorithm==

Kku: lx

2019-09-25T13:17:04Z

← Previous revision		Revision as of 13:17, 25 September 2019
Line 3:		Line 3:

	The island algorithm is a modification of [[belief propagation]].		The island algorithm is a modification of [[belief propagation]].
	It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.<ref>J. Binder, K. Murphy and S. Russell. [https://pdfs.semanticscholar.org/8400/8ac8ea812b5955ffeedd4b27f4cb3a6958c8.pdf Space-Efficient Inference in Dynamic Probabilistic Networks]. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>		It trades smaller [[memory usage]] for longer running time: while belief propagation takes [[Big O notation\|O(n)]] time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.<ref>J. Binder, K. Murphy and S. Russell. [https://pdfs.semanticscholar.org/8400/8ac8ea812b5955ffeedd4b27f4cb3a6958c8.pdf Space-Efficient Inference in Dynamic Probabilistic Networks]. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>

	==The algorithm==		==The algorithm==

	For simplicity, we describe the algorithm on hidden Markov models. It can be easily generalized to dynamic Bayesian networks by using a [[junction tree]].		For simplicity, we describe the algorithm on hidden Markov models. It can be easily generalized to dynamic Bayesian networks by using a [[junction tree]].

	Belief propagation involves sending a message from the first node to the second, then using this message to compute a message from the second node to the third, and so on until the last node (node N). Independently, it performs the same procedure starting at node N and going in reverse order. The i-th message depends on the (i-1)-th, but the messages going in opposite directions do not depend on one another. The messages coming from both sides are required to calculate the marginal distribution for a node.		Belief propagation involves sending a message from the first node to the second, then using this message to compute a message from the second node to the third, and so on until the last node (node N). Independently, it performs the same procedure starting at node N and going in reverse order. The i-th message depends on the (i-1)-th, but the messages going in opposite directions do not depend on one another. The messages coming from both sides are required to calculate the marginal distribution for a node. In normal belief propagation, all messages are stored, which takes O(n) memory.
	In normal belief propagation, all messages are stored, which takes O(n) memory.

	The island begins by passing messages as usual, but it throws away the i-th message after sending the (i+1)-th one.		The island begins by passing messages as usual, but it throws away the i-th message after sending the (i+1)-th one.
	When the two message-passing procedures meet in the middle, the algorithm recurses on each half of the chain.		When the two message-passing procedures meet in the middle, the algorithm recurses on each half of the chain.

	Since the chain is divided in two at each recursive step, the depth of the recursion is log(N). Since every message must be passed again at each level of depth, the algorithm takes O(n log n) time on a single processor. Two messages must be stored at each recursive step, so the algorithm uses O(log n) space.		Since the chain is divided in two at each recursive step, the depth of the [[recursion]] is log(N). Since every message must be passed again at each level of depth, the algorithm takes O(n log n) time on a single processor. Two messages must be stored at each recursive step, so the algorithm uses O(log n) space.
	Given log(N) processors, algorithm can be run in O(n) time by using a separate processor to do each recursive step (thus taking N/2 + N/4 + N/8 ... = N time on a single processor).		Given log(N) processors, algorithm can be run in O(n) time by using a separate processor to do each recursive step (thus taking N/2 + N/4 + N/8 ... = N time on a single processor).

194.78.116.114 at 08:56, 2 January 2019

2019-01-02T08:56:11Z

← Previous revision		Revision as of 08:56, 2 January 2019
Line 16:		Line 16:

	Since the chain is divided in two at each recursive step, the depth of the recursion is log(N). Since every message must be passed again at each level of depth, the algorithm takes O(n log n) time on a single processor. Two messages must be stored at each recursive step, so the algorithm uses O(log n) space.		Since the chain is divided in two at each recursive step, the depth of the recursion is log(N). Since every message must be passed again at each level of depth, the algorithm takes O(n log n) time on a single processor. Two messages must be stored at each recursive step, so the algorithm uses O(log n) space.
	Given log(N) processors, algorithm can be run in O(n) time by using a separate processor to do each recursive step (thus taking N/2 + N/4 + N/8 ... = 1 time on a single processor).		Given log(N) processors, algorithm can be run in O(n) time by using a separate processor to do each recursive step (thus taking N/2 + N/4 + N/8 ... = N time on a single processor).

	==References==		==References==

Jarble: adding links to references using Google Scholar

2018-01-01T20:43:00Z

adding links to references using Google Scholar

← Previous revision		Revision as of 20:43, 1 January 2018
Line 3:		Line 3:

	The island algorithm is a modification of [[belief propagation]].		The island algorithm is a modification of [[belief propagation]].
	It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.<ref>J. Binder, K. Murphy and S. Russell. Space-Efficient Inference in Dynamic Probabilistic Networks. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>		It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.<ref>J. Binder, K. Murphy and S. Russell. [https://pdfs.semanticscholar.org/8400/8ac8ea812b5955ffeedd4b27f4cb3a6958c8.pdf Space-Efficient Inference in Dynamic Probabilistic Networks]. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>

	==The algorithm==		==The algorithm==

Addbot: Bot: Removing Orphan Tag (No longer an Orphan) (Report Errors)

2013-01-09T01:41:41Z

Bot: Removing Orphan Tag (No longer an Orphan) (Report Errors)

← Previous revision		Revision as of 01:41, 9 January 2013
Line 1:		Line 1:
	{{Orphan\|date=June 2012}}

	The '''island algorithm''' is an [[algorithm]] for performing inference on [[hidden Markov models]], or their generalization, [[dynamic Bayesian networks]].		The '''island algorithm''' is an [[algorithm]] for performing inference on [[hidden Markov models]], or their generalization, [[dynamic Bayesian networks]].
	It calculates the [[marginal distribution]] for each unobserved node, conditional on any observed nodes.		It calculates the [[marginal distribution]] for each unobserved node, conditional on any observed nodes.

Jesse V.: tags + general fixes, added orphan tag using AWB

2012-06-29T03:40:16Z

tags + general fixes, added orphan tag using AWB

← Previous revision		Revision as of 03:40, 29 June 2012
Line 1:		Line 1:
			{{Orphan\|date=June 2012}}

	The '''island algorithm''' is an [[algorithm]] for performing inference on [[hidden Markov models]], or their generalization, [[dynamic Bayesian networks]].		The '''island algorithm''' is an [[algorithm]] for performing inference on [[hidden Markov models]], or their generalization, [[dynamic Bayesian networks]].
	It calculates the [[marginal distribution]] for each unobserved node, conditional on any observed nodes.		It calculates the [[marginal distribution]] for each unobserved node, conditional on any observed nodes.

Melcombe: /* References */ add cat

2012-06-11T21:11:34Z

References: add cat

← Previous revision		Revision as of 21:11, 11 June 2012
Line 22:		Line 22:

	[[Category:Bioinformatics algorithms]]		[[Category:Bioinformatics algorithms]]
			[[Category:Hidden Markov models]]

Canley: category

2011-11-27T05:46:42Z

Bearcat: categorization/tagging using AWB

2011-11-18T04:46:35Z

categorization/tagging using AWB

← Previous revision		Revision as of 04:46, 18 November 2011
Line 3:		Line 3:

	The island algorithm is a modification of [[belief propagation]].		The island algorithm is a modification of [[belief propagation]].
	It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory. <ref>J. Binder, K. Murphy and S. Russell. Space-Efficient Inference in Dynamic Probabilistic Networks. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>		It trades smaller memory usage for longer running time: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) memory.<ref>J. Binder, K. Murphy and S. Russell. Space-Efficient Inference in Dynamic Probabilistic Networks. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>

	==The algorithm==		==The algorithm==
Line 20:		Line 20:
	==References==		==References==
	{{reflist}}		{{reflist}}

			{{Uncategorized\|date=November 2011}}

← Previous revision		Revision as of 05:46, 27 November 2011
Line 21:		Line 21:
	{{reflist}}		{{reflist}}

			[[Category:Bioinformatics algorithms]]
	{{Uncategorized\|date=November 2011}}