SCALABLE WEB DATA EXTRACTION
Example embodiments relate to scalable web data extraction. In example embodiments, a joint potential function is defined for data record segments of web data extracted from a web page, where the joint potential function models data record segmentation of the web data and dependencies between pairs of data segments in the data record segments. At this stage, a principal record segment and several related record segments are identified from the data record segments, where each of the plurality of related record segments is associated with the principal record segment. A related attribute is determined for each related record segment. Next, the joint potential function is applied to the principal record segment and each corresponding related segment to determine a relationship label that describes a data relationship between the principal record segment and the corresponding related segment.
1 . A computing device for scalable web data extraction, the computing device comprising:
a processor to:
define a joint potential function for a plurality of data record segments of web data extracted from a web page, wherein the joint potential function models data record segmentation of the web data and dependencies between pairs of data segments in the plurality of data record segments;
identify a principal record segment and a plurality of related record segments from the plurality of data record segments, wherein each of the plurality of related record segments is associated with the principal record segment;
determine a plurality of related attributes, wherein each attribute of the plurality of related attributes is associated with a corresponding related segment of the plurality of related record segments; and
apply the joint potential function to the principal record segment and each corresponding related segment to determine a corresponding relationship label that describes a data relationship between the principal record segment and the corresponding related segment.
2 . The computing device of claim 1 , wherein the joint potential function is trained using at least one of a stochastic gradient and a limited memory quasi-Newton algorithm, and wherein the joint potential function is concave.
3 . The computing device of claim 2 , wherein the joint potential function is defined as
ℒ
=
log
[
Φ
(
r
,
s
,
x
)
]
-
log
[
Z
(
x
)
]
-
∑
k
=
1
K
λ
k
2
2
σ
λ
2
-
∑
w
=
1
W
μ
w
2
2
σ
μ
2
-
∑
t
=
1
T
ν
t
2
2
σ
ν
2
,
and wherein
Φ(r, s, x)=exp{Σ i=1 |s| Σ k=1 K λ kgk (i, s, x)+Σ m,n M Σ w=1 W μ w q w (r pm , r pn , r)+Σ j=1 L Σ i=1 T v t h t (s p , s j , r)}, Z(x)=Σ y ΠΦ(r, s, x), and 1/2σ λ 2 , 1/2σ μ 2 , 1/2σ v 2 are regularization parameters and s is an assignment of data record segmentation, r is an assignment of attribute labeling, x is the web data, and λ k , μ w , v t are parameters for optimization in a probabilistic model that includes the joint potential function.
4 . The computing device of claim 1 , wherein the joint potential function comprises a semi-Markov assumption for determining the data record segmentation such that each segment feature function depends on a current record segment, a previous record segment, and a comprehensive observation of the web data.
5 . The computing device of claim 1 , wherein the joint potential function is included in a probabilistic model that is defined as
P
(
y
|
x
)
=
1
Z
(
x
)
(
∏
C
S
φ
S
(
i
,
s
,
x
)
)
(
∏
C
R
φ
R
(
r
pm
,
r
pn
,
r
)
)
(
∏
C
∇
φ
∇
(
s
p
,
s
j
,
r
)
)
,
and wherein Z(x) is a normalization factor, φ S is a record segmentation potential function, φ R is an attribute potential function, φ ∇ is the joint potential function, s is an assignment of data record segmentation, and r is an assignment of attribute labeling.
6 . A method for scalable web data extraction, the method comprising:
defining a joint potential function in a probabilistic model for a plurality of data record segments of web data extracted from a web page, wherein the joint potential function is concave and models data record segmentation of the web data and dependencies between pairs of data segments in the plurality of data record segments;
identifying a principal record segment and a plurality of related record segments from the plurality of data record segments, wherein each of the plurality of related record segments is associated with the principal record segment;
determining a plurality of related attributes, wherein each attribute of the plurality of related attributes is associated with a corresponding related segment of the plurality of related record segments; and
applying the joint potential function to the principal record segment and each corresponding related segment to determine a corresponding relationship label that describes a data relationship between the principal record segment and the corresponding related segment.
7 . The method of claim 6 , wherein the joint potential function is trained using at least one of a stochastic gradient and a limited memory quasi-Newton algorithm.
8 . The method of claim 7 , wherein the joint potential function is defined as
ℒ
=
log
[
Φ
(
r
,
s
,
x
)
]
-
log
[
Z
(
x
)
]
-
∑
k
=
1
K
λ
k
2
2
σ
λ
2
-
∑
w
=
1
W
μ
w
2
2
σ
μ
2
-
∑
t
=
1
T
ν
t
2
2
σ
ν
2
,
and wherein
Φ(r, s, x)=exp{Σ i=1 |s| Σ k=1 K λ kgk (i, s, x)+Σ m,n M Σ w=1 W μ w q w (r pm , r pn , r)+Σ j=1 L Σ t=1 T v t h t (s p , s j , r)}, Z(x)=Σ y ΠΦ(r, s, x), and 1/2σ λ 2 , 1/2σ μ 2 , 1/2σ v 2 are regularization parameters and s is an assignment of data record segmentation, r is an assignment of attribute labeling, x is the web data, and λ k , μ w , v t are parameters for optimization in the probabilistic model.
9 . The method of claim 6 , wherein the joint potential function comprises a semi-Markov assumption for determining the data record segmentation such that each segment feature function depends on a current record segment, a previous record segment, and a comprehensive observation of the web data.
10 . The method of claim 6 , wherein the probabilistic model is defined as
P
(
y
|
x
)
=
1
Z
(
x
)
(
∏
C
S
φ
S
(
i
,
s
,
x
)
)
(
∏
C
R
φ
R
(
r
pm
,
r
pn
,
r
)
)
(
∏
C
∇
φ
∇
(
s
p
,
s
j
,
r
)
)
,
and wherein Z(x) is a normalization factor, φ S is a record segmentation potential function, φ R is an attribute potential function, φ ∇ is the joint potential function, s is an assignment of data record segmentation, and r is an assignment of attribute labeling.
11 . A non-transitory machine-readable storage medium encoded with instructions executable by a processor for providing scalable web data extraction, the machine-readable storage medium comprising instructions to:
define a joint potential function for a plurality of data record segments of web data extracted from a web page, wherein the joint potential function models data record segmentation of the web data and dependencies between pairs of data segments in the plurality of data record segments, and wherein the joint potential function is trained using at least one of a stochastic gradient and a limited memory quasi-Newton algorithm;
identify a principal record segment and a plurality of related record segments from the plurality of data record segments, wherein each of the plurality of related record segments is associated with the principal record segment;
determine a plurality of related attributes, wherein each attribute of the plurality of related attributes is associated with a corresponding related segment of the plurality of related record segments; and
apply the joint potential function to the principal record segment and each corresponding related segment to determine a corresponding relationship label that describes a data relationship between the principal record segment and the corresponding related segment.
12 . The non-transitory machine-readable storage medium of claim 11 , wherein the joint potential function is concave.
13 . The non-transitory machine-readable storage medium of claim 12 , wherein the joint potential function is defined as
ℒ
=
log
[
Φ
(
r
,
s
,
x
)
]
-
log
[
Z
(
x
)
]
-
∑
k
=
1
K
λ
k
2
2
σ
λ
2
-
∑
w
=
1
W
μ
w
2
2
σ
μ
2
-
∑
t
=
1
T
ν
t
2
2
σ
ν
2
,
and wherein
Φ(r, s, x)=exp{Σ i=1 |s| Σ k=1 K λ kgk (i, s, x)+Σ m,n M Σ w=1 W μ w q w (r pm , r pn , r)+Σ j=1 L Σ t=1 T v t h t (s p , s j , r)}, Z(x)=Σ y ΠΦ(r, s, x), and 1/2σ λ 2 , 1/2σ μ 2 , 1/2σ v 2 are regularization parameters and s is an assignment of data record segmentation, r is an assignment of attribute labeling, x is the web data, and λ k , μ w , v t are parameters for optimization in a probabilistic model that includes the joint potential function.
14 . The non-transitory machine-readable storage medium of claim 11 , wherein the joint potential function comprises a semi-Markov assumption for determining the data record segmentation such that each segment feature function depends on a current record segment, a previous record segment, and a comprehensive observation of the web data.
15 . The non-transitory machine-readable storage medium of claim 11 , wherein the joint potential function is included in a probabilistic model that is defined as
P
(
y
|
x
)
=
1
Z
(
x
)
(
∏
C
S
φ
S
(
i
,
s
,
x
)
)
(
∏
C
R
φ
R
(
r
pm
,
r
pn
,
r
)
)
(
∏
C
∇
φ
∇
(
s
p
,
s
j
,
r
)
)
,
and wherein Z(x) is a normalization factor, φ S is a record segmentation potential function, φ R is an attribute potential function, φ ∇ is the joint potential function, s is an assignment of data record segmentation, and r is an assignment of attribute labeling.