fixedpoint.jp




2017/10/12

選択バイアスのモデルとしてのBerkson's paradox

選択バイアスは疫学研究などにおいて計画段階で考慮して避けるべきポイントとされています。確率論の基礎、特に条件付き確率についての知識があれば、Berkson's paradoxが選択バイアスの良いモデルを提供してくれることが分かります。

選択バイアスが全てこの形になるかどうかは要検討ですが、少なくとも周辺確率と条件付き確率を混同してしまうときにこのバイアス(やその他のバイアス)が生じると言えます。

#permalink

2017/10/01

1 alphabetについての正規表現が任意の文字列にマッチするかどうかの判定はNP-hard

プログラミングで正規表現というと様々な実装がありますが、元々は正規言語として定義されています。この元々の正規言語にはsubmatch captureといった構文はありません。

同じalphabetに対する2つの正規表現が同じ言語を定義する(つまり、マッチする文字列の集合が同じ)かどうかの判定がNP-hardであることは昔から知られていますが、実際にはこれより強い主張が成り立ちます: {a}という1つのalphabetだけについての正規表現が、a*という正規表現と同じ言語を定義するかどうかの判定もNP-hardです。これを証明している論文では、3-SATの充足可能性判定を上の判定に還元しています。

というわけで、与えられた正規表現が任意のaの有限列にマッチするような"つまらない"ものかどうかを判定するのさえ意外(?)と難しいです。

参考

#permalink

Archives

2017: Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2016: Dec / Nov / Sep / Aug / Jul / Mar / Feb / Jan

2015: Dec / Oct / Sep / Jul / May / Mar / Feb

2014: Dec / Nov / Oct / Aug / Apr / Mar / Feb / Jan

2013: Dec / Nov / Oct / Sep / Aug / Jun / May / Apr / Mar

2012: Nov / Oct / Sep / Jul / Jun / May / Mar / Feb / Jan

2011: Dec / Nov / Oct / Sep / Jul / Jun / Apr / Mar / Feb / Jan

2010: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2009: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2008: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2007: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2006: Dec / Nov / Oct / Sep


© 2006-2017 fixedpoint.jp