Hypergraph Format - Revision history

Pdturney: Reverted edits by Creek (talk) to last revision by Chrisq

2012-06-25T11:15:05Z

Reverted edits by Creek (talk) to last revision by Chrisq

← Older revision		Revision as of 11:15, 25 June 2012
Line 41:		Line 41:
	A FeatureVector object has arbitrary fields with float values.		A FeatureVector object has arbitrary fields with float values.

	Example: [http://www.~~thai-sbobet~~.~~com sbo]~~		Example: http://www.isi.edu/~chiang/software/forest/example

	=== Proposed extensions (yea or nay?) / Open questions ===		=== Proposed extensions (yea or nay?) / Open questions ===
Line 122:		Line 122:
	== Tiburon Format ==		== Tiburon Format ==

	[http://www.~~thai~~-~~sbobet.com sbobet~~]		[http://www.isi.edu/licensed-sw/tiburon/ Tiburon Specification]

	== Bindings/Libraries/Software ==		== Bindings/Libraries/Software ==

Creek at 08:20, 25 June 2012

2012-06-25T08:20:34Z

← Older revision		Revision as of 08:20, 25 June 2012
Line 41:		Line 41:
	A FeatureVector object has arbitrary fields with float values.		A FeatureVector object has arbitrary fields with float values.

	Example: http://www.~~isi~~.~~edu/~chiang/software/forest/example~~		Example: [http://www.thai-sbobet.com sbo]

	=== Proposed extensions (yea or nay?) / Open questions ===		=== Proposed extensions (yea or nay?) / Open questions ===
Line 122:		Line 122:
	== Tiburon Format ==		== Tiburon Format ==

	[http://www.~~isi~~.~~edu/licensed-sw/tiburon/ Tiburon Specification~~]		[http://www.thai-sbobet.com sbobet]

	== Bindings/Libraries/Software ==		== Bindings/Libraries/Software ==

Chrisq at 10:08, 12 November 2010

2010-11-12T10:08:13Z

← Older revision		Revision as of 10:08, 12 November 2010
Line 76:		Line 76:
	** David: yea, I think it should be called '''weight''' and the weight of the forest is the sum-product.		** David: yea, I think it should be called '''weight''' and the weight of the forest is the sum-product.
	** ChrisQ: agree.		** ChrisQ: agree.

	* Should Edge have an optional '''features''' field? MERT, amongst other tasks, would need this.

	* Should an Edge with empty '''tails''' be allowed? If so, should the following two forests be considered equivalent:		* Should an Edge with empty '''tails''' be allowed? If so, should the following two forests be considered equivalent:

Chrisq at 10:06, 12 November 2010

2010-11-12T10:06:59Z

← Older revision		Revision as of 10:06, 12 November 2010
Line 71:		Line 71:
	*What do we think about non-coaccessible states? Is a forest well-formed if it contains elements that cannot be reached from the root?		*What do we think about non-coaccessible states? Is a forest well-formed if it contains elements that cannot be reached from the root?
	** David: yes, I don't think the format should care		** David: yes, I don't think the format should care
			** ChrisQ: agree. Provider of forest should ensure that it is well formed

	* Should Edge have an optional '''weight''' field? '''logweight'''?		* Should Edge have an optional '''weight''' field? '''logweight'''?
	** David: yea, I think it should be called '''weight''' and the weight of the forest is the sum-product.		** David: yea, I think it should be called '''weight''' and the weight of the forest is the sum-product.
			** ChrisQ: agree.

			* Should Edge have an optional '''features''' field? MERT, amongst other tasks, would need this.

	* Should an Edge with empty '''tails''' be allowed? If so, should the following two forests be considered equivalent:		* Should an Edge with empty '''tails''' be allowed? If so, should the following two forests be considered equivalent:

David Chiang: /* Proposed extensions (yea or nay?) / Open questions */

2010-11-11T22:54:47Z

Proposed extensions (yea or nay?) / Open questions

← Older revision		Revision as of 22:54, 11 November 2010
Line 85:		Line 85:

	* A tree can be represented as a Forest where every node has only one incoming edge, but is there any desire for a more concise representation of a tree belonging to an existing Forest? Like a list of Edge ids?		* A tree can be represented as a Forest where every node has only one incoming edge, but is there any desire for a more concise representation of a tree belonging to an existing Forest? Like a list of Edge ids?

			* Can/should we require that '''edges''' come after '''nodes'''?

	== Protocol Buffers ==		== Protocol Buffers ==

David Chiang: /* Proposed extensions (yea or nay?) / Open questions */

2010-11-11T21:37:17Z

Proposed extensions (yea or nay?) / Open questions

← Older revision		Revision as of 21:37, 11 November 2010
Line 44:		Line 44:

	=== Proposed extensions (yea or nay?) / Open questions ===		=== Proposed extensions (yea or nay?) / Open questions ===

			* (ChrisD) ''question'': some libraries don't represent node-level features internally (at least Joshua & cdec), so these would need to denormalize node-level features to either all incoming or outgoing edges of the node in question. This may not be completely straightforward to do. Should we possibly consider just edge-level features?
			** David: Since edges are not shared, it should always be easy to propagate node features down to its edges (i.e., to the edges which it is the head of). I would favor, however, eliminating node features.

	*When a hypergraph represents a set of trees, the Node.'''label'''s will be the labels of the tree nodes. It might be convenient to allow a shorthand for leaf/terminal labels: in Edge.'''tails''', a string '''"'''''a'''''"''' would be shorthand for '''{label: "'''''a'''''"}'''		*When a hypergraph represents a set of trees, the Node.'''label'''s will be the labels of the tree nodes. It might be convenient to allow a shorthand for leaf/terminal labels: in Edge.'''tails''', a string '''"'''''a'''''"''' would be shorthand for '''{label: "'''''a'''''"}'''

David Chiang: /* JSON */

2010-11-11T21:37:03Z

JSON

← Older revision		Revision as of 21:37, 11 November 2010
Line 38:		Line 38:
	* '''features''': a FeatureVector object		* '''features''': a FeatureVector object
	and any other application-specific fields.		and any other application-specific fields.
	* (ChrisD) ''question'': some libraries don't represent node-level features internally (at least Joshua & cdec), so these would need to denormalize node-level features to either all incoming or outgoing edges of the node in question. This may not be completely straightforward to do. Should we possibly consider just edge-level features?
	** David: Since edges are not shared, it should always be easy to propagate node features down to its edges (i.e., to the edges which it is the head of). I would favor, however, eliminating node features.

	A FeatureVector object has arbitrary fields with float values.		A FeatureVector object has arbitrary fields with float values.

David Chiang: /* Proposed extensions (yea or nay?) / Open questions */

2010-11-11T21:36:30Z

Proposed extensions (yea or nay?) / Open questions

← Older revision		Revision as of 21:36, 11 November 2010
Line 82:		Line 82:
	</pre>		</pre>
	** David: yes, tailless edges should be allowed, otherwise it's not nice to represent the set of trees { (a b) , (a (b c)) }. But the two example forests above should be considered equivalent since they generate the same set of trees.		** David: yes, tailless edges should be allowed, otherwise it's not nice to represent the set of trees { (a b) , (a (b c)) }. But the two example forests above should be considered equivalent since they generate the same set of trees.

			* A tree can be represented as a Forest where every node has only one incoming edge, but is there any desire for a more concise representation of a tree belonging to an existing Forest? Like a list of Edge ids?

	== Protocol Buffers ==		== Protocol Buffers ==

David Chiang: /* Proposed extensions (yea or nay?) / Open questions */

2010-11-11T21:33:15Z

Proposed extensions (yea or nay?) / Open questions

← Older revision		Revision as of 21:33, 11 November 2010
Line 48:		Line 48:

	*When a hypergraph represents a set of trees, the Node.'''label'''s will be the labels of the tree nodes. It might be convenient to allow a shorthand for leaf/terminal labels: in Edge.'''tails''', a string '''"'''''a'''''"''' would be shorthand for '''{label: "'''''a'''''"}'''		*When a hypergraph represents a set of trees, the Node.'''label'''s will be the labels of the tree nodes. It might be convenient to allow a shorthand for leaf/terminal labels: in Edge.'''tails''', a string '''"'''''a'''''"''' would be shorthand for '''{label: "'''''a'''''"}'''
			** David: yea

	*In Node.'''label''', a value of '''null''' means that the tree node is labeled with epsilon, the empty string. This is not the same as '''""'''': the former would not contribute anything to the yield of the tree, whereas the latter would contribute a token of length 0.		*In Node.'''label''', a value of '''null''' means that the tree node is labeled with epsilon, the empty string. This is not the same as '''""'''': the former would not contribute anything to the yield of the tree, whereas the latter would contribute a token of length 0.
	** David ~~Chiang~~: nay, this should be left to the application. An empty Edge.'''tails''' list has the same effect. And people who care about explicit empty nodes might want to distinguish several kinds of empty nodes (''t'', PRO, pro, etc.).		** David: nay, this should be left to the application. An empty Edge.'''tails''' list has the same effect. And people who care about explicit empty nodes might want to distinguish several kinds of empty nodes (''t'', PRO, pro, etc.).
	** ChrisD: nay. agree with David.		** ChrisD: nay. agree with David.

	*When a hypergraph represents a CFG, the Nodes will be the nonterminal symbols and the Edges will be the productions. It will be ugly for numeric Node ids to appear in the productions, so symbolic names might be preferable. Perhaps a Node object can have a string-valued '''id''' field by which it can be referred to. Con: who is going to guarantee that the names are unique? Alternatively, a Forest object can have a '''nodealiases''' field which is an object mapping from symbolic names to numeric ids.		*When a hypergraph represents a CFG, the Nodes will be the nonterminal symbols and the Edges will be the productions. It will be ugly for numeric Node ids to appear in the productions, so symbolic names might be preferable. Perhaps a Node object can have a string-valued '''id''' field by which it can be referred to. Con: who is going to guarantee that the names are unique? Alternatively, a Forest object can have a '''nodealiases''' field which is an object mapping from symbolic names to numeric ids.
	** ChrisD: I'm in favor of referring to nodes/nonterminals with a numeric id for consistency enforcement (which is admittedly ugly), but supporting optional string aliases/labels for applications that care about such things.		** ChrisD: I'm in favor of referring to nodes/nonterminals with a numeric id for consistency enforcement (which is admittedly ugly), but supporting optional string aliases/labels for applications that care about such things.
			** David: on the fence about this one

	*Another possible extension for edges: it may be useful to encode synchronous forests (for example, imagine the forest of derivations over an input lattice). Do we want to have an optional alt_tails? or a vector of tails (for multiple languages?)?		*Another possible extension for edges: it may be useful to encode synchronous forests (for example, imagine the forest of derivations over an input lattice). Do we want to have an optional alt_tails? or a vector of tails (for multiple languages?)?
Line 69:		Line 72:

	* Should Edge have an optional '''weight''' field? '''logweight'''?		* Should Edge have an optional '''weight''' field? '''logweight'''?
			** David: yea, I think it should be called '''weight''' and the weight of the forest is the sum-product.

			* Should an Edge with empty '''tails''' be allowed? If so, should the following two forests be considered equivalent:
			<pre>
			{ nodes: [ { label: "a" } ],
			edges: [ ] }
			{ nodes : [ { label: "a" } ],
			edges: [ { head: 0, tails: [ ] } ] }
			</pre>
			** David: yes, tailless edges should be allowed, otherwise it's not nice to represent the set of trees { (a b) , (a (b c)) }. But the two example forests above should be considered equivalent since they generate the same set of trees.

	== Protocol Buffers ==		== Protocol Buffers ==

David Chiang: /* JSON */

2010-11-09T21:53:14Z

JSON

← Older revision		Revision as of 21:53, 9 November 2010
Line 21:		Line 21:
	* Need additional code to check for well-formed hypergraphs, since there is no schema for JSON objects		* Need additional code to check for well-formed hypergraphs, since there is no schema for JSON objects
	* Some languages (e.g., Python) do not natively support event-driven parsers for JSON, meaning it's hard to do process JSON files without first loading the entire thing. Since parse forests can be '''big''' in real applications, event-driven parsers that construct a hypergraph library's internal data structure are crucial. For example, loading the example hypergraph using Python's json.load() command takes almost 10 minutes and 7gb of memory. I understand the desire for familiarity and simplicity, but this scaling behavior makes me worry this won't be usable for real applications.		* Some languages (e.g., Python) do not natively support event-driven parsers for JSON, meaning it's hard to do process JSON files without first loading the entire thing. Since parse forests can be '''big''' in real applications, event-driven parsers that construct a hypergraph library's internal data structure are crucial. For example, loading the example hypergraph using Python's json.load() command takes almost 10 minutes and 7gb of memory. I understand the desire for familiarity and simplicity, but this scaling behavior makes me worry this won't be usable for real applications.
	** For Python, yajl + (~~<a href="~~http://pypi.python.org/pypi/ijson/~~">ijson</a>~~ or ~~<a href="~~http://pykler.github.com/yajl-py/~~">yajl-py</a>~~) might address these concerns.		** For Python, yajl + ijson (http://pypi.python.org/pypi/ijson/) or yajl-py (http://pykler.github.com/yajl-py/) might address these concerns.

	Proposed schema:		Proposed schema: